4.4.3　方法及原理

（1）应用于网络舆情热点发现的文本聚类方法

设原始文档集个数为k，每个文档集对应一个主题，文档集分别记为。实验文档集为上述文档集的并集，在不必区分或者无法区分文档的归属时，可将文档集记为：，其中，为文档集中的文档数。聚类过程中，文档相似度采用笔者所提的随机n-Grams文本相似度计算方法（王贤明等，2013）进行计算，相似度阈值为T，即若文档相似度值不低于T，则将这些文档归属到一个类中。聚类中文档数阈值为C，即若某个初始聚类中的文档数不低于该值，则认定该初始聚类为一个有效聚类，否则舍弃。

聚类的主要流程如图4-12所示。

图4-12　聚类过程

其中，上述flag变量既可以用于记录初始聚类完毕时所得的聚类数，也可以用于记录各聚类的序号。S=Sim（di，dj）是文档di和dj的相似度值，范围为［0，100］。聚类完毕，根据flag值即可知所获得的初始聚类个数，且每个初始聚类中最少元素个数为C。此处的初始聚类是指经过上述方法聚类后的直接聚类结果，以便和最终的聚类区分开。

经由上述方法聚类后，所得初始聚类结果可以直接用于类似网络热点识别之类的应用场景。倘若需将其聚类应用到其他更为广泛的聚类场合，则需要对上述初始聚类结果执行合并处理。所谓合并处理，即对各个初始聚类进行二次聚类。二次聚类可以通过两种方式进行。第一种是准确性更好的方式，即将各个初始聚类视为一个整体来对待，例如计算各个初始聚类中文档集的频繁项集，该频繁项集对应于该初始聚类，然后利用频繁项集的方法（ZHANG W et al，2010）即可完成初始聚类的合并，亦即完成最终聚类。第二种是一种快捷的方式，即以各个初始聚类中的最长文档作为该聚类的代表文档，并对各个代表文档进行聚类计算。若代表文档聚为一类，则意味着其对应的初始聚类可以合并为一个大的聚类。一般情况下，采用第二种方式也可以取得较为满意的结果。由于聚类的合并可以采用多种常规的聚类方法，因此此处不再赘述。

（2）聚类覆盖率

设与原始文档集对应的各个合并聚类中元素数为，正确的元素数分别为，则聚类的整体覆盖率可被定义为：，即所有聚类中文档数之和与总文档数的比值；正确覆盖率定义为：，即所有聚类中正确的文档数之和与总文档数的比值。显然，聚类整体覆盖率和正确覆盖率的取值范围均为［0，1］，且满足Cr≤Ca，其中正确覆盖率表征了聚类的整体性能，其值越大，表明聚类整体效果越好。本文除了使用传统的准确率、召回率和F-score来讨论聚类结果外，还将使用聚类覆盖率指标对聚类结果进行讨论。