聚类算法流程

6．2．2　聚类算法流程

如前文所述，本文拟采用等级聚类算法，在以上相似度矩阵基础上聚类相似词汇。等级聚类算法属于自下而上的聚类算法，先将所有研究对象都各自看作一簇，将最“靠近”的首先进行聚类，再将这个新簇和其他最相近的簇结合，直到所有对象都合并为一个大簇为止。而词聚类目的在于把同一主题相关的词汇聚集到一起，把词汇集合按主题分成若干个簇，事先并不知道簇的数目，聚类算法需要停止在某个点上，即需要设定一个阈值以控制聚类过程，使得算法停止在此阈值时能够得到最好的聚类效果。

假设相似度阈值为D，当簇之间的最小距离d大于阈值D时，则认为剩余的簇之间主题相似程度很弱，结束聚类循环。其算法流程如下：

步骤1：初始化距离矩阵（即相似度矩阵，在聚类过程中通常把“相似度”称为“距离”，相似度越大，簇间距离越小）。首先根据关联概念空间，从大到小提取目标词汇的前50个最相关词汇作为特征向量。把词表中的每个词作为一个单独的簇，通过余弦相似度系数计算簇和簇之间的距离，生成距离矩阵。

图6－5　词聚类流程图

步骤2：找出距离最短的两个簇。

步骤3：合并距离最短的两个簇，生成一个新词簇。

步骤4：计算刚合并的簇与其他簇之间的距离，更新距离矩阵。

步骤5：判断最小距离是否小于阈值，是则结束程序，否则转步骤2。

如前文所述，根据步骤4中对簇间距离计算方法不同，等级聚类算法一般分为全连通、单连通和平均连通三种算法。为了说明算法，下面以几个词为例采用单连通聚类算法演示整个聚类过程。表6－4为经初始化后得到的相似度矩阵，各数据表示其所在行和列的词汇之间的相似度。

表6－4　初始相似度矩阵

经过比较，距离最近（即相似度最大）为0．73，因此第一次聚类实现对“企业所得税”和“所得税”的合并，从而生成新簇“企业所得税/所得税”。根据单连通算法对簇间距离的定义，再计算得到的新簇与剩余其他簇之间的距离分别为：

　　　　　distance（产品，企业所得税/所得税）

　　　　　＝min［distance（产品，企业所得税），distance（产品，所得税）］

　　　　　＝0．45

　　同理，distance（消费税，企业所得税/所得税）＝0．49

　　　　　distance（关税，企业所得税/所得税）＝0．59

　　　　　distance（公司，企业所得税/所得税）＝0．41

更新距离矩阵，得到相似度矩阵（见表6－5）：

表6－5　第一轮聚类后的相似度矩阵

以此类推，在以后聚类过程中，簇的合并情况以及生成的相似度矩阵（见表6－6、表6－7、表6－8）。

表6－6　第二轮聚类后的相似度矩阵

表6－7　第三轮聚类后的相似度矩阵

表6－8　第四轮聚类后的相似度矩阵

当所有簇都合并为一个大簇时，聚类结束。最后形成的类别体系如图6－6所示，当阈值设为大于0．47而小于0．49的一个数值时，聚类得到两个簇“企业所得税/所得税/关税/消费税”和“产品/公司”。

图6－6　聚类结果图示