数学文化节|K-聚类算法

vlambda
2020-06-15

数学文化节|K-聚类算法

如果我们有一组人的收入和支出，

我们可以将他们分为以下几类：

高收入，高消费

高收入，低消费

低收入，低消费

低收入，高消费

什么叫聚类

从上述例子，我们不难引出概念：

简单来说，聚类是指根据相似数据点的属性或特征将它们分组在一起。

在比较专业的术语中，聚类是一个无监督的分类算法，是由计算机自己找出规律，把有相似属性的样本放在一组，每个小组也称为簇。

在第一种分类中，机器学习算法可以分为两类，一类是监督学习，一类是无监督学习。监督的意思是，这一个算法需要事先用一些正确的数据来进行训练，使这个算法的模型中的待定参数被确定下来，然后才能用于其他的数据。而无监督机器学习算法不需要对它们进行事先训练，运用时，直接立足于数据即可使用。另一种分类中，学习模型又可以分为两类，分类和回归。分类模型：目标变量是离散的分类型变量；回归模型：目标变量是连续性数值型变量。

当然分类算法有很多种，下面我们要介绍最出名的一个分类算法k-menas算法，也叫做k聚类算法。

什么是k-means算法

K-means有一个很著名很清晰的解析，就是牧师-村民模型。

根据上面这个故事，我们可以简单来概括一下K-means算法的一般步骤，K-Means聚类步骤是一个循环迭代的算法，非常简单易懂：

Step1：确定类别数量K，K值人为设定，在训练数据分布范围内，随机选择K个点作为初始中心点；

Step2：按照距离最小原则，把所有数据点分到距离最近的中心点所在的类中；

step3：每类中有若干个数据点，计算K个类中所有数据点的均值，作为下一次迭代的中心点；

Step4：重复step2、step3步，直到收敛（每个数据点所属类别或中心点不再改变），聚类过程结束。

如何实现k-means算法

k聚类算法的实现有很多版本，我们先来看看最初级的版本（这一个版本对应了上面所说的简单概括），在这个版本中，聚类中心的个数是事先确定好的，设为k。

No.1

目的

在若干个点中找出它们的聚类中心（聚类中心也就是在这一个周围聚集了很多其他的点的点，而周围聚集的其他的点，叫做这个聚点中心的聚类域），如图所示。

（f中即为表示最终目的的图，红色和蓝色的×是两个聚类中心，与它们颜色相同的点表示该聚类中心对应的聚类。从图a到f即为下面所讲解的实现步骤对这些数据的应用）

No.2

实现步骤

初始状态

任选k个初始聚类中心，z1(1),z2(1),……zk(1)。

迭代步骤1

（1）在第m轮迭代开始时，聚类中心为z2(m)，z1(m)，……zk(m)，这k个聚点的聚类域为fj(m)，j=1,2，……，k，fj(m)为空集。然后，将样本集合中的每一个样本按距离最先原则分配给k个聚类中心，即在第m次迭代时，若||x-zj(m)||<||x-zi(m)||，对任意i=1,2，……k，且，则令点x∈fj(m)。

迭代步骤2

当每个聚点的聚类域已经完全确定下来过后，我们计算新的聚点中心，zi(m+1)=1/N*Σx（x∈fi（x）)，i=1,2，……k，计算出来新的聚点中心过后，就可以进入下一轮迭代，回到步骤（2）

迭代终止

若zi(m+1)=zi(m)，任意i=1，2，……，k，则算法终止，计算完毕，此时求出的这k个聚点中心z2(m)，z1(m),……zk(m)即为最终答案。

No.3

算法的评价

该算法快速简单，时间复杂度近乎线性，且为无监督机器学习算法，但是，该算法也有一些缺点，首先，k值需要确定下来，这个k值不一定是最好的k值，而且算法不一定收敛，如果初始状态的聚类中心选择不合理，迭代过程会发散。

No.4

算法的改进

算法的改进分为两种，分别针对前面所说的两个缺点进行改进，下面的第一个是改进k值必须事先确定这个缺点的，第二个改善改进的是“改善初始聚类的选择使得迭代过程收敛”

对k值的选取方式的改进

改善的依据：在k未知时，假设给定数据集最合理的划分的聚类数为k，若在实际中，k值为，则一般会产生下面两种情况。

（1）k1>k,说明至少有一个合理划分的类被划分为若干类

（2）k1<k,说明至少有两个合理划分的类被划分为若干类

但是，怎样评估一个类是否合理呢？我们可以实现设置一个边界距离的阈值（边界距离就是在两个或多个聚类域中的点之间的最小距离，和平面上定义两个区域的距离类似）d，如果划分得到的聚类域的边界距离小于这个阈值，我们就可以把这些聚类域合并成同一个聚类域，因为他们靠的足够近。具体的做法如下：

（1）首先取k1=n^1/2作为k值得上限，n为样本数（一般来说，聚类域的个数不会超过n^1/2），对样本集运行未改进的k聚类算法（k=n^1/2），得到k个聚类

（2）判断k个聚类中是否有聚类的边界距离小于设定的阈值，若有，则将这些聚类合并，相应的k值也减小。若没有，此时的k值即为最合理的分类值，此时的分类即是最合理的分类，算法结束

（3）把最新获得的k值作为输入对样本集运行未改进的k聚类算法，得到k个新的聚类

（4）重复（2）（3），直到算法结束为止。

改进初始聚类中心得选择方式使得k聚类算法收敛

由于这个改进的实现较为复杂，我们大致介绍一下它的思想。为了使k聚类算法收敛，我们最后得到的聚类应当包含所有的数据点，所以初始状态下，聚类中心的选择应当较为分散，同时，应该考虑密度因素，即聚类中心应当选择分散的且局部集中的点作为聚类中心。那么，现在的问题就是如何衡量分散和密度因素呢？设n个样本点为{x1，x2，……xn}密度的计算方式，可以考虑dens(xi)=zi/Σzk(k=1,2,……,n)，其中的zi称为样本间的距离参数，定义为zi=Σ1/||xk-xi||^a(k=1,2,i-1,i+1……,n),a为密度系数，可以取任意大于1的数，dens(xi)越大，样本点xi周围的点越多，也就是密度越大；dens(xi)越小，样本点周围的点越少，也就是密度越小。而分散程度的衡量，可以考虑共享最近邻（SNN）相似度。这一个改进的具体实现，有兴趣的同学可以自行查阅。

No.5

算法的实现

参数的含义：

①X为数据矩阵，是一个N*P的数据矩阵，一行代表一个数据，每一列表示一个属性。

②k为一个整数，表示聚类的个数

③Idx是一个n*1的列向量，每一个数字对应一个数据点，表示每个点的聚类的中心的标号，取值为1~k

④C是一个k*P的数据矩阵，表示每一个聚类的聚类中心得位置

⑤sumD是一个k*1的列向量，向量中的每一个数字表示每一个聚类域中点到聚类中心的距离之和

⑥D是一个N*k的矩阵，储存的是每一个点到所有聚类中心的距离。

k聚类算法在matlab中，被简化为一个函数keans（）就可以实现，它的实现方法由下面几种形式，其中X和k是事先已知的

Idx=kmeans(X,k) [Idx,C]=kmeans(X,k)

[idx,C,sumD]=kmeans(X,k) [idx,C,sumD,D]=kmeans(X,k)

而关于kmenas函数的高级用法，比如选择测度是欧式测度还是其他，可以通过

help kmeans指令查找，这里就不再赘述。

k-means算法的应用

基于用户位置信息的商业选址

随着信息技术的快速发展，移动设备和移动互联网已经普及到千家万户。在用户使用移动网络时，会自然的留下用户的位置信息。随着近年来GIS地理信息技术的不断完善普及，结合用户位置和GIS地理信息将带来创新应用。如百度与万达进行合作，通过定位用户的位置，结合万达的商户信息，向用户推送位置营销服务，提升商户效益。希望通过大量移动设备用户的位置信息，为某连锁餐饮机构提供新店选址。

国家电网用户画像

随着电力体制改革向纵深推进，售电侧逐步向社会资本放开，当下的粗放式经营和统一式客户服务内容及模式，难以应对日益增长的个性化、精准化客户服务体验要求。如何充分利用现有数据资源，深入挖掘客户潜在需求，改善供电服务质量，增强客户黏性，对公司未来发展至关重要。

对电力服务具有较强敏感度的客户对于电费计量、供电质量、电力营销等各方面服务的质量及方式上往往具备更高的要求，成为各级电力公司关注的重点客户。经过多年的发展与沉淀，目前国家电网积累了全网4亿多客户档案数据和海量供电服务信息，以及公司营销、电网生产等数据，可以有效的支撑海量电力数据分析。

因此，国家电网公司希望通过大数据分析技术，科学的开展电力敏感客户分析，以准确地识别敏感客户，并量化敏感程度，进而支撑有针对性的精细化客户服务策略，控制电力服务人工成本、提升企业公众形象。

非人恶意流量识别

2016年第一季度Facebook发文称，其Atlas DSP平台半年的流量质量测试结果显示，由机器人模拟和黑IP等手段导致的非人恶意流量高达75% . 仅2016上半年，AdMaster反作弊解决方案认定平均每天能有高达 28% 的作弊流量。低质量虚假流量的问题一直存在，这也是过去十年间数字营销行业一直在博弈的问题。基于AdMaster海量监测数据，50%以上的项目均存在作弊嫌疑；不同项目中，作弊流量占广告投放5%到95%不等；其中垂直类和网盟类媒体的作弊流量占比最高；PC端作弊流量比例显著高于移动端和智能电视平台。广告监测行为数据被越来越多地用于建模和做决策，例如绘制用户画像，跨设备识别对应用户等。作弊行为，恶意曝光，网络爬虫，误导点击，甚至是在用户完全无感知的情况下被控制访问等产生的不由用户主观发出的行为给数据带来了巨大的噪声，给模型训练造成了很大影响。

希望基于给定的数据，建立一个模型来识别和标记作弊流量，去除数据的噪声，从而更好的使用数据，使得广告主的利益最大化。

求职信息完善

有大约10万分优质简历，其中部分简历包含完整的字段，部分简历在学历、公司规模、薪水、职位名称等字段有些置空项。希望对数据进行学习、编码与测试，挖掘出职位路径的走向与规律，形成算法模型，再对数据中置空的信息进行预测。

搜索引擎查询聚类以进行流量推荐

在搜索引擎中，很多网民的查询意图的比较类似的，对这些查询进行聚类，一方面可以使用类内部的词进行关键词推荐；另一方面，如果聚类过程实现自动化，则也有助于新话题的发现；同时还有助于减少存储空间等。

生物种群固有结构认知

对动植物分类和对基因进行分类，获取对种群固有结构的认识。

保险投保者分组

通过一个高的平均消费来鉴定汽车保险单持有者的分组，同时根据住宅类型，价值，地理位置来鉴定一个城市的房产分组。

网络关键词来源聚类整合

以领域特征明显的词和短语作为聚类对象，在分类系统的大规模层级分类语料库中，利用文本分类的特征提取算法进行词语的领域聚类，通过控制词语频率的影响，分别获取领域通用词和领域专类词。

图像分割

图像分割广泛应用于医学、交通、军事等领域。图像分割就是把图像分成若干个特定的、具有独特性质的区域并提出感兴趣目标的技术和过程。它是由图像处理到图像分析的关键步骤。聚类算法先将图像空间中的像素用对应的特征空间点表示，根据它们在特征空间的聚集对特征空间进行分割，然后将它们映射回原图像空间，得到分割结果。