一种基于优化ReliefF特征选择机制的融合聚类方法

技术领域

本发明涉及数据聚类分析技术领域，尤其是涉及一种基于优化ReliefF特征选择机制的融合聚类方法。

背景技术

随着信息时代的高速发展，如何从海量数据中发掘有效特征，实现准确聚类变得十分重要。聚类分析是对海量数据高效利用的有效途径，但聚类方法的性能主要依赖于对数据特征的准确挖掘、精细度量与优化选择。目前最具有代表性的k-modes聚类方法是k-means聚类方法的扩展与提升。然而，该方法由于存在对数据中所包含特征挖掘不够准确、度量不够精细、特征选取有待优化等不足，在实际应用中效果不佳。

目前，不仅需要对日益增长的数据进行处理，还要面临数据高维度的难题。因此，若想通过聚类算法针对现如今数据进行精准分析计算，不仅要考虑数据属性之间的关系，还须将数据降维加入其中。特征选择算法可以很好地解决数据降维的问题，该算法的思想是：从初始数据集的所有特征中，根据分类类别筛选出具有最大相关性的特征子集。这对于处理多特征、高维度数据集是有助力的。过滤式特征选择算法在1974年由Cover人首次提出。20世纪90年代，Kira和Rendell等人提出了Relief算法，目前使用广泛。该算法基于二分类问题提出，主要思想是通过统计特征对于分类类别的贡献率进行权值赋予，然后根据权值的高低进行特征子集的筛选。虽然该方法计算简单高效，但由于只能处理二分类问题，具有一定的局限性。1994年，Kononenko在Relief算法的基础上延伸出了ReliefF算法，该算法扩展了原来的Relief算法，使其可以解决多分类问题。但是Relief系列算法由于选择特征子集过程中只涉及到权值大小排序，故大部分存在着冗余特征的问题。

发明内容

本发明的目的是提供一种基于优化ReliefF特征选择机制的融合聚类方法，解决现有的选择算法难以去除冗余特征造成聚类耗时长、精度低的问题。

为实现上述目的，本发明提供了一种基于优化ReliefF特征选择机制的融合聚类方法，包括以下步骤：

S1、给定数据集D和聚类数k，D＝{x

权值更新公式为：

其中，R表示迭代计算特征权重R次，R＞1；K指NHit和NMiss集合中的K个样本点，NH

S2、对初始数据集D＝{x

S3、选取合适的阈值δ

S4、对特征子集D′＝{x′

S5、将步骤4中得到的特征子集D″＝{x″

定义对象x″

其中x″

其中，x″

给出样本x″

S6、任意给出D″的k个非空子集D″

S7、计算当前k个非空子集D″

S8、对每一个样本x″

S9、返回到步骤S7，直到每个样本所属的类不再改变。

优选的，所述步骤S4中，基于Renyi熵计算互信息的公式如下：

其中，

上式中，m表示为数据集的特征数量。

优选的，所述步骤S5中，最大信息系数MIC(A

其中x,y是在x轴y轴方向上的划分格子的个数，B(n)是n的变量，I(A

本发明所述的一种基于优化ReliefF特征选择机制的融合聚类方法的优点和积极效果是：

1、本发明在ReliefF特征选择中加入优化的Renyi熵互信息度量，建立剔除特征子集中冗余信息的特征筛选方法，有效地解决了ReliefF算法无法去除冗余特征的问题，优化筛选出的特征子集，克服了ReliefF算法的不足。

2、本发明针对互信息概率密度难求的问题，本发明在步骤S4中提出引入势函数和高斯函数计算数据中数据样本和来代替对概率密度函数的计算。

3、本发明以获取的优化特征子集为输入，结合引入MIC改进后的k-modes方法，定义了一种新的距离度量。在计算样本之间距离时，通过函数f(x″

下面通过附图和实施例，对本发明的技术方案做进一步的详细描述。

附图说明

图1为本发明一种基于优化ReliefF特征选择机制的融合聚类方法实施例的流程图；

图2为MIC-kmodes、R-MIC-kmodes、RI-MIC-kmodes以及本发明RIR-MIC-kmodes四种方法的AC值在vote、cancer、musk、mushroom数据集上的分布情况；

图3为MIC-kmodes、R-MIC-kmodes、RI-MIC-kmodes以及本发明RIR-MIC-kmodes四种方法的PE值在vote、cancer、musk、mushroom数据集上的分布情况；

图4为MIC-kmodes、R-MIC-kmodes、RI-MIC-kmodes以及本发明RIR-MIC-kmodes四种方法的RE值在vote、cancer、musk、mushroom数据集上的分布情况；

图5为MIC-kmodes、R-MIC-kmodes、RI-MIC-kmodes以及本发明RIR-MIC-kmodes四种方法的Time在vote、cancer、musk、mushroom数据集上的分布情况。

具体实施方式

以下通过附图和实施例对本发明的技术方案作进一步说明。

实施例

图1为本发明一种基于优化ReliefF特征选择机制的融合聚类方法实施例的流程图。如图所示，一种基于优化ReliefF特征选择机制的融合聚类方法，包括以下步骤：

S1、给定数据集D和聚类数k，D＝{x

权值更新公式为：

其中，R表示迭代计算特征权重R次，R＞1；K指NHit和NMiss集合中的K个样本点，NH

S2、对初始数据集D＝{x

S3、选取合适的阈值δ

S4、对特征子集D′＝{x′

基于Renyi熵计算互信息的公式如下：

其中，

上式中，m表示为数据集的特征数量。

S5、将步骤4中得到的特征子集D″＝{x″

定义对象x″

其中x″

最大信息系数MIC(A

其中x,y是在x轴y轴方向上的划分格子的个数，B(n)是n的变量，I(A

函数f(x″

其中，x″

给出样本x″

S6、任意给出D″的k个非空子集D″

S7、计算当前k个非空子集D″

S8、对每一个样本x″

S9、返回到步骤S7，直到每个样本所属的类不再改变。

为了证明本发明的优势，从UCI数据集中挑选了4组对象数据，具体的数据描述见表1所示，通过对该4组数据的聚类仿真，本发明所述的聚类方法RIR-MIC-kmodes(RenyiInformation ReliefF Maximal Information Coefficient kmodes)与MIC-kmodes方法，使用传统ReliefF特征选择算法融合的MIC-kmodes聚类方法(R-MIC-kmodes)以及使用ReliefF与传统互信息组合的特征选择算法融合的MIC-kmodes聚类方法(IR-MIC-kmodes)进行仿真测试比较。

表1：数据集描述

为了验证RIR-MIC-kmodes聚类方法的效果，本发明使用分类正确率(Accuracy,AC)、分类精度(Precision,PE)、召回率(Recall,RE)、执行时间(Time)四个指标对仿真结果进行评定。AC、PE、RE的公式为：

上式中，n指的是数据中所包含的第i类样本总数，a

AC计算的是准确分类的样本数占总样本数的比例。PE计算的是每类中正确分类样本数与错误分类样本数之间的比例，计算k类总和后求均值。RE计算的是每类中正确分类样本数与本属于该类却没分到的样本数之间的比例，同样统计k类总和后求均值。执行时间(Time)定义为从初始数据集到得到最终聚类结果的算法耗时。因此，评判标准为：AC值、PE值、RE值越大，Time值越小代表算法聚类效果越好。

分别运用MIC-kmodes、R-MIC-kmodes、RI-MIC-kmodes以及本发明RIR-MIC-kmodes四种方法对表1中的数据集进行聚类分析，由于方法受初始类中心选取影响很大，即当选择不同的初始类中心时，即使是相同的聚类方法也可能会得到不同的最终聚类结果。因此为了验证方法有效性，对每种方法随机选取100次初始类中心，并在相同的初始聚类中心下分别运行以上四种方法，通过取100次的平均聚类结果的AC、PE、RE、Time值来验证改进后方法的有效性。

图2为MIC-kmodes、R-MIC-kmodes、RI-MIC-kmodes以及本发明RIR-MIC-kmodes四种方法的AC值在vote、cancer、musk、mushroom数据集上的分布情况，图3为MIC-kmodes、R-MIC-kmodes、RI-MIC-kmodes以及本发明RIR-MIC-kmodes四种方法的PE值在vote、cancer、musk、mushroom数据集上的分布情况，图4为MIC-kmodes、R-MIC-kmodes、RI-MIC-kmodes以及本发明RIR-MIC-kmodes四种方法的RE值在vote、cancer、musk、mushroom数据集上的分布情况，图5为MIC-kmodes、R-MIC-kmodes、RI-MIC-kmodes以及本发明RIR-MIC-kmodes四种方法的Time在vote、cancer、musk、mushroom数据集上的分布情况。为了更加清晰地分析聚类方法的有效性，算出vote、cancer、musk、mushroom数据集下100次聚类结果的平均数，如表2、表3、表4和表5所示。

表2：4种方法在vote数据集下的聚类结果

表3：4种方法在cancer数据集下的聚类结果

表4：4种方法在musk数据集下的聚类结果

表5：4种方法在mushroom数据集下的聚类结果

通过分析观察图2可以看出，在UCI数据集上，本发明提出的RIR-MIC-kmodes聚类方法的仿真结果在AC、PE、RE以及Time四个评判标准下的值均在MIC-kmodes聚类方法之上，且优于R-MIC-kmodes方法以及IR-MIC-kmodes方法，尤其在musk数据集上表现明显。具体地，根据表2、表3、表4、表5，可以看出RIR-MIC-kmodes聚类方法的算法耗时用时最短，在musk数据集上该方法耗时相比于MIC-kmodes方法降低了606.79s。

另外，IR-MIC-kmodes方法相比于R-MIC-kmodes方法的算法耗时有所增加，而在RIR-MIC-kmodes方法上又下降了，这是因为IR-MIC-kmodes方法增加了互信息计算导致算法复杂度增加、速度变慢，而本发明的RIR-MIC-kmodes方法使用优化的特征选择算法筛选出强特征子集，改善了聚类速度。对比4个数据集的仿真效果，可以发现随着数据集样本的增加，尤其是数据特征的数量增加，本发明在去冗余特征与缩短计算时间方面的优势更为突出，相较于之前拥有更高的聚类精度、更短的耗时以及更高的召回率。

因此，本发明采用上述基于优化ReliefF特征选择机制的融合聚类方法，能够解决现有的选择算法难以去除冗余特征造成聚类耗时长、精度低的问题。

最后应说明的是：以上实施例仅用以说明本发明的技术方案而非对其进行限制，尽管参照较佳实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对本发明的技术方案进行修改或者等同替换，而这些修改或者等同替换亦不能使修改后的技术方案脱离本发明技术方案的精神和范围。