基于特征词袋的双聚类算法研究

第第页基于特征词袋的双聚类算法研究摘要：传统聚类方法分析数据时，仅仅从单一角度进行分析，无法利用数据对象和其特征之间存在的协作关系，针对该问题，本文提出了基于特征词袋的双路聚类算法。该算法可以同时从数据对象和特征两个方向进行数据压缩，将特征词压缩袋一个词袋里，充分的利用二者之间存在的写作关系，对每一路数据进行分析。实验结果表明，该双聚类算法不仅提高了数据分析的精度，而且在动态减少的过程的数据分析，易于理解的数据分析结果。

关键词：聚类；特征词；数据分析；数据挖掘

中图分类号：TP311.13

传统聚类方法在进行数据分析时，尤其是在分析文本类数据时，仅仅从单一角度进行分析，往往忽略了能够提高聚类精度的关键内容，从而无法利用数据对象和特征之间存在的关系。为此，本文在已有的经典聚类算法基础上，提出了双路聚类算法。该算法进行聚类分析时，分为两个关键步骤：（1）使用某种聚类算法对特征进行聚类分析，寻找特征之间存在的潜在模式；（2）根据第一步寻找的特征模式，对数据对象进行聚类，寻找数据对象间存在的数据模式。

双路聚类算法对数据以及特征进行分析，其能够同时对数据以及特征进行分析，可以充分利用二者之间的协作关系。为了验证本文算法的效果，使用了经典的以互信息为度量的模拟退火的聚类算法[1]，该算法的实验数据来源于Lang收集的20-Newsgroup数据集[2]。实验结果表明，双聚类算法不仅可以获得更为准确的数据对象的潜在模式，提高数据分析结果的准确性，同时还存在动态降维的作用，加快了数据分析的时间精度。

本文提出了一种合理的数据分析机制，能够发现数据和特征存在的协作关系，该协作关系对数据分析结果具有很大的影响。

1背景知识

1.1双路聚类模型。传统聚类算法分析海量数据时，其原变量、目标变量和相关变量均是单一的。为此本文在前人研究的基础上，提出了一种双聚类思想，该思想可以将特征词压缩到特征词袋中[3]，然后对数据对象进行聚类分析，这样既可以降低数据分析时间，又可以提高其精度。具体双聚类模型进行聚类分析的过程可以描述如下：在压缩的过程中，给定的变量X和变量Y作为源变量和相关变量同时存在，变量X压缩到变量TX中尽可能保存变量Y（TY）的信息，变量Y压缩到变量TY中尽可能保存变量X（TX）的信息。该模型存在两个优点：一是高维数据分析时，不是全部特征对数据分析都有作用，数据中存在很多不相关或者是相关度较低的特征，维数过高造成维度灾难，双路聚类模型提供特征选择机制，将特征缩小到高度相关的范围内，该机制可称为动态降维。二是该模型使用数据和特征之间的协作关系，同时进行数据分析，不但提高数据分析结果的精度，还使数据分析结果变的更加容易解释。

基于以上描述可知双路聚类模型的目标函数为：

F（p（Tx|X），p（TY|Y））=I（X；Y）+I（TX；X）+I（TY；Y）-β（I（Tx；Y）+I（TY；X）+I（TX；TY））（1）

其中I（X；Y）是常量，可以省略不写，β是平衡因子。从双路聚类模型的目标函数可以得知，一方面要尽可能的压缩变量X和变量Y，另一方面也要尽可能的使TX和TY相互提供信息。

1.2双路聚类算法。为了验证本文算法的效果，本文引入经典的以互信息为度量的模拟退火的聚类算法[4]为对比，提出了基于双聚类模型的双聚类算法，其分析机制可以描述如下：初始变量X，Y中的数据为一个划分，使用自底向上凝聚原则，生成一棵层次树，每一次合并当前层的两个划分，使本层互信息损失最小，直到把全部数据合并到一个划分中。双路聚类算法对数据以及特征同时进行数据分析，与传统的数据分析算法相比，该算法具有很强的可视化性和可理解性。

本文使用文本数据验证双路聚类算法的有效性，具体地，X、Y、TX和TY分别指文本X、特征词Y、文本模式TX和特征词袋TY。假设tm和tn是即将压缩到一个变量的任意两个变量，压缩过程中损失的信息称为合并代价，其被定义为：

d（tm，tn）=I（Tbefore；Y）-I（Tafter；Y）（2）

其中，I（Tbefore；Y）和I（Tafter；Y）分别代表tm和tn合并前和合并后的T和Y之间的互信息。在传统聚类算法中，，双路聚类算法为实现动态的降维机制，，JSП（PPQ）是概率分布p（・）和q（・）之间的Jensen-Shannon距离，。基于上述思想，双路聚类算法如表1所示。

表1双路聚类算法

输入：联合概率分布P（X，Y），平衡参数β（调节压缩和保存之间的平衡），平衡参数α（调节合并X或者Y的次序）

输出：把X和Y分别划分到一个层次树中，其中||和||是期望得到的层（||=||，假设他们之间是一一对应的关系，为什么这么说呢，为了便于使用得到的解释得到的）

初始化：

X，Y，β=∞，

根据公式（2）计算所有模式对之间的合并代价_Merge_Cost[i，j]，1

根据公式（2）计算所有模式对之间的合并代价_Merge_Cost[m，n]，1

While（||>1）

{

Min_Merge_Cost[]；

Min_Merge_Cost[]；

if（）

{

；

根据公式（2）更新_Merge_Cost[]；

}

else

{

；

根据公式（2）更新_Merge_Cost[]；

}

}

End

2实验结果与分析

2.1实验评估方法。在本文中，数据采用Lang收集的20-Newsgroup数据集，并基于BoW工具进行预处理，从中取出九个子数据集，分别为B_1、B_2、B_3、M5_1、M5_2、M5_3、M10_1、M10_2、M10_3，每个数据集都包含500篇文章，计算每篇文章中的特征词对聚类的贡献，选取前2000个单词作为特征词。

为了有效的评估本文提出的双聚类算法的有效性，采用的评价标准包括精确度和召回率，精确度定义为：

（3）

召回率定义为：

（4）

其中，T表示聚类算法分析结果的类标号，C表示文本正确的类标号，因此，本文定义A1（c，T）表示正确分配到类C中的文本数，A2（c，T）表示错误的将文档分配到C中的文本数量，A3（c，T）表示错误的将文本分配到C中的文本数量。在聚类算法中，规定数据集和算法都是单类标记时，召回率和精确度是相同的，因此，本文的实验数据集和算法都是单类标，其算法运行结果仅用精确度进行度量即可。

2.2实验结果分析。传统聚类算法和双路聚类算法的实验结果如图1所示，经过分析，本文可以得到如下结果：（1）与传统聚类算法相比，双路聚类算法精确度更高。其中在数据集B_2上精确度提高最大，达到30.4%，在9个数据集上得到的平均精确度为73.7%，相比于传统聚类算法提高达14.0%。（2）与传统聚类算法相比，双聚类算法具有较好的鲁棒性。传统聚类算法在B_1、B_2、B_3上精确度表明了对于同构数据，其运行结果的精确度不够稳定，鲁棒性较低，而双聚类算法则表现很稳定，鲁棒性高。同时，该现象在其他6个数据集上也可以体现出来。

图1在九个数据集上，传统聚类算法和双路聚类算法运行结果精确度比较

3结论及下一步工作

传统聚类方法作为一种数据分析方法，已经得到广泛的应用，为了更好的适应问题需要，本文提出双路聚类模型。该模型可以从多视角对数据进行分析，然后利用每一路数据之间的协作关系，来更好地发现数据中隐含的数据模式，并利用得到的数据模式解释另一路数据模式。下一步工作是近一步完善双路聚类算法，利用无监督学习思想发现特征模式和数据模式之间的协作关系。

参考文献：

[1]N.Slonim，N.Friedman，N.Tishby.Unsuperviseddocumentclassificationusingsequentialinformationmaximization[C].In：Proceedingsofthe25thAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval，2002：129-136.

[2]R.Bekkerman，R.El-Yaniv，N.Tishby，etal.Distributionalwordclustersvs.wordsfortextcategorization[J].JournalofMachineLearningResearch，2003：1183-1208.

[3]C.Galleguillos，A.Rabinovich，S.Belongie.Objectcategorizationusingco-occurrence，locationandappearance[C].IEEEConferenceonComputerVisionandPatternRecognition，2008：1-8.

[4]N.Slonim，N.Tishby.Agglomerativeinformat