1. 算法依据

2. 算法特点

3. 术语定义

4. 算法步骤

4.1 预处理

• 分词(word segmentation)，去停用词(stop word removal)，词根还原(stemming)

4.2 文档表示

• 将文档表示成文档-词频矩阵，为了简化，只使用TF值。

      如下图所示，该示例文档集共12个文档，文档集的所有特征词数量为6。

     

4.3 挖掘全局频繁项集(设最小全局支持度为35%)

• 根据最小全局支持度挖掘所有的全局频繁项集(1-项集，2-项集......)，如下图所示：

     

4.4 构造初始簇(constructing initial clusters)

• 为每个频繁项集构造一个初始簇，初始簇由包含了频繁项集中的所有项的文档构成。
• 由于一个文档可能包含了多个全局频繁项集，所以初始簇不是分离的。
• 下一步将去除重叠簇。
• 初始簇的一个属性是：在簇中的所有文档一定包含了定义该簇的全局频繁项集的所有频繁项。
• 设最小簇支持度为70%，计算每个初始簇的全局簇频繁项。即对于某个全局的频繁项来说，如果簇Ci中有不少于70%的文档包含了该全局频繁项，则它变成了该簇的簇频繁项。
• 计算时可参考Table3.1，下图中的红色部分为反例。图示如下：

     

4.5 分离簇(making clusters disjoint)

• 由于一个文档可能属于多个初始簇，这一步我们将为每一个文档确定一个最佳初始簇。假设

  表示文档对于簇的归属合适度。对于每一个文档，我们只保留所有初始簇中值最大的，所有初始簇中的其它统统移除。如果有多个初始簇包含相同的最大值，我们就选择包含项最多的那个初始簇。经过这个步骤，每个文档属于唯一的一个簇。

• 直觉上告诉我们，如果簇中有许多的文档包含了"许多"全局频繁项，这些全局频繁项也出现在中，那么，文档对于簇的归属度就高。"许多"将由簇中的簇频繁来衡量。打分函数定义为

• x表示中的全局频繁项同时也是簇中的簇频繁项。x' 表示中的全局频繁项但不是中的簇频繁项。n(x)和n(x')为文档向量空间中的加权频率TF*IDF，为方便理解，本文仅用TF。

  例如：为了找到文档med.6最合适的归属簇，我们需要计算它对每个包含med.6的初始簇的分值，计算结果如下：

  

  

  

  

  由计算可知，有两个分值都是10.8，根据前面的原则，我们将文档med.6赋给初始簇，其它照做，得到的分离簇如下图所示。到此该算法的功能基本完成。