CN104376057A - 一种基于最大最小距离和K-means的自适应聚类方法 - Google Patents

Abstract

本发明公开了一种基于最大最小距离和K-means的自适应聚类方法，该方法解决了传统K-means聚类算法存在的对初始中心敏感，以及簇个数需事先确定的问题。本发明是一种策略性方法。本发明对初始中心以及新增簇的初始中心的选择都不是随机的，而是经过计算得到的，以数据(子)集中分别与相距最大的两个点相距最小的两个点作为初始中心，能够有效地避免选取到孤立点作为初始中心，同时能有效地减少聚类过程的迭代次数，并得到较好的聚类结果；本发明针对各簇SSE(误差平方和)情况和总的SSE变化趋势决定是否增加簇以及是否结束聚类，从而能自适应确定簇数，特别适合那些簇数难以确定的应用场景。

Description

一种基于最大最小距离和K-means的自适应聚类方法

技术领域

本发明涉及一种基于最大最小距离和K-means聚类算法的自适应聚类方法，属于数据挖掘技术领域。

背景技术

聚类分析将数据划分成有意义或有用的组(簇)，其目标为：组内的对象相互之间是相似的，而不同组中的对象是不同的。组内的相似性越大，组间差别越大，聚类就越好。在某种意义下，聚类分析只是解决其他问题的起点。在信息检索方面，万维网包含数以亿计的Web页面，网络搜索引擎可能返回数以千计的页面。可以使用聚类将搜索结果分成若干簇，每个簇捕获查询的某个特定方面，每个类别(簇)又可以划分成若干子类别(子簇)，从而产生一个层次结构，帮助用户进一步探索查询结果。在气候方面，聚类分析已经用来发现对陆地气候具有显著影响的极地和海洋大气压力模式。在心里学和医学方面，聚类已经用来识别不同类型的抑郁症，同时聚类分析也可以用来检测疾病的时间和空间分布模式。因此无论是旨在理解还是实用，聚类分析在诸多领域都扮演着重要的角色，这些领域包括：统计学、模式识别、信息检索、机器学习和数据挖掘。

国际权威学术会议IEEE International Conference on Data Mining(ICDM)2006年12月评选出了数据挖掘领域的十大经典算法，K-means聚类算法是其中之一。K-means算法比较简单，首先，选择K个初始中心，其中K是用户指定的参数，即所期望的簇的个数。将每个点划分到最近的中心，而划分到一个中心的点集为一个簇。然后，计算各簇的质心，将其作为各簇的中心。重复划分点和更新簇中心步骤，直到簇不再发生变化，或者等价地，直到中心不发生变化。然而，随机地选择K-means聚类算法初始中心，不仅会使聚类陷入局部最优解，而且可能得不到最优的聚类结果。选择合适的初始中心，不仅可以减少聚类过程的迭代次数，而且可以提高聚类的效果，而且随机选取初始中心可能会选取到孤立点作为初始中心，导致迭代次数过多，抑或得到不合理的聚类结果。K-means聚类算法不仅对初始中心敏感，同时簇个数的选择也是影响聚类结果的重要因素。而本发明能够较好地解决上面的问题。

发明内容

本发明目的在于提供一种基于最大最小距离和K-means聚类算法的自适应聚类方法，该方法解决了传统K-means聚类算法存在的对初始中心敏感，以及簇个数需事先确定的问题。该方法能有效地避免选取到孤立点作为初始中心，同时能有效地减少聚类过程的迭代次数，并且能得到较好的聚类结果。

本发明解决其技术问题所采用的技术方案是：本发明是一种策略性方法。K-means是基于原型的、划分的聚类技术，以其简单的算法、较快的聚类速度和稳定的聚类结果得到了广泛应用，然而基本K-means算法还存在一些问题，比如K-means难处理非球形的簇和不同大小的簇，并且受噪声和离群点的影响。同时聚类结果也很受聚类中心个数和初始中心选择的影响。

本发明针对K-means聚类算法的缺点提出了一个基于最大最小距离和K-means算法，以数据集总的SSE(Sum of Square Error，误差平方和)出现拐点作为聚类结束条件的自适应聚类方法。该方法对初始中心的选择不是随机的，而是经过计算得到的，可以较有效地避免选取到孤立点作为初始中心，同时能有效地减少聚类过程的迭代次数，并得到较好的聚类结果；此外针对各簇SSE情况和总的SSE变化趋势决定是否增加簇以及是否结束聚类，从而能自适应确定簇数，特别适合那些簇数难以确定的应用场景。

传统K-means聚类算法是将n个数据点划分到K个簇中，使每个数据点到其簇中心的距离之和最小，算法处理过程：

(1)随机选择K个数据点作为初始中心

(2)将每个数据点划分到最近的中心，形成K个簇

(3)计算每个簇的质心，将其作为簇的中心

(4)重复步骤(2)和(3)直到中心不再发生变化

本发明中使用如下的定义和计算公式：

(1)数据点之间的相似程度可以通过计算两两数据之间的距离来确定，欧氏距离是最为人所知的距离测度，在n维欧式空间中，每个点都是n维实数向量，空间中x和y两点之间的欧几里得距离定义为：

$d(x,y)=\sqrt{\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{(x_i-y_i)}^2}---\left(1\right)$

(2)聚类目标函数用来度量聚类质量，本发明使用误差平方和作为度量聚类质量的目标函数，数据集总的误差平方和SSE定义为：

$\mathrm{SSE}=\underset{i=1}{\overset{K}{\mathrm{\Σ}}}\underset{x\∈S_i}{\mathrm{\Σ}}{\left(d(c_i,x)\right)}^2---\left(2\right)$

其中c_i是第i个簇S_i的中心。

方法流程：

本发明提出一种基于最大最小距离和K-means聚类算法的自适应聚类方法，该方法对数据集S＝{x₁,x₂,...,x_n}的聚类包括如下步骤：

步骤1：计算数据集S中任意两个数据点之间的欧几里得距离；

步骤2：找到数据集S中相距最远的两个点x_i和x_j，再找到距离x_i最近的点x_p和距离x_j最近的点x_q；

步骤3：将x_p和x_q作为初始聚类(簇)中心，此时聚类(簇)中心集合C⁽⁰⁾＝{x_p,x_q}，另设t＝1，SSE⁽⁰⁾＝∞；

步骤4：采用K-means聚类算法，划分数据集S、更新各个簇中心，得到新的簇中心集合C^(t)和|C^(t)|个簇，此时

步骤5：分别计算各个簇中各点到簇中心的距离平方和k＝1,2,…,|C^(t)|，并累加得到总的误差平方和SSE^{t}，如果其中δ为阈值，转步骤9；否则继续；

步骤6：选择最大的簇，记为S_max，其中心记为c_max，去除C^(t)中该簇的聚类中心，即令C^(t)＝C^(t)-{c_max}；

步骤7：找到数据子集S_max中相距最远的两个点x_i和x_j，再找到距离x_i最近的点x_p和距离x_j最近的点x_q；

步骤8：将x_p和x_q并入C^(t)，即令C^(t)＝C^(t)∪{x_p,x_q}，再令t＝t+1，转步骤4；

步骤9：取上一次聚类结果为最终聚类结果，即最终的聚类中心集C＝C^(t-1)。

本发明的步骤2、步骤3首先找到数据集S中相距最远的两个点x_i和x_j，避免了K-means算法初始中心选取时有可能过于邻近的问题；再找到距离x_i最近的点x_p和距离x_j最近的点x_q，选取相距最远两个点的最近邻点是为了避免相距最远两个点是孤立点；并以这两个最远最近点x_p和x_q为初始中心，进行第一次K-means聚类。步骤5、步骤6针对各簇SSE情况和总的SSE变化趋势决定是否增加簇以及是否结束聚类，从而能自适应确定簇数，特别适合那些簇数难以确定的应用场景。步骤6～8分裂簇并采用本发明特有的最大最小距离方法为新簇选择初始中心。

有益效果：

1、本发明对初始中心以及新增簇的初始中心的选择都不是随机的，而是经过计算得到的，能够有效地避免选取到孤立点作为初始中心，同时能够有效地减少聚类过程的迭代次数，并且能够得到较好的聚类结果。

2、本发明针对各簇SSE情况和总的SSE变化趋势决定是否增加簇以及是否结束聚类，从而能自适应确定簇数，特别适合那些簇数难以确定的应用场景。

3、本发明应用于数据挖掘技术领域。

附图说明

图1为本发明的方法流程图。

具体实施方式

以下结合说明书附图对本发明创造作进一步的详细说明。

为了方便描述，下面举一个例子进行简要说明：

已知数据集：x₁＝(0，0)，x₂＝(1，1)，x₃＝(2，2)，x₄＝(4，4)，x₅＝(5，5)，x₆＝(2，1)，x₇＝(5，4)，x₈＝(3，6)，x₉＝(7，4)，x₁₀＝(8，5)，阈值σ＝0.3

如图1所示，本发明提供一种基于最大最小距离和K-means的自适应聚类方法，该方法包括如下步骤：

(1)根据上述公式(1)，算出数据集中两两数据之间的距离，选择最远的两个点，对于已知数据集可知点x₁＝(0，0)和点x₁₀＝(8，5)是距离最远的两个点；

(2)同时点x₂＝(1，1)是x₁＝(0，0)距离最小的点，点x₉＝(7，4)是x₁₀＝(8，5)距离最小的点；

(3)令初始中心点c₁和c₂分别存储最大最小距离点x₂＝(1，1)和点x₉＝(7，4)

(4)将初始中心点c₁和c₂代入K-means聚类算法，得到两个簇S₁和S₂，S₁＝{x₁,x₂,x₃,x₆}和S₂＝{x₄,x₅,x₇,x₈,x₉,x₁₀}，计算SSE₁、SSE₂、SSE⁽¹⁾＝SSE₁+SSE₂；

(5)因SSE₁/|S₁|<SSE₂/|S₂|，将簇S₂中的数据看成新的数据集，计算此时最大最小距离点为x₅＝(5，5)和x₉＝(7，4)并用c₂₁和c₂₂存储；

(6)新的初始中心C＝{c₁,c₂₁,c₂₂}并代入K-means聚类算法，得到3个簇S₂₁、S₂₂和S₂₃，S₂₁＝{x₁,x₂,x₃,x₆}，S₂₂＝{x₄,x₅,x₇,x₈}，S₂₃＝{x₉,x₁₀}，计算SSE₂₁、SSE₂₂、SSE₂₃、SSE⁽²⁾＝SSE₂₁+SSE₂₂+SSE₂₃，因聚类结束。

Claims (3)

1.一种基于最大最小距离和K-means聚类算法的自适应聚类方法，其特征在于，所述方法对数据集S＝{x₁,x₂,...,x_n}的聚类包括如下步骤：

步骤1：计算数据集S中任意两个数据点之间的欧几里得距离；

步骤2：找到数据集S中相距最远的两个点x_i和x_j，再找到距离x_i最近的点x_p和距离x_j最近的点x_q；

步骤3：将x_p和x_q作为初始聚类(簇)中心，此时聚类(簇)中心集合C⁽⁰⁾＝{x_p,x_q}，另设t＝1，SSE⁽⁰⁾＝∞；

步骤4：采用K-means聚类算法，划分数据集S、更新各个簇中心，得到新的簇中心集合C^(t)和|C^(t)|个簇，此时

步骤5：分别计算各个簇中各点到簇中心的距离平方和并累加得到总的误差平方和SSE^{t}，如果其中δ为阈值，转步骤9；否则继续；

步骤6：选择最大的簇，记为S_max，其中心记为c_max，去除C^(t)中该簇的聚类中心，即令C^(t)＝C^(t)-{c_max}；

步骤7：找到数据子集S_max中相距最远的两个点x_i和x_j，再找到距离x_i最近的点x_p和距离x_j最近的点x_q；

步骤8：将x_p和x_q并入C^(t)，即令C^(t)＝C^(t)∪{x_p,x_q}，再令t＝t+1，转步骤4；

步骤9：取上一次聚类结果为最终聚类结果，即最终的聚类中心集C＝C^(t-1)。

2.根据权利要求1所述的一种基于最大最小距离和K-means聚类算法的自适应聚类方法，其特征在于：所述方法对初始中心以及新增簇的初始中心的选择都不是随机的，而是经过计算得到的。

3.根据权利要求1所述的一种基于最大最小距离和K-means聚类算法的自适应聚类方法，其特征在于：所述方法应用于数据挖掘技术领域。