机器学习 Kmeans聚类算法

聚类分析将大量数据划分为性质相同的子类，便于了解数据的分布情况。因此，它广泛 应用于模式识别、图像处理、数据压缩等许多领域，例如：

等等，这里就不一一列举了。

#输入数据及要求# 在进行 K m e a n s Kmeans Kmeans聚类时，必须对数据进行预处理。

#算法原理# K m e a n s Kmeans Kmeans聚类也称快速聚类，属于覆盖型数值划分聚类算法。它得到的聚类结果，每 个样本点都唯一属于一个类，而且聚类变量为数值型，并采用划分原理进行聚类。

K m e a n s Kmeans Kmeans 聚类涉及两个主要方面的问题：

下面将重点讨论这些问题。

通常，“亲疏程度”的测度一般都有两个角度：第一，数据间的相似程度；第二，数据 间的差异程度。衡量相似程度一般可采用简单相关系数或等级相关系数等，差异程度则一般 通过某种距离来测度。 K m e a n s Kmeans Kmeans聚类方法采用的是第二个测度角度。

为有效测度数据之间的差异程度， K m e a n s Kmeans Kmeans聚类算法将所收集到具有 p p p个变量的样本 数据，看成 p p p维空间上的点，并以此定义某种距离。通常，点与点之间的距离越小，意味 着它们越“亲密”，差异程度越小，越有可能聚成一类；相反，点与点之间的距离越大，意 味着它们越“疏远”，差异程度越大，越有可能分属不同的类。

由于$Kmeans $聚类方法所处理的聚类变量均为数值型，因此，它将点与点之间的距离 定义为欧氏距离( E u c l i d e a n d i s t a n c e Euclidean distance Euclideandistance)，即数据点$x 与 与 与y 间 的 欧 氏 距 离 是 两 个 点 的 间的欧氏距离是两个点的 间的欧氏距离是两个点的p$个变量 之差的平方和的算术平方根，数学定义为 E u c l i d ( x , y ) = ∑ i = 1 p ( x i − y i ) p . Euclid(x,y)=\sqrt{\sum_{i=1}^{p}(x_{i}-y_{i})^p}. Euclid(x,y)=i=1∑p​(xi​−yi​)p ​. 除此之外，常用的距离还包括平方欧氏距离( S q u a r e d E u c l i d e a n d i s t a n c e Squared Euclidean distance SquaredEuclideandistance)、切比雪 夫( C h e b y c h e v Chebychev Chebychev)距离、 B l o c k Block Block距离、明考斯基( M i n k o w s k i Minkowski Minkowski)距离等。这里我们就不做 介绍了。

##改进后的“亲疏程度”的测度##

由于 K m e a n s Kmeans Kmeans聚类算法采用欧氏距离来表示样本间的“亲疏程度”，而欧式距离在计算 距离时采用的是循环的思想对样本的各个分量计算距离，因此在解决大数据集的聚类问题方 面存在效率低，占用内存大的缺陷。由于计算机的内存有限，无法存储超过内存容量的大数 据集。因此，尽管 K m e a n s Kmeans Kmeans聚类算法在理论上无懈可击，但却无法通过计算机实现。为此， 我们提出了一种巧妙的数据存储方案，即 C F CF CF树( C l u s t e r i n g F e a t u r e T r e e Clustering Feature Tree ClusteringFeatureTree)。

C F CF CF树是一种数据的压缩存储方式。树中每个节点只存储聚类过程计算距离所必须的汇 总统计量。

在 K m e a n s Kmeans Kmeans聚类算法中，关于树节点 i i i，即第 i i i类的汇总统计量包括 C F i = { N i , L S i → , S S i 2 } CF_{i}=\left \{N_{i},\overrightarrow{LS_{i}},SS_{i}^2 \right\} CFi​={Ni​,LSi​ ​,SSi2​},依次为节点所包含的样本量，数值型变量值的向量和，数值型变量值的平方和。可见，节点并没有存储原始数据本身，因而大大减少了存储的数据量，使得大数据集聚类具有实现的可能。

下面我们来推导用 C F CF CF树来存储的数据集的欧氏距离( E u c l i d e a n d i s t a n c e Euclidean distance Euclideandistance)。

对于任意两个 C F CF CF树，树一： { X i → ∣ X 1 → , X 2 → , . . . , X N 1 → } \left \{\overrightarrow{X_{i}} | \overrightarrow{X_{1}} , \overrightarrow{X_{2}} , ..., \overrightarrow{X_{N_{1}} } \right \} {Xi​ ​∣X1​ ​,X2​ ​,...,XN1​​ ​}；树二： { Y i → ∣ Y 1 → , Y 2 → , . . . , Y N 1 → } \left \{\overrightarrow{Y_{i}} | \overrightarrow{Y_{1}} , \overrightarrow{Y_{2}} , ..., \overrightarrow{Y_{N_{1}} } \right \} {Yi​ ​∣Y1​ ​,Y2​ ​,...,YN1​​ ​}，则两个树之间的距离： KaTeX parse error: No such environment: align* at position 8: \begin{̲a̲l̲i̲g̲n̲*̲}̲ D &= \sqrt{\df…

下面我们定义 C F CF CF树的存储结构： C F = { N , ∑ i = 1 N X i → , ∑ i = 1 N X i → 2 } = { N , L S → , S S } , CF=\left\{N, \sum_{i=1}^{N}\overrightarrow{X_{i}}, \sum_{i=1}^{N}\overrightarrow{X_{i}}^2 \right\}=\left\{N, \overrightarrow{LS}, SS \right\}, CF={N,i=1∑N​Xi​ ​,i=1∑N​Xi​ ​2}={N,LS ,SS}, 其中 N N N代表存储的样本个数， L S → \overrightarrow{LS} LS 代表数值型变量值的向量和， S S SS SS代表数值型变量值的平 方和。

假设现在有两个 C F CF CF树： C F 1 = { N 1 , X 1 → + X 2 → + . . . + X N 1 → , X 1 → 2 + X 2 → 2 + . . . + X N 1 → 2 } = { N 1 , L S 1 → , S S 1 } CF_{1}=\left\{N_{1}, \overrightarrow{X_{1}}+\overrightarrow{X_{2}}+...+\overrightarrow{X_{N_{1}}}, \overrightarrow{X_{1}}^2+\overrightarrow{X_{2}}^2+...+\overrightarrow{X_{N_{1}}}^2 \right\}=\left\{N_{1}, \overrightarrow{LS_{1}}, SS_{1} \right\} CF1​={N1​,X1​ ​+X2​ ​+...+XN1​​ ​,X1​ ​2+X2​ ​2+...+XN1​​ ​2}={N1​,LS1​ ​,SS1​}

C F 2 = { N 2 , Y 1 → + Y 2 → + . . . + Y N 2 → , Y 1 → 2 + Y 2 → 2 + . . . + Y N 2 → 2 } = { N 2 , L S 2 → , S S 2 } CF_{2}=\left\{N_{2}, \overrightarrow{Y_{1}}+\overrightarrow{Y_{2}}+...+\overrightarrow{Y_{N_{2}}}, \overrightarrow{Y_{1}}^2+\overrightarrow{Y_{2}}^2+...+\overrightarrow{Y_{N_{2}}}^2 \right\}=\left\{N_{2}, \overrightarrow{LS_{2}}, SS_{2} \right\} CF2​={N2​,Y1​ ​+Y2​ ​+...+YN2​​ ​,Y1​ ​2+Y2​ ​2+...+YN2​​ ​2}={N2​,LS2​ ​,SS2​} 根据上面的推导，我们可以得到两个树间的距离： D = S S 1 N 1 + S S 2 N 2 − 2 L S 1 → ⋅ L S 2 → N 1 ⋅ N 2 D = \sqrt {\frac{{S{S_1}}}{{{N_1}}} + \frac{{S{S_2}}}{{{N_2}}} - \frac{{2\overrightarrow {L{S_1}} \cdot \overrightarrow {L{S_2}} }}{{{N_1} \cdot {N_2}}}} D=N1​SS1​​+N2​SS2​​−N1​⋅N2​2LS1​ ​⋅LS2​ ​​ ​

每个树的中心为： X 0 → = ∑ i = 1 N X i → N = L S → N \overrightarrow {{X_0}} = \frac{{\sum\limits_{i = 1}^N {\overrightarrow {{X_i}} } }}{N} = \frac{{\overrightarrow {LS} }}{N} X0​ ​=Ni=1∑N​Xi​ ​​=NLS ​ 如果求两个点的欧氏距离，我们可以这样构造 C F CF CF树，$C{F_1} = { 1,\overrightarrow {{X_1}} ,{\overrightarrow {{X_1}} ^2}} = { 1,\overrightarrow {L{S_1}} ,S{S_1}} ， ， ，C{F_2} = { 1,\overrightarrow {{X_2}} ,{\overrightarrow {{X_2}} ^2}} = { 1,\overrightarrow {L{S_2}} ,S{S_2}} $，则 KaTeX parse error: No such environment: align* at position 8: \begin{̲a̲l̲i̲g̲n̲*̲}̲Euclid(x,y) &= … 这样，我们就可以只通过 C F CF CF树中的三个特征来求解两点之间的欧氏距离，这大大的减少了存储的数据量。

## K M e a n s KMeans KMeans聚类过程## 在上述距离的定义下， K M e a n s KMeans KMeans聚类算法采用“划分”方式实现聚类。

所谓划分是指，首先将样本空间随意划分为若干个区域(类)，然后依据上述定义的距离，将所有样本点分配到与之“亲近”的区域(类)中，形成初始的聚类结果。良好的聚类应使类内部的样本结构相似，类间的样本结构差异显著，而由于初始聚类结果是在空间随意划分的基础上产生的，因而无法确保所给出的聚类满足上述要求，所以多次反复是必须的。 在这样的设计思路下， K M e a n s KMeans KMeans聚类算法的具体过程如下。

聚类终止的条件通常有两个。第一，迭代次数。当前的迭代次数等于指定的迭代次数时终止聚类；第二，类中心点偏移程度。新确定的类中心点距上次类中心点的最大偏移量小于指定值时终止聚类。通过适当增加迭代次数或合理调整中心点偏移量的判定标准，能够有效克服初始类中心点指定时可能存在的偏差。上述两个条件中任意一个满足，则结束聚类。

可见， K M e a n s KMeans KMeans聚类是一个反复迭代过程。在聚类过程中，样本所属的类会不断调整，直到最终达到稳定为止。

下图直观反映了 K M e a n s KMeans KMeans 聚类的过程。

首先指定聚类中心，图中空心圆为类中心。可以看到，迭代过程中图中最下面的一个点的所属类发生了变化，其原因是类中心进行了调整。

由于距离是 K M e a n s KMeans KMeans 聚类的基础，它将直接影响最终的聚类结果。因此，通常在分析之前应剔除影响距离正确计算的因素。

第一、聚类变量值不应有数量级上的差异。聚类分析是以距离度量“亲疏”程度的，数量级将对距离计算产生较大影响。例如，下表是某银行三个贷款客户的数据。

直接计算两两样本点之间的欧氏距离和将贷款金额的计量单位转换成十万元后的欧氏距离，结果如下表所示。

由上表可知：当贷款以元为计量单位时，样本2和样本3的距离最小，其次是样本1和2，样本1和3的距离最远；当以十万元为计量单位时，样本1和2的距离最近，其次是样本1和3，样本2和样本3的距离最远。可见，数量级对距离产生了巨大影响，也直接影响了距离结果。

为解决该问题，聚类分析之前通常应首先消除变量的数量级差异，一般可通过标准化处理实现。

第二，对分类型变量的处理。由于 K M e a n s KMeans KMeans算法的距离计算是基于数值的，为符合计算要求需要对分类型聚类变量进行预处理。

对于具有 k k k个类别的多分类型变量，采用 k k k个取值为0或1的数值型变量(哑变量)共同来表示。例如，变量 x x x有 A , B , C A,B,C A,B,C 三个类别，则采用 x 1 , x 2 , x 3 x_{1}, x_{2}, x_{3} x1​,x2​,x3​ 三个变量共同表示。如果 x x x取 A A A，则 x 1 , x 2 , x 3 x_{1}, x_{2}, x_{3} x1​,x2​,x3​分别为 1 , 0 , 1 1, 0, 1 1,0,1；如果 x x x 取 B B B ，则 x 1 , x 2 , x 3 x_{1}, x_{2}, x_{3} x1​,x2​,x3​分别为 0 , 1 , 0 0, 1, 0 0,1,0；如果 x x x取 C C C，则 x 1 , x 2 , x 3 x_{1}, x_{2}, x_{3} x1​,x2​,x3​分别为 0 , 0 , 1 0, 0, 1 0,0,1。于是，原来具有 k k k个类别的一个聚类变量派生出取0或1的 k k k个变量。

由此引发的另外一个问题是，分类型变量在欧氏距离计算中的“贡献”将大于其他数值型变量。

例如，计算样本点 x x x与样本点 y y y的欧氏距离时，如果样本点 x x x在一个 3 3 3分类型变量上取 A A A，样本点 y y y取 B B B，则该分类型变量在欧氏距离中的“贡献”为： ( 1 − 0 ) 2 + ( 0 − 1 ) 2 + ( 0 − 0 ) 2 = 2 {(1 - 0)^2} + {(0 - 1)^2} + {(0 - 0)^2} = 2 (1−0)2+(0−1)2+(0−0)2=2，大于1 。而数值型变量由于取值在0至1之间，贡献不可能大于1。这就意味着分类型变量的权重要高于数值型变量，显然是有问题的。

为此，解决的策略是：将1调整为 0.5 \sqrt{0.5} 0.5 ​，即 ( 0.5 − 0 ) 2 + ( 0 − 0.5 ) 2 + ( 0 − 0 ) 2 = 1 {(\sqrt{0.5} - 0)^2} + {(0 - \sqrt{0.5})^2} + {(0 - 0)^2} = 1 (0.5 ​−0)2+(0−0.5 ​)2+(0−0)2=1，以保证分类型变量在欧氏距离中的“贡献”不大于1。

对于二分类型变量，用取值为0或1的一个数值型变量替代。

#算法流程#