一种面向高维数据的集成聚类算法(2)

3.2 信息增益

对特点进行聚类后受到多个特征团，如何对他们进行特点选取，如何度量特征团中的特点的重要程度是我们遭遇的弊端。信息增益是信息论中的一个重要概念，它被广泛应用在机器学习、数据挖掘领域，计算信息增益是针对一个特征项而言的高维聚类分析，它借助统计某一个特征项t在类型C中发生与否的例子数来推导特征项t对类型C的信息增益，定义为[2]：

其中P(ci)表示ci类实例在数据集中发生的概率，p(t)表示数据集中包括特征项t的例子数，p(ci|t)表示实例包括特征项t时属于ci类的条件概率，p(t )表示数据集中不包括特征项t的例子数，p(c_i |t )表示实例不包括特征项t时属于ci类的概率，m为类型数。信息增益考虑特点与类型信息的相关程度，认为信息增益值越大，其贡献越大。我们的方式引入信息增益来度量特征簇中的特点的重要程度。

3.3 分层抽样（Stratified sampling）

在对特点进行聚类后对特征进行选取，我们采取信息增益来度量每个特点簇中的特性的重要程度。但是每个特点簇我们选用多少个特点非常适合，这是分层抽样解决的难题。抽样的目的是在不妨碍聚类效果的状况下在即将分好以及聚好类的示例中，从每位类中抽取部分的样本来替代整个类。Stratified sampling[18]方法依照的原则是：计算每个案例之间的相关性(用标准差、方差来评判)，我们觉得类中的例子相关性比较大的可以选用较小的样本来替代当前类，类中相关性较小的就多选用一些例子来替代当前类的样本。这个办法就是确定每个类中筛选的例子的数量。此步骤中每位类的样本数量为：

其中nh是第h类应该抽取的例子数。n是预计抽取的总样本数，Nh是在总体样本中第h类的例子数，h是第h类的标准差。通过(1)式我们就可以受到每个类中需要选用的例子数目。提出这中抽样方式的专家还对它的精确度、置信区间进行了探讨，证明了它在不妨碍学习效果的状况下对可以对数据降维，提高学习效率。

在本文的方式中，我们先用上面看到的k均值算法对特点进行加权，然后用信息增益来评判不同簇中的特点的重要程度，而每个特点簇中的所抽取特性的数量nh由下面stratified sampling的方式给与，最后运用信息增益选择top(nh)的特点。根据上述步骤对特点进行迭代，得到了最具代表的数据子集，进行后面的数据集的降维集成。

4、实验结果与预测

4.1 实验数据集

本文选用了8个数据集，包括文献[1]中的两个数据集：一个人工数据集Four-Gaussian[19]和一个被用来做基因数据降维的真实数据集Leukemia dataset[20],另外就是六个真实数据集包括两个文本数据集，两个图像数据集，两个基因数据。表1给出了很多数据集的名称或者数据的样本、属性、类别总量。

Table 1 Number of instance, features and classes of datasets

4.2 实验分析

实验中，本文对比了三种分类算法包含特色的k-means算法，文献[1]中的LB算法及其我们推动的算法SSLB。聚类性能通过以下四个评价指标来评判，表2给出了这四个评价指标[1]的详细描述：

Table 2 Name of measures, formulas

K为阈值结果中簇的数量，nk是属于第k个簇的数据点数目，d(xi,xj)是数据点xi和xj的距离，N是数据集中数据点的总量。n11是指在两个划分’(正确的界定)和*中发生在相同簇中的数据线对的个数，n00是指在两个划分’、*中中发生在不同簇中的数据点对的个数，n01表示在界定*中属于不同簇在另一个划分’ 中属于同一个簇的数据点对数目，n10表示在界定’中属于不同簇在另一个划分*中属于同一个簇的数据点对数目。

其中CP衡量的是在同一个簇中，所有数据点的数据点对的平均距离，越小越好。CA衡量的是与尚未的类标相比，聚类正确的数据点数目，CA的范围是从0到1，越大越好。RI这个指标评判存在于相似和不同簇中的点对数目，RI的值从0到1，越大越好，AR也是越大越好。

本文对这8个数据集进行加权集成，聚类成员由k均值对特点聚类然后分层抽样产生的局部特性子集获得，聚类中心的个数为数据集的类型数。为了提高试验的可靠性，所有的试验结果为10次结果的平均值。对比实验引入原始的K均值聚类算法、基于链接(LB)的方式，与我们推动的方式(SSLB)进行非常。在表3中，我们把关键值都突出的体现出来，在这8个数据集上，SSLB有在四个评价指标上都表现出比较大的优势。

根据表四，比较集成前的K均值算法、LB方法和SSLB方法，可以看出，在数据集Four-Gaussian上，SSLB在四种评价指标上都可以看出，其聚类性能显著优于集成前的K均值算法和LB聚类集成算法。在两种文本数据集Tr31和Tr41上，我们的方式优势不是很明显，但是在前两个指标CP和CA上而是明显好于集成前的K均值聚类，与LB算法在这两个指标上性能非常，而且在这两个文本数据上，在RI和AR上集成前的K均值算法与LB和SSLB方法相比都存在劣势。在两个图像数据集上，SSLB方法在CP这个评判指标上都远远好于集成前的K均值聚类算法和LB算法，但是在第二个评价指标和第三个评价指标上就比LB算法差一点。在基因数据Colon上SSLB再第一个聚类评价指标上一直存在巨大的劣势，在聚类的准确率上，我们的方式与LB方法比较，但是显著优于集成前的K均值算法。在基因数据TOX-171上，我们的方式取得了最好的聚类集成性能，在四个聚类评价指标上，都远远好于集成前的K均值算法和LB算法。

下面我们逐一在这四个聚类评价标准非常集成前的K均值算法、SSLB算法和LB算法。图四、图五、图六、以及图七分别描述了集成前的K均值聚类、LB以及我们的方式SSLB在CP、CA、RI、AR上的体现。

聚类评价指标CP衡量的是在同一个簇中，所有数据点的数据点对的平均距离，越小越好。通过图四可以看出，在所有数据集上，我们的算法SSLB都存在巨大的劣势，比集成前的K-means算法以及LB算法在CP这个指标上都好，此外还会看出CP在不同的数据集上的差别还是非常大的，在Four-Gaussian上显著比其它数据集上差。

聚类评价指标CA衡量的是与已知的类标相比，聚类正确的数据点数目占总的数据点数目的比例，CA的范围是从0到1，越大越好。从图五可以看出我们的算法在数据集Four-Gaussian、Tr41、Colon和TOX-171上的聚类精度比集成前的K均值算法及其LB算法都要好，但是在Tr31以及两个图像数据集上的劣势不大，这这个现象值得我们关注，也是我们接下来会研究的工作。

聚类评价指标RI衡量的是存在于相似和不同簇中的点对数目，RI的值从0到1，越大越好。从图六可以看出我们的算法在人工数据集Four-Gaussian以及几个基因数据集上的体现非常突显、但是在其它数据集上就进入弱势，而且可以看出集成前的K均值算法在所有的数据集在RI上的体现都比较好。

聚类评价指标AR衡量的只是存在于相似和不同簇中的点对数目，AR的值从0到1，越大越好。从图七可以看出我们的算法SSLB在大多数数据集上存在着劣势，但是在数据集Leukemia、Tr41、Colon上的达到了集成前的K均值算法和我们的算法。这些现象和结果都是我们接下来的研究的重点。

综上所述，在几乎所有数据集上，在所有的加权评价指标上我们的降维集成算法SSLB好于集成前K均值算法的聚类效果，而且在大多数数据集上，我们的算法比LB算法存在必定的劣势，尤其是在基因数据上的体现较为突出。但是在有的数据集上劣势也不够明显，我们要再次探讨这种数据结构上的特征和我们的算法可能存在的难题，这只是我们接下来研究的方向。

5 结 论

本文提出了一种面向高维数据的集成聚类方式。针对高维数据的特征，对传统的降维集成进行了一些优化，首先对特点聚类然后基于分层抽样抽取特性子集，抽取到最具代表性的特点子集后用基于链接的方式进行聚类集成。并在8个实际数据集包括文本、图像、基因数据上进行试验，在这8个数据集上探讨和非常了我们的方式和集成前的K均值算法及其基于链接的降维集成算法在四个评价标准上的聚类性能，能够看出我们的算法在阈值性能上有一定提升。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-126198-2.html