机器学习-吴恩达笔记8(1)之K-means

作者: 皮皮大 | 来源:发表于2019-12-04 21:22 被阅读0次

    Week8-聚类与降维

    无监督学习unsupervised learning

    无监督学习简介

    聚类和降维是无监督学习方法,在无监督学习中数据是没有标签的。

    比如下面的数据中,横纵轴都是​,没有标签(输出​)。在非监督学习中,我们需要将一系列无标签的训练数据,输入到一个算法中,快速这个数据的中找到其内在数据结构。

    image

    无监督学习应用

    • 市场分割

    • 社交网络分析

    • 组织计算机集群

    • 了解星系的形成

    image

    聚类

    聚类clustering

    聚类试图将数据集中的样本划分成若干个通常是不相交的子集,称之为“簇cluster”。聚类可以作为一个单独过程,用于寻找数据内部的分布结构,也能够作为其他学习任务的前驱过程。聚类算法涉及到的两个问题:性能度量和距离计算

    性能度量

    聚类性能度量也称之为“有效性指标”。希望“物以类聚”。聚类的结果是“簇内相似度高”和“簇间相似度低”。

    常用的外部指标是:

    1. Jaccard 系数
    2. FM 系数
    3. Rand 系数

    上述3个系数的值都在[0,1]之间,越小越好

    常用的内部指标是:

    1. DB指数
    2. Dunn指数

    DBI的值越小越好,Dunn的值越大越好。

    距离计算

    x_i,x_jL_p的距离定义为
    L_p(x_i,x_j)=(\sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|^p)^\frac{1}{p}

    规定:p\geq1,常用的距离计算公式有

    • p=2时,即为欧式距离,比较常用,即:
      L_2(x_i,x_j)=(\sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|^2)^\frac{1}{2}
    • p=1时,即曼哈顿距离,即:
      L_1(x_i,x_j)=(\sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|

    • p趋于无穷,为切比雪夫距离,它是各个坐标距离的最大值:
      L_{\infty}(x_i,x_j)=\mathop {max}\limits_{l}|x_i^{(l)}-x_j^{(l)}|

    余弦相似度

    \cos (\theta)=\frac{x^{T} y}{|x| \cdot|y|}=\frac{\sum_{i=1}^{n} x_{i} y_{i}}{\sqrt{\sum_{i=1}^{n} x_{i}^{2}} \sqrt{\sum_{i=1}^{n} y_{i}^{2}}}

    Pearson皮尔逊相关系数

    \rho_{X Y}=\frac{\operatorname{cov}(X, Y)}{\sigma_{X} \sigma_{Y}}=\frac{E\left[\left(X-\mu_{X}\right)\left(Y-\mu_{Y}\right)\right]}{\sigma_{X} \sigma_{Y}}=\frac{\sum_{i=1}^{n}\left(x-\mu_{X}\right)\left(y-\mu_{Y}\right)}{\sqrt{\sum_{i=1}^{n}\left(x-\mu_{X}\right)^{2}} \sqrt{\sum_{i=1}^{n}\left(y-\mu_{Y}\right)^{2}}}

    K-均值算法

    算法思想

    K-均值,也叫做k-means算法,最常见的聚类算法,算法接受一个未标记的数据集,然后将数据聚类成不同的组。 假设将数据分成n个组,方法为:

    • 随机选择K个点,称之为“聚类中心”
    • 对于数据集中的每个数据,按照距离K个中心点的距离,将其和距离最近的中心点关联起来,与同个中心点关联的所有点聚成一类。
    • 计算上面步骤中形成的类的平均值,将该组所关联的中心点移动到平均值的位置
    • 重复上面两个步骤,直到中心点不再变化。

    图解K-means

    1. 给定需要划分的数据,随机确定两个聚类中心点
    2. 计算其他数据和这两个中心点的距离,划入距离小的类中,假设两个类是C_1,C_2
    3. 确定上述步骤中两个类是C_1,C_2的均值,这个均值就是新的聚类中心
    4. 重复:计算数据和这两个中心点的距离,划入距离小的类中,形成新的类;再确定新的聚类中心
    5. 直至中心点不再变化,结束
    image image image image image

    全过程

    image

    K-mean算法过程

    吴恩达视频的中的伪代码为

    repeat {
      for i= to m
      #  计算每个样例属于的类
      c(i) := index (from 1 to K)  of cluster centroid closest to x(i)
      
     for k = 1 to K
      # 聚类中心的移动,重新计算该类的质心
     u(k) := average (mean) of points assigned to cluster K
    }
    

    西瓜书中的伪代码

    image

    优化目标Optimization Objective

    K-均值最小化问题,是要最小化所有的数据点与其所关联的聚类中心点之间的距离之和,因此 K-均值的代价函数(畸变函数Distortion function
    J\left(c^{(1)}, \ldots, c^{(m)}, \mu_{1}, \ldots, \mu_{K}\right)=\frac{1}{m} \sum_{i=1}^{m}\left\|X^{(i)}-\mu_{c^{(i)}}\right\|^{2}
    其中u_{c^{(i)}}代表的是x^{(i)}最近的聚类中心点。优化目标就是找出使得代价函数最小的c^{(1)},c^{(2)},…,c^{(m)}\mu^1,\mu^2,…,\mu^k,即:

    image

    随机初始化

    在运行K-均值算法的之前,首先要随机初始化所有的聚类中心点:

    • 选择K < m,即聚类中心的个数小于训练样本的实例数量
    • 随机训练K个训练实例,然后令K个聚类中心分别和这K个训练实例相等

    关于K-means的局部最小值问题:

    image

    Scikit learn 实现K-means

    make_blobs数据集

    make_blobs聚类数据生成器make_blobs方法常被用来生成聚类算法的测试数据。它会根据用户指定的特征数量、中心点数量、范围等来生成几类数据。

    主要参数

    sklearn.datasets.make_blobs(n_samples=100, n_features=2,centers=3, cluster_std=1.0, center_box=(-10.0, 10.0), shuffle=True, random_state=None)[source]
    
    • n_samples是待生成的样本的总数
    • n_features是每个样本的特征数
    • centers表示类别数
    • cluster_std表示每个类别的方差
    import numpy as np
    import matplotlib.pyplot as plt
    
    # 导入 KMeans 模块和数据集
    from sklearn.cluster import KMeans
    from sklearn.datasets import make_blobs
    
    # 定义画布
    plt.figure(figsize=(12,12))
    
    # 定义样本量和随机种子
    n_samples = 1500
    random_state = 170
    
    # X是测试数据集,y是目标分类标签0,1,2
    X, y = make_blobs(n_samples=n_samples, random_state=random_state)
    
    X
    
    array([[-5.19811282e+00,  6.41869316e-01],
           [-5.75229538e+00,  4.18627111e-01],
           [-1.08448984e+01, -7.55352273e+00],
           ...,
           [ 1.36105255e+00, -9.07491863e-01],
           [-3.54141108e-01,  7.12241630e-01],
           [ 1.88577252e+00,  1.41185693e-03]])
    
    y
    
    array([1, 1, 0, ..., 2, 2, 2])
    
    # 预测值的簇类
    y_pred = KMeans(n_clusters=2, random_state=random_state).fit_predict(X)
    
    y_pred
    
    array([0, 0, 1, ..., 0, 0, 0], dtype=int32)
    
    X[:,0]  # 所有行的第1列数据
    
    array([ -5.19811282,  -5.75229538, -10.84489837, ...,   1.36105255,
            -0.35414111,   1.88577252])
    
    # 子图1的绘制
    plt.subplot(221)
    plt.scatter(X[:, 0], X[:, 1], c=y_pred)
    plt.title("incorrrect Number of Blods")
    
    image
    transformation = [[0.60834549, -0.63667341],[-0.40887718, 0.85253229]]
    X_aniso = np.dot(X, transformation)
    y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X_aniso)
    
    # 子图2的绘制
    plt.subplot(222)
    plt.scatter(X_aniso[:, 0], X_aniso[:, 1], c=y_pred)
    plt.title("Anisotropicly Distributed Blobs")
    
    image
    X_varied, y_varied = make_blobs(n_samples=n_samples,
                                   cluster_std=[1.0,2.5,0.5],random_state=random_state)
    y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X_varied)
    
    plt.subplot(223)
    plt.scatter(X_varied[:, 0], X_varied[:, 1], c=y_pred)
    plt.title("Unequal Variance")
    
    image
    X_filtered = np.vstack((X[y == 0][:500], 
                          X[y == 1][:100],
                          X[y == 2][:10]))
    y_pred = KMeans(n_clusters=3,random_state=random_state).fit_predict(X_filtered)
    
    plt.subplot(224)
    plt.scatter(X_filtered[:, 0],
               X_filtered[:, 1],
               c=y_pred)
    plt.title("Unevenly Sized Blobs")
    plt.show()
    
    image

    python实现KNN算法

    import numpy as np
    import random
    import pandas as pd
    import re
    import matplotlib.pyplot as plt
    
    def show_fig():
        dataSet = loadDataSet()
        fig = plt.figure()
        ax = fig.add_subplot(111)
        ax.scatter(dataSet[:, 0], dataSet[:, 1])
        plt.show()
    
    def calcuDistance(vec1, vec2):
        # 步骤1:定义欧式距离的公式
        # 计算两个向量之间的欧式距离:根号下[(x_1-x_2)^2+(y_1-y_2)^2+...+(x_n-y_n)^2]
        # ver1 - ver2:表示两个向量的对应元素相减
        return np.sqrt(np.sum(np.square(vec1 - vec2)))  #注意这里的减号
    
    def loadDataSet():
        # 导入数据集,填写路径
        dataSet = np.loadtxt("/Users/peter/skl/cluster/dataset.csv")
        print(dataSet)
        return dataSet
    
    def initCentroids(dataSet, k):
        # 步骤2:初始化质心
        # dataset: 传入的数据
        # k: 选择分类的质心个数(也就是簇的个数)
        dataSet = list(dataSet)
        return random.sample(dataSet, k)   # 使用random模块,随机选取k个样本数据
    
    def minDistance(dataSet, centroidList):
            # 步骤3:计算每个实例 item 和 centroidList 中k个质心的距离
        # 找出上面距离的最小值,并且加入相应的簇类中,总共k个簇
        clusterDict = dict()  # 用于保存簇类结果
        clusterDict = dict()  # dict保存簇类结果
        k = len(centroidList)
        for item in dataSet:
            vec1 = item
            flag = -1
            minDis = float("inf") # 初始化为最大值
            for i in range(k):
                vec2 = centroidList[i]
                distance = calcuDistance(vec1, vec2)  # error
                if distance < minDis:
                    minDis = distance
                    flag = i  # 循环结束时, flag保存与当前item最近的蔟标记
            if flag not in clusterDict.keys():
                clusterDict.setdefault(flag, [])
            clusterDict[flag].append(item)  #加入相应的类别中
        return clusterDict  #不同的类别
    
    def getCentroids(clusterDict):
        #重新计算k个质心
        centroidList = []
        for key in clusterDict.keys():
            centroid = np.mean(clusterDict[key], axis=0)
            centroidList.append(centroid)
        return centroidList  #得到新的质心
    
    
    def getVar(centroidList, clusterDict):
        # 计算各蔟集合间的均方误差
        # 将蔟类中各个向量与质心的距离累加求和
        sum = 0.0
        for key in clusterDict.keys():
            vec1 = centroidList[key]
            distance = 0.0
            for item in clusterDict[key]:
                vec2 = item
                distance += calcuDistance(vec1, vec2)
            sum += distance
        return sum
    
    def showCluster(centroidList, clusterDict):
        # 展示聚类结果
        colorMark = ['or', 'ob', 'og', 'ok', 'oy', 'ow'] # 不同簇类标记,o表示圆形,另一个表示颜色
        centroidMark = ['dr', 'db', 'dg', 'dk', 'dy', 'dw']
    
        for key in clusterDict.keys():
            plt.plot(centroidList[key][0], centroidList[key][1], centroidMark[key], markersize=12) #质心点
            for item in clusterDict[key]:
                plt.plot(item[0], item[1], colorMark[key])
        plt.show()
    
    
    def main():
        dataSet = loadDataSet()
        centroidList = initCentroids(dataSet, 4)
        clusterDict = minDistance(dataSet, centroidList)
        # # getCentroids(clusterDict)
        # showCluster(centroidList, clusterDict)
        newVar = getVar(centroidList, clusterDict)
        oldVar = 1  # 当两次聚类的误差小于某个值是,说明质心基本确定。
    
        times = 2
        while abs(newVar - oldVar) >= 0.00001:
            centroidList = getCentroids(clusterDict)
            clusterDict = minDistance(dataSet, centroidList)
            oldVar = newVar
            newVar = getVar(centroidList, clusterDict)
            times += 1
            showCluster(centroidList, clusterDict)
    
    if __name__ == '__main__':
        show_fig()
        main()
    

    相关文章

      网友评论

        本文标题:机器学习-吴恩达笔记8(1)之K-means

        本文链接:https://www.haomeiwen.com/subject/kxcrgctx.html