一种基于互信息的文本聚类算法研究

摘 要 随着互联网的应用和普及，集聚了海量的网络文档数据。为了提高网络数据的可利用性和用户搜索的准确度，本文提出了一种基于互信息的文本聚类算法，能够将网络文本数据自动分类，提高用户搜索的准确度和精确度。

【关键词】文本数据 聚类互信息 互联网

1 引言

随着计算机技术、网络技术的迅速普及和发展，用户规模迅速上升，诞生了海量的网络文档数据，面对海量的信息资源，人们无法根据自己的需求在短时间内寻找到期望的信息。聚类算法能够将海量数据集中具有相似主题的文档划分到一起，并且保证主题之间具有极大的相异性，被广泛的应用于网络文本数据挖掘中，目前，经过多年的研究，文本数据挖掘过程中已经诞生了许多优秀的聚类算法，比如K均值、密度聚类、词共现聚类、主成分分析等，并且有效的提高了文本数据挖掘的准确度。但是，聚类算法通常从单角度对文本数据进行挖掘和分析，但是随着文本数据较多，维度较大，因此聚类算法精确度急剧下降。为了解决上述问题，提高聚类算法精度，本文提出了基于互信息的文本聚类算法，可以从两个角度同时对文本数据集进行分析，实验结果显示本文算法能够提高聚类的准确度。

2 互信息理论

信息理论中，通常用熵描述两个概率事件发生的不确定程度，互信息是一种熵的应用形式，其可以描述两个概率之间的互相包含的程度，互信的数学形式化描述如下所述：给定一个离散随机变量（X，Y）～p（x，y），p（x）=∑Yp（x，y），p（y）=∑Xp（x，y），则随机变量X和Y之间互相包含的互信息为可以使用公式（1）描述：

I（X；Y）=∑X∑Yp（x，y）log （1）

3 基于互信息的文本聚类算法设计

在网络文本数据挖掘分析过中，基于互信息的文本聚类算法可以使用变量X描述文本数据集中的文本对象，使用变量Y描述文本数据集中的单词等特征对象，x表示某一个具体的文本，y表示一个具体的单词，因此基于互信息的文本聚类算法可以采用从文本对象、单词特征两个角度开始聚类分析，具体的聚类算法思想如下所述：在聚类算法开始执行的时候，基于互信息的聚类算法针对原始数据集从两个角度进行分析，将x作为一个相关变量，从y方向进行数据分析，尽可能的发现描述文本的单词的模式，这样就能够将相关的单词划分到一个个簇中，以簇为变量，将其作为X的相关变量Y；将第一步分析得到的单词簇Y作为文本变量x的相关变量，从x方向进行数据分析，尽可能精确的发现文本数据中蕴含的模式；在聚类算法执行过程中设定一个阈值，使得上述步骤能够交替进行聚类分析，实现文本数据挖掘。

在算法执行过程中，为了能够更好的实现数据迭代挖掘，算法的每一个执行步骤都可以使用数据集整体的互信息损失量进行度量，假设tm和tn是Tj中的两个对象，合并tm和tn所产生的信息损失，也称合并代价，定义为（2）：

cost（tm，tn）=I（Tbef；Y）−I（Taft；Y） （2）

通过上述算法执行的互信息度量方法法描述之后，本文给出了基于互信息的文本聚类算法具体描述：

输入：联合概率分布P（X，Y），文本数据X，单词数据Y，协作参数α和平衡参数β

输出：数据模式TX，TY

算法步骤：

①初始化文本数据TX←X，单词数据TY←Y，β=∞。

②基于公式（2）计算TX，TY中模式对之间的合并代价cost （ti，tj），cost （tm，tn），1≤i≤j≤|TX|，1≤m≤n≤|TY|。

③选择Min（Min（cost （ti，tj））， αMin（cost （tm，tn）））的一路数据合并。

④基于公式（2）更新下一次迭代时的合并代价cost（ti，tj），cost（tm，tn）。

⑤直到|TX|，|TY|全部合并到一个数据模式中，算法结束；否则，回到第3步。

4 算法实验及结果分析

算法实验过程中，本文采用Lang收集的文本数据集进行分析，通过对数据集进行预处理，本文选择出9个基本数据集，这九个基本数据集都能够准确的标注相关的具体文本分类，具体的为二类数据集三个、五类数据集三个、十类数据集三个，同时可以使用召回率分析文本聚类算法的准确度。同时，为了能够更好地验证本文算法的有效性，与最大距离法选取初始簇中心的K-means文本聚类算法的结果进行对比分析。

实验结果显示，在九个数据集上，本文算法的召回率都非常高，并且针对同构的文本数据挖掘过程中，具有较好的鲁棒性。比如在具有两个分类的数据中，数据分析精度区域稳定，没有出现大的跳跃，而K均值算法则出现了很大的波动。因此，从准确度和鲁棒性等方面验证了本文算法具有较大的优势。

参考文献

[1]郑诚，李鸿.基于主题模型的K-均值文本聚类[J].计算机与现代化，2013， 24（8）：78-80.

[2]李霞，蒋盛益，张倩生等.适用于大规模文本处理的动态密度聚类算法[J].北京大学学报：自然科学版，2013，49（1）：133-139.

作者单位

同济大学 上海市 200092