面向噪声抑制的聚类有效性指标确定最佳聚类个数的方法

摘要

本发明公开了一种面向噪声抑制的聚类有效性指标确定最佳聚类个数的方法，具体按照以下步骤实施：步骤1、确定待聚类的实际问题的聚类个数范围，这里的实际问题可以是当前大规模在线教育所产生的在线学习数据、网络购物所产生的大量商品交易数据以及智能交通所产生的大量交通信息等(但不限于此)，并获得k个初始聚类中心集合；步骤2、重新计算聚类后簇的质心，更新聚类中心集合，然后重新划分簇；步骤3、如果聚类中心不再发生变化，则代表聚类过程结束，根据面向噪声抑制的聚类有效性指标计算相似因子；步骤4、求得最佳聚类结果。本发明能够在噪声数据环境下更准确地进行聚类个数确定。

说明书

技术领域

本发明属于数据挖掘技术领域，具体涉及一种面向噪声抑制的聚类有效性指标确定最佳聚类个数的方法。

背景技术

数据挖掘在大数据分析中越来越流行，它能够满足人们对于深层次的信息的需求。聚类是数据挖掘中最热门的研究方向之一，它指的是将数据分组为多个簇的过程，以便使相同的簇中的数据尽可能相似，而不同簇的数据尽可能不同。作为一种传统的聚类算法，K-means算法由于其简单、快速、容易实现的特点以及它在处理数据信息量较大的问题时依然可以保持良好的伸缩性和高效性，因此被广泛的应用。虽然K-means算法原理比较简单，容易实现，但是传统的K-means算法存在聚类个数k的选择问题，这个需要先验知识的值的设定会对结果造成巨大的影响，但是由于在处理实际问题的过程中，往往是缺少足够的先验知识的，因此就需要用户寻找其他的方法帮助进行这个k的确定。因为缺少严格的数学准则，如何针对每个不同的问题选取一个与之对应的合适的k值引发了广泛的讨论。目前已经有许多专家和学者提出了检验聚类有效性的指标函数，比如Dunn指标、DB指标、CH指标等，他们使用这些指标函数去计算最佳聚类个数k

发明内容

本发明的目的是提供一种面向噪声抑制的聚类有效性指标确定最佳聚类个数的方法，能够在噪声数据环境下更准确地进行聚类个数确定。

本发明所采用的技术方案是，面向噪声抑制的聚类有效性指标确定最佳聚类个数的方法，具体按照以下步骤实施：

步骤1、确定待聚类的实际问题的聚类个数范围，这里的实际问题包括当前大规模在线教育所产生的在线学习数据、网络购物所产生的大量商品交易数据以及智能交通所产生的大量交通信息，并获得k个初始聚类中心集合；

步骤2、重新计算聚类后簇的质心，更新聚类中心集合，然后重新划分簇；

步骤3、如果聚类中心不再发生变化，则代表聚类过程结束，根据面向噪声抑制的聚类有效性指标计算相似因子；

步骤4、求得最佳聚类结果。

本发明的特点还在于，

步骤1具体按照以下步骤实施：

步骤1.1、对待聚类的实际问题形成的数据集X确定聚类个数的范围为k，

步骤1.2、以样本数据点x

步骤1.3、由所有的x

步骤1.4、重复步骤1.3，直到获得包含k个初始聚类中心的集合c。

步骤2具体按照以下步骤实施：

步骤2.1、将集合c中的k个初始聚类中心形成k个簇C

步骤2.2、重新计算聚类后的每个簇的质心，更新聚类中心集合c＝{c

步骤3具体按照以下步骤实施：

步骤3.1、如果聚类中心不再发生变化，则代表聚类过程结束，计算相似因子，即步骤3.2～步骤3.6，否则跳转至步骤2.1；

步骤3.2、对于聚类划分结果中的每个簇C

步骤3.3、计算数据集X的全局聚类中心g以及每个簇中距离全局聚类中心g的最短距离Dist_be(st

步骤3.4、计算簇间噪声距离抑制函数F(C

步骤3.5、已知每个簇C

步骤3.6、计算整个数据集的平均相似因子Ave_Sim，将平均相似因子Ave_Sim结果记录为F(k)，如果

所述步骤3.2中簇内相似因子Sim_in(C

其中，C

步骤3.3中全局聚类中心g具体计算如下：

n为数据点的个数，x

每个簇中距离全局聚类中心g的最短距离Dist_best(C

x

整个数据空间的平均距离Ave_distance计算如下：

x

步骤3.4中簇间噪声距离抑制函数F(C

簇内噪声距离抑制函数G(C

步骤3.5中：

簇C

步骤3.6中平均相似因子Ave_Sim具体计算如下：

步骤4具体如下：

将k＝2时的F(2)设为最小值minimum，循环将F(k)和minimum进行比较，如果minimum＞F(k)，则minimum＝F(k)，最终的minimum对应的k值记为最佳聚类个数k

本发明的有益效果是，一种面向噪声抑制的聚类有效性指标确定最佳聚类个数的方法，首先采用基于密度的初始聚类中心选择方法替代传统的随机选择初始聚类中心的方式，从而达到优化K-means算法聚类结果，提高聚类精度的目的。然后通过研究噪声环境下的数据内聚度和分离度两种因素对于簇的密集程度以及分离程度进行评价，提出一种新型的聚类有效性指标：相似因子，其中包括簇内相似因子、簇间相似因子、全局簇内相似因子、全局簇间相似因子和平均相似因子。并且引入噪声距离抑制函数来降低噪声数据点对于内部有效性指标评估结果的影响，从而使得本发明的方法实现对于噪声数据环境下最优聚类个数k

附图说明

图1(a)是CH指标在Iris数据集以及添加10个噪声数据的Iris数据集上的标准化值；

图1(b)是DB指标在Iris数据集以及添加10个噪声数据的Iris数据集上的标准化值；

图1(c)是VCN指标在Iris数据集以及添加10个噪声数据的Iris数据集上的标准化值；

图1(d)是Ave_Sim指标在Iris数据集以及添加10个噪声数据的Iris数据集上的标准化值。

图2(a)是CH指标在Wine数据集以及添加10个噪声数据的Wine数据集上的标准化值；

图2(b)是DB指标在Wine数据集以及添加10个噪声数据的Wine数据集上的标准化值；

图2(c)是VCN指标在Wine数据集以及添加10个噪声数据的Wine数据集上的标准化值；

图2(d)是Ave_Sim指标在Wine数据集以及添加10个噪声数据的Wine数据集上的标准化值。

图3(a)是CH指标在Haberman数据集以及添加10个噪声数据的Haberman数据集上的标准化值；

图3(b)是DB指标在Haberman数据集以及添加10个噪声数据的Haberman数据集上的标准化值；

图3(c)是VCN指标在Haberman数据集以及添加10个噪声数据的Haberman数据集上的标准化值；

图3(d)是Ave_Sim指标在Haberman数据集以及添加10个噪声数据的Haberman数据集上的标准化值。

图4(a)是CH指标在Heart数据集以及添加10个噪声数据的Heart数据集上的标准化值；

图4(b)是DB指标在Heart数据集以及添加10个噪声数据的Heart数据集上的标准化值；

图4(c)是VCN指标在Heart数据集以及添加10个噪声数据的Heart数据集上的标准化值；

图4(d)是Ave_Sim指标在Heart数据集以及添加10个噪声数据的Heart数据集上的标准化值。

图5(a)是CH指标在Banknote数据集以及添加5％和10％噪声数据的Banknote数据集上的标准化值；

图5(b)是DB指标在Banknote数据集以及添加5％和10％噪声数据的Banknote数据集上的标准化值；

图5(c)是VCN指标在Banknote数据集以及添加5％和10％噪声数据的Banknote数据集上的标准化值；

图5(d)是Ave_Sim指标在Banknote数据集以及添加5％和10％噪声数据的Banknote数据集上的标准化值。

具体实施方式

下面结合附图和具体实施方式对本发明进行详细说明。

本发明面向噪声抑制的聚类有效性指标确定最佳聚类个数的方法，具体按照以下步骤实施：

步骤1、确定待聚类的实际问题的聚类个数范围，这里的实际问题可以是当前大规模在线教育所产生的在线学习数据、网络购物所产生的大量商品交易数据以及智能交通所产生的大量交通信息等(但不限于此)，并获得k个初始聚类中心集合；

步骤1具体按照以下步骤实施：

步骤1.1、对待聚类的实际问题形成的数据集X确定聚类个数的范围为k，

步骤1.2、以样本数据点x

步骤1.3、由所有的x

步骤1.4、重复步骤1.3，直到获得包含k个初始聚类中心的集合c。

步骤2、重新计算聚类后簇的质心，更新聚类中心集合，然后重新划分簇；

步骤2具体按照以下步骤实施：

步骤2.1、将集合c中的k个初始聚类中心形成k个簇C

步骤2.2、重新计算聚类后的每个簇的质心，更新聚类中心集合c＝{c

步骤3、如果聚类中心不再发生变化，则代表聚类过程结束，根据面向噪声抑制的聚类有效性指标计算相似因子；

步骤3具体按照以下步骤实施：

步骤3.1、如果聚类中心不再发生变化，则代表聚类过程结束，计算相似因子，即步骤3.2～步骤3.6，否则跳转至步骤2.1；

步骤3.2、对于聚类划分结果中的每个簇C

步骤3.3、计算数据集X的全局聚类中心g以及每个簇中距离全局聚类中心g的最短距离Dist_best(C

步骤3.4、计算簇间噪声距离抑制函数F(C

步骤3.5、已知每个簇C

步骤3.6、计算整个数据集的平均相似因子Ave_Sim，将平均相似因子Ave_Sim结果记录为F(k)，如果

步骤3.2中簇内相似因子Sim_in(C

其中，C

步骤3.3中全局聚类中心g具体计算如下：

n为数据点的个数，x

每个簇中距离全局聚类中心g的最短距离Dist_best(C

x

整个数据空间的平均距离Ave_distance计算如下：

x

步骤3.4中簇间噪声距离抑制函数F(C

簇内噪声距离抑制函数G(C

步骤3.5中：

簇C

步骤3.6中平均相似因子Ave_Sim具体计算如下：

步骤4、求得最佳聚类结果。

步骤4具体如下：

将k＝2时的F(2)设为最小值minimum，循环将F(k)和minimum进行比较，如果minimum＞F(k)，则minimum＝F(k)，最终的minimum对应的k值记为最佳聚类个数k

为了验证本发明中提出的内部有效性指标相似因子来确定最优聚类个数k

实验评估所选择的数据集(Iris、Wine、Haberman、Heart、Banknote)均从UCI开放数据集存储库获得，实验采用数值型数据，五个数据集的基础信息如表1所示。

表1实验数据集具体描述信息

实验工作是对各数据集设置不同的聚类个数k并聚类划分，然后使用提出的内部有效性指标对聚类划分结果进行评估，同时将实验结果与传统的聚类有效性指标以及其他学者所提出的新型内部有效性指标CH指标、DB指标、VCN指标的运行结果进行对比实验。由于不同的聚类个数k对应的不同的指标值区间并不一定相同，因此对不同的指标值进行标准化，标准化的聚类有效性值

(1)添加固定噪声数据的实验

在实验结果图中将不同聚类有效性指标所计算出的最优聚类个数k

如图1(a)～图1(d)所示，对于未加噪声的Iris数据集，CH指标与本文提出的Ave_Sim指标都可以得到正确的聚类个数3。而DB指标和VCN指标得到的最佳聚类个数为2。而对于添加10个噪声的Iris数据集，CH指标得到的最佳聚类个数为4，DB指标和VCN指标得到的最佳聚类个数为2，Ave_Sim指标得到了最佳聚类个数3。

如图2所示，图2(a)～图2(d)对于Wine数据集不同的聚类有效性指标标准化值，对于未加噪声的Wine数据集，通过实验可以发现，只有本文提出的Ave_Sim指标可以得到正确的聚类个数3，DB指标以及VCN指标得到的最佳聚类个数为2，而CH指标得到的最佳聚类个数为6。而对于添加10个噪声的Wine数据集，CH指标和DB指标以及VCN指标得到的最佳聚类个数为2，本文所提出的Ave_Sim指标可以得到最佳聚类个数3。

如图3所示，图3(a)～图3(d)对于Haberman数据集不同的聚类有效性指标标准化值，由图3的实验结果可知，对于未加噪声的Haberman数据集，CH指标以及本文提出的Ave_Sim指标可以获得正确的聚类个数2，而DB指标以及VCN得到的最佳聚类个数是4。而对于添加10个噪声的Haberman数据集，DB指标与VCN指标得到的最佳聚类个数是4，CH指标和本文提出的Ave_Sim指标可以得到正确的最佳聚类个数2。

如图4所示，图4(a)～图4(d)对于Heart数据集不同的聚类有效性指标标准化值，由图4的实验结果可知，对于未加噪声的Heart数据集，四种指标均可以得到正确的聚类个数2。而对于添加10个噪声的Heart数据集，CH指标、DB指标与VCN指标得到的最佳聚类个数是3，只有本文提出的Ave_Sim指标可以得到最佳聚类个数2。

(2)添加固定噪声数据的实验：

在实验中，我们分别将满足高斯分布的5％和10％的随机噪声数据加入到Banknote数据集中，实验结果如图5所示。图5(a)～图5(d)对于Banknote数据集不同的聚类有效性指标标准化值，从图5可以看出，对于未加噪声的Banknote数据集和加入5％噪声数据的Banknote数据集，CH指标与本文提出的Ave_Sim指标可以得到正确的聚类个数，而对于加入10％噪声数据的Banknote数据集，CH指标得到的最佳聚类个数是4。所提出的Ave_Sim指标仍然能够得到正确的最佳聚类个数。对于Banknote数据集，DB与VCN指标表现不佳。在原始数据集和加入噪声的数据集中均不能得到最佳聚类个数。

经实验结果表明，本发明给出的聚类有效性指标“相似因子”无论在无噪声还是含有一定数量噪声的数据环境下，聚类有效性指标相似因子都可以得到正确的最佳聚类个数k

本文提通过抑制噪声数据在计算簇内聚度和分离度时的影响，从而得到正确的评价结果。实验说明在噪声环境下，本发明相似因子指标的表现优于其它广泛使用的内部有效性指标。