one preparation of algorithms in short text clustering

文本聚类算法

文本聚类一般步骤

• 文本表示（Text Representation）
  把文档表示成聚类算法可以处理的形式。
• 聚类算法选择或设计（Clustering Algorithms）
  算法的选择，往往伴随着相似度计算方法的选择。在文本挖掘中，最常用的相似度计算方法是余弦相似度。聚类算法有很多种，但是没有一个通用的算法可以解决所有的聚类问题。因此，需要认真研究要解决的问题的特点，以选择合适的算法。
• 聚类评估（Clustering Evaluation）
  因为没有训练文档集合，所以评测聚类效果是比较困难的。 常用的方法是： 选择人工已经分好类或者做好标记的文档集合作为测试集合，聚类结束后，将聚类结果与已有的人工分类结果进行比较。常用评测指标也是查全率、查准率及F1值。

六大常见聚类方法

• 均值聚类 K-Means

  • 算法步骤

    (1) 首先我们选择一些类/组，并随机初始化它们各自的中心点。中心点是与每个数据点向量长度相同的位置。这需要我们提前预知类的数量(即中心点的数量)。
    (2) 计算每个数据点到中心点的距离，数据点距离哪个中心点最近就划分到哪一类中。
    (3) 计算每一类中中心点作为新的中心点。
    (4) 重复以上步骤，直到每一类中心在每次迭代后变化不大为止。也可以多次随机初始化中心点，然后选择运行结果最好的一个。

  • 优点：
    速度快，计算简便

  • 缺点：
    我们必须提前知道数据有多少类/组。
    K-Medians是K-Means的一种变体，是用数据集的中位数而不是均值来计算数据的中心点。
    K-Medians的优势是使用中位数来计算中心点不受异常值的影响；缺点是计算中位数时需要对数据集中的数据进行排序，速度相对于K-Means较慢。

• 均值漂移聚类 mean shift

  • 具体步骤：
    \1. 确定滑动窗口半径r，以随机选取的中心点C半径为r的圆形滑动窗口开始滑动。均值漂移类似一种爬山算法，在每一次迭代中向密度更高的区域移动，直到收敛。
    \2. 每一次滑动到新的区域，计算滑动窗口内的均值来作为中心点，滑动窗口内的点的数量为窗口内的密度。在每一次移动中，窗口会想密度更高的区域移动。
    \3. 移动窗口，计算窗口内的中心点以及窗口内的密度，知道没有方向在窗口内可以容纳更多的点，即一直移动到圆内密度不再增加为止。
    \4. 步骤一到三会产生很多个滑动窗口，当多个滑动窗口重叠时，保留包含最多点的窗口，然后根据数据点所在的滑动窗口进行聚类。

  • 优点：

    （1）不同于K-Means算法，均值漂移聚类算法不需要我们知道有多少类/组。
    （2）基于密度的算法相比于K-Means受均值影响较小。
    缺点：

    （1）窗口半径r的选择可能是不重要的。

• 基于密度的聚类 DBSCAN

  • 具体步骤：
    \1. 首先确定半径r和minPoints. 从一个没有被访问过的任意数据点开始，以这个点为中心，r为半径的圆内包含的点的数量是否大于或等于minPoints，如果大于或等于minPoints则改点被标记为central point,反之则会被标记为noise point。
    \2. 重复1的步骤，如果一个noise point存在于某个central point为半径的圆内，则这个点被标记为边缘点，反之仍为noise point。重复步骤1，知道所有的点都被访问过。
  • 优点：不需要知道簇的数量
  • 缺点：需要确定距离r和minPoints

• 用高斯混合模型（GMM）的最大期望（EM）聚类

  • 具体步骤：
    \1. 选择簇的数量（与K-Means类似）并随机初始化每个簇的高斯分布参数（均值和方差）。也可以先观察数据给出一个相对精确的均值和方差。
    \2. 给定每个簇的高斯分布，计算每个数据点属于每个簇的概率。一个点越靠近高斯分布的中心就越可能属于该簇。
    \3. 基于这些概率我们计算高斯分布参数使得数据点的概率最大化，可以使用数据点概率的加权来计算这些新的参数，权重就是数据点属于该簇的概率。
    \4. 重复迭代2和3直到在迭代中的变化不大。

  • GMMs的优点：

    （1）GMMs使用均值和标准差，簇可以呈现出椭圆形而不是仅仅限制于圆形。K-Means是GMMs的一个特殊情况，是方差在所有维度上都接近于0时簇就会呈现出圆形。
    （2）GMMs是使用概率，所有一个数据点可以属于多个簇。例如数据点X可以有百分之20的概率属于A簇，百分之80的概率属于B簇。也就是说GMMs可以支持混合资格。

• 凝聚层次聚类 GAAC(Group-average Agglomerative Clustering)

  • 具体步骤：
    \1. 首先我们将每个数据点视为一个单一的簇，然后选择一个测量两个簇之间距离的度量标准。例如我们使用average linkage作为标准，它将两个簇之间的距离定义为第一个簇中的数据点与第二个簇中的数据点之间的平均距离。
    \2. 在每次迭代中，我们将两个具有最小average linkage的簇合并成为一个簇。
    \3. 重复步骤2知道所有的数据点合并成一个簇，然后选择我们需要多少个簇。
  • 优点：（1）不需要知道有多少个簇
    （2）对于距离度量标准的选择并不敏感
  • 缺点：效率低

• 图团体检测 Graph Community Detection

  • 具体步骤：
    \1. 首先初始分配每个顶点到其自己的团体，然后计算整个网络的模块性 M。
    \2. 第 1 步要求每个团体对（community pair）至少被一条单边链接，如果有两个团体融合到了一起，该算法就计算由此造成的模块性改变 ΔM。
    \3. 第 2 步是取 ΔM 出现了最大增长的团体对，然后融合。然后为这个聚类计算新的模块性 M，并记录下来。
    \4. 重复第 1 步和 第 2 步——每一次都融合团体对，这样最后得到 ΔM 的最大增益，然后记录新的聚类模式及其相应的模块性分数 M。
    \5. 重复第 1 步和 第 2 步——每一次都融合团体对，这样最后得到 ΔM 的最大增益，然后记录新的聚类模式及其相应的模块性分数 M。

补充

• 谱聚类 Spectral Clustering

  • 具体步骤：
    数据准备，生成图的邻接矩阵；
    归一化普拉斯矩阵；
    生成最小的k个特征值和对应的特征向量；
    将特征向量kmeans聚类(少量的特征向量)；

• CLARANS

• BIRCH

  全称为利用层次方法的平衡迭代规约和聚类（Balanced Iterative Reducing and Clustering Using Hierarchies）。BIRCH 算法利用了树结构来帮助我们快速的聚类，我们一般将 BIRCH 算法中的这种树结构称之为聚类特征树(Clustering Feature Tree，CF Tree)。

  聚类特征树的构建过程如下：

  1. 从根节点开始，自上而下选择最近的子节点；

  2. 到达叶子节点后，检查最近的元组$CF_i$能否在大样本半径阈值T范围内吸收此数据点，如果可以，则更新CF值；若不能，则考虑是否可以添加一个新的元组，若无法添加则分裂最远的一对元组，作为种子，按最近距离重新分配其它元组；

  3. 更新每个非叶节点的CF信息，如果分裂节点，在父节点中插入新的元组，检查分裂，直到root。在此基础上， BIRCH 算法的流程分为以下4个阶段：
     1)在内存中构建 CF 树；
     2)对第1阶段中的 CF 树进行瘦身（可选步骤）；
     3)以 CF 叶子节点对应的子簇为基础，实现数据点的聚类；
     4)对第3阶段的聚类结果进行精修（可选步骤）。

• CLIQUE

参考文章：
https://blog.csdn.net/cainiao22222/article/details/84861210
https://blog.51cto.com/u_15057807/4330081?articleABtest=1
https://blog.csdn.net/weixin_42788078/article/details/107929817