K均值聚类分析
K K K均值算法，是一种最古老的，也是最广泛使用的聚类算法。
通常， K K K均值聚类应用于 n n n维连续空间中的对象。从数学的角度讲，假定样本集（数据集） D D D包含 m m m个样本（对象），每个样本均为 n n n维向量，则 K K K均值聚类将样本集 D D D划分为 k k k个互不相交的簇（ c l u s t e r cluster cluster）。
例如，研究电信用户留存时，想知道哪些客户群容易流失，可以使用 K K K均值聚类对用户群体进行划分。
一、基本K均值算法
1、算法的过程
首先，选择 k k k个对象作为初始的质心，其中 k k k是预先指定的参数，即所期望的 c l u s t e r cluster cluster的个数。初始质心的选取通常是随机的，当然这么做的聚类效果往往很一般。
其次，选取一个对象，计算对象到各个质心的距离，把对象分配给距离最近的质心。质心以及分配给其的对象就组成一个 c l u s t e r cluster cluster。
然后，根据现有的 c l u s t e r cluster cluster，计算 c l u s t e r cluster cluster的质心—— c l u s t e r cluster cluster内对象的平均值，并更新cluster的质心。
接着，不断的循环执行对象分配以及质点更新的步骤。
最后，当 c l u s t e r cluster cluster不再发生变化，或者等价地， c l u s t e r cluster cluster的质心不再发生变化时，终止循环，结束过程。
选择K个点作为初始质心; repeat 将每个点指派到最近的质心，形成K个cluster; 重新计算每个cluster的质心; until 质心不发生变化; 2、质心的计算
假设数据集包含 n n n个对象，每个对象对应一个 2 2 2维的线性空间，( x c , y c x_{c},y_{c} xc,yc)为质心的坐标：
x c = 1 n ∑ i = 1 n x i x_{c}=\frac{1}{n}\sum_{i=1}^{n}x_{i} xc=n1i=1∑nxi y c = 1 n ∑ i = 1 n y i y_{c}=\frac{1}{n}\sum_{i=1}^{n}y_{i} yc=n1i=1∑nyi
对于高维的数据样本，可依次进行推广。
3、距离的度量
由于 K K K均值算法往往应用于 n n n维连续空间中的对象，因此在计算对象到质心的距离时，该距离的定义方式应符合度量空间的定义——正定性、对称性、三角不等式。 n n n维度量空间中，常见的距离的度量方式有：
①曼哈顿距离
d ( x , y ) = ∑ i = 1 n ∣ x i − y i ∣ d\left ( x,y \right)=\sum_{i=1}^{n}\left | x_{i}-y_{i} \right | d(x,y)=i=1∑n∣xi−yi∣
②欧几里得距离
d ( x , y ) = ∑ i = 1 n ( x i − y i ) 2 d\left ( x,y \right )=\sqrt{\sum_{i=1}^{n}{(x_{i}- y_{i})^2}} d(x,y)=i=1∑n(xi−yi)2
③闵可夫斯基距离
d ( x , y ) = ∑ i = 1 n ∣ x i − y i ∣ p p d\left ( x,y \right)=\sqrt[p]{\sum_{i=1}^{n}\left | x_{i}-y_{i} \right |^{p}} d(x,y)=pi=1∑n∣xi−yi∣p
其中， p = 1 p=1 p=1时，即曼哈顿距离； p = 2 p=2 p=2时，即欧几里得距离。
4、性能的评估
对于聚类的结果，我们希望尽可能的“物以类聚”。即同一 c l u s t e r cluster cluster内的样本尽可能彼此相似（相关性强），隶属不同 c l u s t e r cluster cluster的样本尽可能不同（不相关）。换言之，聚类结果的簇内相似度高，且簇间相似度低。
①偏差平方和
最常见的，可以使用偏差平方和 S S E SSE SSE（Sum of the Squared Error），即每个数据点到其最近质心的欧几里得距离平方和，来进行衡量：
S S E = ∑ i = 1 k ∑ x ϵ C i d i s c ( c i , x ) 2 SSE=\sum_{i=1}^{k}\sum_{x\epsilon C_{i}}^{}disc\left ( c_{i},x \right )^2 SSE=i=1∑kxϵCi∑disc(ci,x)2
其中， C i C_{i} Ci代表 k k k个 c l u s t e r cluster cluster； c i c_{i} ci代表 c l u s t e r cluster cluster的质心； x x x代表数据集中的数据点； d i s c disc disc代表两点间的欧几里得距离。
显然， S S E SSE SSE越小，簇内相似度越高，聚类效果越好。
②轮廓系数
另一个常见的度量方式是轮廓系数，不同于 S S E SSE SSE只衡量了簇内相似度，轮廓系数通过 c l u s t e r cluster cluster内的聚合度和不同 c l u s t e r cluster cluster间的离散度的比值来衡量：
离 散 度 聚 合 度 \frac{离散度}{聚合度} 聚合度离散度
二、二分K均值算法
二分 K K K均值算法是基本 K K K均值算法的直接扩充，其思想是：为了得到 K K K个 c l u s t e r cluster cluster，将所有点的集合分裂成两个 c l u s t e r cluster cluster，从这些 c l u s t e r cluster cluster中选取一个继续分裂，如此下去，直到产生 K K K个 c l u s t e r cluster cluster。
初始化数据，将所有数据作为一个cluster; repeat 选取一个cluster; for i=1 to 实验次数; 使用基本K均值，令k=2，二分选定的cluster; end for 根据选取的不同的初始cluster，计算二分后的SSE; 将使SSE最小的cluster二分后的结果，加入到总的cluster集中; until 数据集分为k个cluster; 三、K均值的优点和缺点
1、K均值的优点
K K K均值算法简单，且可用于各种数据类型。
K K K均值算法往往相当有效，甚至有些变种算法（包括二分 K K K均值）更加有效，并且不太受初始化问题的影响。
2、K均值的缺点
K K K均值算法并不适合所有的数据类型。
K K K均值算法不能处理非球形 c l u s t e r cluster cluster、不同尺寸和不同密度的 c l u s t e r cluster cluster，尽管指定足够大的 K K K值时它通常可以发现纯子 c l u s t e r cluster cluster。
对包含离群点的数据进行聚类时， K K K均值也有问题。这种情况下，离群点检测和删除大有帮助。
K K K均值算法只限于有质心概念的数据，对于没有质心概念的数据，可以使用 K K K中心点聚类，但是开销更大。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/223850.html原文链接：https://javaforall.net
