【机器学习】--Kmeans从初识到应用

一.前述

Kmeans算法一般在数据分析前期使用,选取适当的k,将数据分类后,然后分类研究不同聚类下数据的特点。

Kmeans算法是一种无监督的算法。 

常用于分组,比如用户偏好。

二.概念及原理

Kmeans原理:

      1 随机选取k个中心点

      2 遍历所有数据,将每个数据划分到最近的中心点中

      3 计算每个聚类的平均值,并作为新的中心点

      4 重复2-3,直到这k个中线点不再变化(收敛了),或执行了足够多的迭代。

样本点之间的相似度距离计算:

1.欧氏距离相似度(常用!!!

2.Jaccard相似度(用于比较样本之间的相似性,系数值越大表示值越高

3.余弦相似度

余弦相似度值在[-1,1]之间,值越趋近于1代表越相近,越趋近于-1,代表越相反,接近于0,代表两个向量正交。

常用计算文本相似性!!!将两个文本根据他们词,建立两个向量,计算这两个向量的余弦值,就可以知道两个文本在统计学方法中他们的相似度情况。

4.Pearson相似度

5.相对熵(K-L距离)

 总结:

对于高维空间点之间的度量,用欧氏距离。

对于集合度量Jaccard相似度。

     对于自然语言处理用余弦相似度。

     对于函数度量用Pearson相似度

目标函数:

考虑欧几里得距离的数据,使用误差平方和(Sum of the Squared Error,SSE)作为聚类的目标函数,两次运行K均值产生的两个不同的簇集,我们更喜欢SSE最小的那个。

k表示k个聚类中心,ci表示第几个中心,dist表示的是欧几里得距离。 这里有一个问题就是为什么,我们更新质心是让所有的点的平均值,这里就是SSE所决定的。

通俗来说,每个点计算 到所在分配的中心店的距离,然后加和。

随着k的增长损失函数,逐渐递减。肘部法就是计算不同的K,然后计算SSE,求最大的两组即可。

选择一开始下降速度快,后来下降速度慢的。

肘部法图解:

聚类评价方法:

常见的聚类评测指标有纯度和 F 值,其中 F 值更为常用。

F 值的更普适的应用是信息检索的结果,其计算包括了两个指标:召回率(Recall Rate)和准确率(Precision Rate)。

  • 召回率的定义为:检索出的相关文档数和文档库中所有的相关文档数的比率,衡量的是检索系统的查全率;
  • 准确率的定义为:检索出相关文档数与检索出的文档总数的比率,衡量的是检索系统的查准率;F 值为两者的调和平均值。

以上评估方法都是基于原始数据事先知道一定的标签,但这种似乎并不太常用,所以常用的评估模型的指标是轮廓系数,适用于在一开始不知道标签的情况下。

具体如下:

轮廓系数它结合内聚度和分离度两种因素。可以用来在相同原始数据的基础上用来评价不同算法、或者算法不同运行方式对聚类结果所产生的影响。

方法:

                  1,计算样本i到同簇其他样本的平均距离ai。ai 越小,说明样本i越应该被聚类到该簇。将ai 称为样本i的簇内不相似度

簇C中所有样本的a i 均值称为簇C的簇不相似度。

                  2,计算样本i到其他某簇Cj 的所有样本的平均距离bij,称为样本i与簇Cj 的不相似度。定义为样本i的簇间不相似度:bi =min{bi1, bi2, ..., bik}

                            bi越大,说明样本i越不属于其他簇。

                  3,根据样本i的簇内不相似度a i 和簇间不相似度b i ,定义样本i的轮廓系数

                 4,判断:

                            si接近1,则说明样本i聚类合理;

                            si接近-1,则说明样本i更应该分类到另外的簇;

                            若si 近似为0,则说明样本i在两个簇的边界上。

结果为负数则可以直接放弃了!!!说明分类的很不好。

二分Kmeans原理:

为了得到k个簇,将所有点的集合分裂成两个簇,从这些簇中选取一个继续分裂,如此下去,直到产生k个簇。

比如要分成5个组,第一次分裂产生2个组,然后从这2个组中选一个目标函数产生的误差比较大的,分裂这个组产生2个,这样加上开始那1个就有3个组了,然后再从这3个组里选一个分裂,产生4个组,重复此过程,产生5个组。这算是一中基本求精的思想。二分k均值不太受初始化的困扰,因为它执行了多次二分试验并选取具有最小误差的试验结果,还因为每步只有两个质心。

Kmeans++原理:

k-means++算法选择初始seeds的基本思想就是:初始的聚类中心之间的相互距离要尽可能的远。

  1. 从输入的数据点集合中随机选择一个点作为第一个聚类中心
  2. 对于数据集中的每一个点x,计算它与聚类中心(指已选择的聚类中心)的距离D(x),然后对于每一个点/总和得出一个概率,则第二个点依据概率进行选择。第三个点的选择是其他所有的点到前两个点的距离然后加和,再计算每一个点/总和的概率,再选择一个中心店。以此类推。。。。。
  3. 选择一个新的数据点作为新的聚类中心,选择的原则是:D(x)较大的点被选取作为聚类中心的概率较大(概率化选择)

利用Canopy计算初始类簇中心点。

不需要迭代,比较快

步骤:

1.首先定义两个距离T1和T2,T1>T2.从初始的点的集合S中随机移除一个点P,然后对于还在S中的每个点I,计算该点I与点P的距离。

2.如果距离小于T1,则将点I加入到点P所代表的Canopy中,如果距离小于T2,则将点I从集合S中移除,并将点I加入到点P所代表的Canopy中。

3.迭代完一次之后,重新从集合S中随机选择一个点作为新的点P,然后重复执行以上步骤。

图示:

总结:与中心的距离大于T1时,这些点就不会被归入到中心所在的这个canopy类中。然当距离小于T1大于T2时,这些点会被归入到该中心所在的canopy中,但是它们并不会从D中被移除,也就是说,它们将会参与到下一轮的聚类过程中,成为新的canopy类的中心或者成员。亦即,两个Canopy类中有些成员是重叠的。而当距离小于T2的时候,这些点就会被归入到该中心的canopy类中,而且会从D中被移除,也就是不会参加下一次的聚类过程了。

 三、代码

代码一:Kmeans实现

# !/usr/bin/python
# -*- coding:utf-8 -*-

import numpy as np
import matplotlib.pyplot as plt
import sklearn.datasets as ds
import matplotlib.colors
from sklearn.cluster import KMeans


def expand(a, b):
    d = (b - a) * 0.1
    return a-d, b+d


if __name__ == "__main__":
    N = 400#400个数据点
    centers = 4#4个中心店
    data, y = ds.make_blobs(N, n_features=2, centers=centers, random_state=2)#聚类测试点 创建高沙分布的点
    data2, y2 = ds.make_blobs(N, n_features=2, centers=centers, cluster_std=(1, 2.5, 0.5, 2), random_state=2)#每个类别的标准差不一样,u是正态分布,胖瘦
    data3 = np.vstack((data[y == 0][:], data[y == 1][:50], data[y == 2][:20], data[y == 3][:5]))#垂直放 每个类别生成一百个数据 每个类别拿的数据不一样。目的是每一个簇里面的密度不一样,看看聚类效果。
    y3 = np.array([0] * 100 + [1] * 50 + [2] * 20 + [3] * 5)#自己构建label

    cls = KMeans(n_clusters=4, init='k-means++')
    y_hat = cls.fit_predict(data)
    y2_hat = cls.fit_predict(data2)
    y3_hat = cls.fit_predict(data3)

    m = np.array(((1, 1), (1, 3)))#矩阵点乘 ,相当于旋转
    data_r = data.dot(m)
    y_r_hat = cls.fit_predict(data_r)

    matplotlib.rcParams['font.sans-serif'] = [u'SimHei']
    matplotlib.rcParams['axes.unicode_minus'] = False
    cm = matplotlib.colors.ListedColormap(list('rgbm'))

    plt.figure(figsize=(9, 10), facecolor='w')
    plt.subplot(421)
    plt.title(u'原始数据')
    plt.scatter(data[:, 0], data[:, 1], c=y, s=30, cmap=cm, edgecolors='none')#坐标轴
    x1_min, x2_min = np.min(data, axis=0)
    x1_max, x2_max = np.max(data, axis=0)
    x1_min, x1_max = expand(x1_min, x1_max)
    x2_min, x2_max = expand(x2_min, x2_max)
    plt.xlim((x1_min, x1_max))
    plt.ylim((x2_min, x2_max))
    plt.grid(True)

    plt.subplot(422)
    plt.title(u'KMeans++聚类')
    plt.scatter(data[:, 0], data[:, 1], c=y_hat, s=30, cmap=cm, edgecolors='none')
    plt.xlim((x1_min, x1_max))
    plt.ylim((x2_min, x2_max))
    plt.grid(True)

    plt.subplot(423)
    plt.title(u'旋转后数据')
    plt.scatter(data_r[:, 0], data_r[:, 1], c=y, s=30, cmap=cm, edgecolors='none')
    x1_min, x2_min = np.min(data_r, axis=0)
    x1_max, x2_max = np.max(data_r, axis=0)
    x1_min, x1_max = expand(x1_min, x1_max)
    x2_min, x2_max = expand(x2_min, x2_max)
    plt.xlim((x1_min, x1_max))
    plt.ylim((x2_min, x2_max))
    plt.grid(True)

    plt.subplot(424)
    plt.title(u'旋转后KMeans++聚类')
    plt.scatter(data_r[:, 0], data_r[:, 1], c=y_r_hat, s=30, cmap=cm, edgecolors='none')
    plt.xlim((x1_min, x1_max))
    plt.ylim((x2_min, x2_max))
    plt.grid(True)

    plt.subplot(425)
    plt.title(u'方差不相等数据')
    plt.scatter(data2[:, 0], data2[:, 1], c=y2, s=30, cmap=cm, edgecolors='none')
    x1_min, x2_min = np.min(data2, axis=0)
    x1_max, x2_max = np.max(data2, axis=0)
    x1_min, x1_max = expand(x1_min, x1_max)
    x2_min, x2_max = expand(x2_min, x2_max)
    plt.xlim((x1_min, x1_max))
    plt.ylim((x2_min, x2_max))
    plt.grid(True)

    plt.subplot(426)
    plt.title(u'方差不相等KMeans++聚类')
    plt.scatter(data2[:, 0], data2[:, 1], c=y2_hat, s=30, cmap=cm, edgecolors='none')
    plt.xlim((x1_min, x1_max))
    plt.ylim((x2_min, x2_max))
    plt.grid(True)

    plt.subplot(427)
    plt.title(u'数量不相等数据')
    plt.scatter(data3[:, 0], data3[:, 1], s=30, c=y3, cmap=cm, edgecolors='none')
    x1_min, x2_min = np.min(data3, axis=0)
    x1_max, x2_max = np.max(data3, axis=0)
    x1_min, x1_max = expand(x1_min, x1_max)
    x2_min, x2_max = expand(x2_min, x2_max)
    plt.xlim((x1_min, x1_max))
    plt.ylim((x2_min, x2_max))
    plt.grid(True)

    plt.subplot(428)
    plt.title(u'数量不相等KMeans++聚类')
    plt.scatter(data3[:, 0], data3[:, 1], c=y3_hat, s=30, cmap=cm, edgecolors='none')
    plt.xlim((x1_min, x1_max))
    plt.ylim((x2_min, x2_max))
    plt.grid(True)

    plt.tight_layout(2, rect=(0, 0, 1, 0.97))
    plt.suptitle(u'数据分布对KMeans聚类的影响', fontsize=18)
    # https://github.com/matplotlib/matplotlib/issues/829
    # plt.subplots_adjust(top=0.92)
    # plt.show()
    plt.savefig('cluster_kmeans')

  结果:

代码二:评估指标

# !/usr/bin/python
# -*- coding:utf-8 -*-

from sklearn import metrics#评估


if __name__ == "__main__":
    y = [0, 0, 0, 1, 1, 1]
    y_hat = [0, 0, 1, 1, 2, 2]
    h = metrics.homogeneity_score(y, y_hat)
    c = metrics.completeness_score(y, y_hat)
    print(u'同一性(Homogeneity):', h)
    print(u'完整性(Completeness):', c)
    v2 = 2 * c * h / (c + h)
    v = metrics.v_measure_score(y, y_hat)
    print(u'V-Measure:', v2, v)

    y = [0, 0, 0, 1, 1, 1]
    y_hat = [0, 0, 1, 3, 3, 3]
    h = metrics.homogeneity_score(y, y_hat)
    c = metrics.completeness_score(y, y_hat)
    v = metrics.v_measure_score(y, y_hat)
    print(u'同一性(Homogeneity):', h)
    print(u'完整性(Completeness):', c)
    print(u'V-Measure:', v)

    # 允许不同值
    y = [0, 0, 0, 1, 1, 1]
    y_hat = [1, 1, 1, 0, 0, 0]
    h = metrics.homogeneity_score(y, y_hat)
    c = metrics.completeness_score(y, y_hat)
    v = metrics.v_measure_score(y, y_hat)
    print(u'同一性(Homogeneity):', h)
    print(u'完整性(Completeness):', c)
    print(u'V-Measure:', v)

    y = [0, 0, 1, 1]
    y_hat = [0, 1, 0, 1]
    ari = metrics.adjusted_rand_score(y, y_hat)
    print(ari)

    y = [0, 0, 0, 1, 1, 1]
    y_hat = [0, 0, 1, 1, 2, 2]
    ari = metrics.adjusted_rand_score(y, y_hat)
    print(ari)

均一性,一个簇中只包含一个类别样本,Precision 完整性,同类别样本被归到同一个簇中,Recall

V-Measure:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

资源 | 从ReLU到Sinc,26种神经网络激活函数可视化

3239
来自专栏深度学习那些事儿

利用pytorch实现Visualising Image Classification Models and Saliency Maps

saliency map即特征图,可以告诉我们图像中的像素点对图像分类结果的影响。

2484
来自专栏目标检测和深度学习

KNN算法虹膜图片识别(源码)

2682
来自专栏自学笔记

Hidden Markov ModelHMM隐马尔科夫模型

等等,这种序列叫可见状态序列,但在HMM里面,还存在一个隐含状态链,比如这个状态链可能是

2432
来自专栏Petrichor的专栏

深度学习: ResNet (残差) 网络

ResNet (残差) 网络 由He Kaiming、Sun jian等大佬在2015年的论文 Deep Residual Learning for Image...

7852
来自专栏MixLab科技+设计实验室

深度学习生成舞蹈影片01之MDN

Dance generator using Variational Autoencoder, LSTM and Mixture Density Network.

3283
来自专栏大数据文摘

手把手 | 30行JavaScript代码,教你分分钟创建神经网络

1723

用Pandas在Python中可视化机器学习数据

为了从机器学习算法中获取最佳结果,你就必须要了解你的数据。

2235
来自专栏SnailTyan

ResNet论文翻译——中文版

Deep Residual Learning for Image Recognition 摘要 更深的神经网络更难训练。我们提出了一种残差学习框架来减轻网络训...

3947
来自专栏企鹅号快讯

详解各种随机算法

转自:JarvisChu 之前将的算法都是确定的,即对于相同的输入总对应着相同的输出。但实际中也常常用到不确定的算法,比如随机数生成算法,算法的结果是不确定的,...

5149

扫码关注云+社区

领取腾讯云代金券