文本聚类算法总结

1. 聚类介绍

聚类试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为一个“簇”(cluster).
通过这样的划分，使得同一个簇内的数据对象的相似性尽可能大，同时不在同一个簇中的数据对象的差异性也尽可能地大。
聚类过程仅能自动形成簇结构，簇所对应的概念语义需由使用者自己来把握。
聚类既能作为一个单独的过程用于寻找数据内在的分布结构，也可以作为分类等其他学习任务的前驱过程。

1.1 聚类算法：

基于原型的聚类(Prototype-based Clustering)
- K均值聚类(K-means)
- 学习向量量化聚类(Learning Vector Quantization)
- 高斯混合模型聚类 (Gaussian Mixture Model)
基于密度的聚类 (Density-based Clustering)
- DBSCAN (Density-Based Spatial Clustering of Application with Noise)
- OPTICS (Ordering Points To Identify the Clustering Structure)
层次聚类 (Hierarchical Clustering)
基于模型的聚类 (Model-based Clustering)
- 混合回归模型 (Mixture Regression Model)
  1.2 聚类的一般过程

数据准备：特征标准化和降维
特征选择：从最初的特征中选择最有效的特征，并将其存储在向量中
特征提取：通过对选择的特征进行转换形成新的突出特征
聚类：基于某种距离函数进行相似度度量，获取簇
聚类结果评估：分析聚类结果，如距离误差和(SSE)等

1.3 聚类距离计算：

距离度量(distance measure)函数 $d()$ 需满足的基本性质：

非负性： $d(x,y)>=0$
同一性：$d(x,y) = 0 \quad if \quad and \quad only \quad if \quad x=y$
对称性： $d(x,y) = d(y,x)$
直递性：$d(x,y) \leq d(x,z) + d(z,y)$ (可不满足)

常用基于距离的相似度度量方法：

欧几里得距离：

曼哈顿距离：

1.4 聚类性能度量：

聚类性能度量亦称聚类“有效性指标”(validity index).

设置聚类性能度量的目的:

对聚类结果，通过某种性能度量来评估其好坏；
若明确了最终将要使用的性能度量，则可直接将其作为聚类过程的优化目标，从而更好地得到符合要求的聚类结果。

什么样的聚类结果比较好？

“簇内相似度”(intra-cluster similarity)高
“蔟间相似度”(inter-cluster similarity)低

聚类性能度量分类：

“外部指标”(external index) ：将聚类结果与某个“参考模型”(reference model)进行比较
“内部指标”(internal index): 直接考察聚类结果而不利用任何参考模型

性能度量指标：

(1) 外部指标

(2) 内部指标

2 聚类算法介绍及实现

聚类算法类型：

基于原型的聚类(Prototype-based Clustering)
- K均值聚类(K-means )
- 学习向量量化聚类(Learning vector Quantization)
- 高斯混合聚类(Mixture-of-Gaussian)
基于密度的聚类(Density-based Clustering)
层次聚类(Hierarchical Clustering)

2.1 基于原型的聚类

原型聚类prototype-based clustering，假设聚类结构能通过一组原型刻画（原型，即簇类的数目或者聚类中心）. 通常情况下, 算法先对原型进行初始化, 然后对原型进行迭代更新求解, 采用不同的原型表示, 不同的求解方式,将产生不同的算法.

2.1.1 K-means

(1) 算法介绍

给定样本集 $D={x_1,x_2,…,x_n}$, K-means 算法针对聚类所得簇划分 $C={C_1,C_2,…,C_k}$, 最小化平方误差:

其中 $u_k$ 是簇的均值向量：

直观上看, 平方误差在一定程度上刻画了簇内样本围绕均值向量的紧密程度, $err$ 值越小簇内样本相似度越高。但最小化 $err$ 不容易，是一个NP难问题, K-means 算法采用了贪心策略，通过迭代优化来近似求解 EE 的最小值。具体算法如下：

(2) 算法实现

我们的 k-means 实现将分为五个辅助方法和一个运行算法的主循环：

1.计算成对距离

def pairwise_dist(self, x, y):
        """
        Args:
            x: N x D numpy array
            y: M x D numpy array
        Return:
            dist: N x M array, where dist2[i, j] is the euclidean distance between 
            x[i, :] and y[j, :]
        """
        xSumSquare = np.sum(np.square(x),axis=1);
        ySumSquare = np.sum(np.square(y),axis=1);
        mul = np.dot(x, y.T);
        dists = np.sqrt(abs(xSumSquare[:, np.newaxis] + ySumSquare-2*mul))
        return dists

pairwise_dist 函数与前面描述的相似性函数等效。这是我们比较两点相似性的指标。在这里，我使用的是欧几里得距离。我使用的公式可能看起来与欧几里德距离函数的常规公式不同。这是因为我们正在执行矩阵操作，而不是使用两个单个向量。在这里深入阅读。

2.初始化中心

def _init_centers(self, points, K, **kwargs):
        """
        Args:
            points: NxD numpy array, where N is # points and D is the dimensionality
            K: number of clusters
            kwargs: any additional arguments you want
        Return:
            centers: K x D numpy array, the centers. 
        """
        row, col = points.shape
        retArr = np.empty([K, col])
        for number in range(K):
            randIndex = np.random.randint(row)
            retArr[number] = points[randIndex]
        
        return retArr

该函数接收点数组并随机选择其中的 K 个作为初始质心。该函数仅返回 K 个选定点。

3.更新分配

def _update_assignment(self, centers, points):
        """
        Args:
            centers: KxD numpy array, where K is the number of clusters, and D is the dimension
            points: NxD numpy array, the observations
        Return:
            cluster_idx: numpy array of length N, the cluster assignment for each point

        Hint: You could call pairwise_dist() function.
        """
        row, col = points.shape
        cluster_idx = np.empty([row])
        distances = self.pairwise_dist(points, centers)
        cluster_idx = np.argmin(distances, axis=1)

        return cluster_idx

更新分配函数负责选择每个点应该属于哪个集群。首先，我使用 pairwise_dist 函数计算每个点和每个质心之间的距离。然后，我得到每一行的最小距离的索引。最小距离的索引也是给定数据点的聚类分配索引，因为我们希望将每个点分配给最近的质心。

4.更新中心

def _update_centers(self, old_centers, cluster_idx, points):
        """
        Args:
            old_centers: old centers KxD numpy array, where K is the number of clusters, and D is the dimension
            cluster_idx: numpy array of length N, the cluster assignment for each point
            points: NxD numpy array, the observations
        Return:
            centers: new centers, K x D numpy array, where K is the number of clusters, and D is the dimension.
        """
        K, D = old_centers.shape
        new_centers = np.empty(old_centers.shape)
        for i in range(K):
            new_centers[i] = np.mean(points[cluster_idx == i], axis = 0)
        return new_centers

更新中心功能负责对属于给定集群的所有点进行平均。该平均值是相应聚类的新质心。该函数返回新中心的数组。

5.计算损失

def _get_loss(self, centers, cluster_idx, points):
        """
        Args:
            centers: KxD numpy array, where K is the number of clusters, and D is the dimension
            cluster_idx: numpy array of length N, the cluster assignment for each point
            points: NxD numpy array, the observations
        Return:
            loss: a single float number, which is the objective function of KMeans. 
        """
        dists = self.pairwise_dist(points, centers)
        loss = 0.0
        N, D = points.shape
        for i in range(N):
            loss = loss + np.square(dists[i][cluster_idx[i]])
        
        return loss

损失函数是我们评估聚类算法性能的指标。我们的损失只是每个点与其聚类质心之间的平方距离之和。在我们的实现中，我们首先调用成对距离来获得每个点和每个中心之间的距离矩阵。我们使用 cluster_idx 为每个点选择与集群对应的适当距离2。

主循环

def __call__(self, points, K, max_iters=100, abs_tol=1e-16, rel_tol=1e-16, verbose=False, **kwargs):
        """
        Args:
            points: NxD numpy array, where N is # points and D is the dimensionality
            K: number of clusters
            max_iters: maximum number of iterations (Hint: You could change it when debugging)
            abs_tol: convergence criteria w.r.t absolute change of loss
            rel_tol: convergence criteria w.r.t relative change of loss
            verbose: boolean to set whether method should print loss (Hint: helpful for debugging)
            kwargs: any additional arguments you want
        Return:
            cluster assignments: Nx1 int numpy array
            cluster centers: K x D numpy array, the centers
            loss: final loss value of the objective function of KMeans
        """
        centers = self._init_centers(points, K, **kwargs)
        for it in range(max_iters):
            cluster_idx = self._update_assignment(centers, points)
            centers = self._update_centers(centers, cluster_idx, points)
            loss = self._get_loss(centers, cluster_idx, points)
            K = centers.shape[0]
            if it:
                diff = np.abs(prev_loss - loss)
                if diff < abs_tol and diff / prev_loss < rel_tol:
                    break
            prev_loss = loss
            if verbose:
                print('iter %d, loss: %.4f' % (it, loss))
        return cluster_idx, centers, loss

现在，在主循环中，我们可以组合所有实用函数并实现伪代码。首先，中心用_init_centers随机初始化。然后，对于指定的迭代次数，我们重复update_assignment和update_centers步骤。每次迭代后，我们计算总损失并将其与之前的损失进行比较。如果差异小于我们的阈值，则算法执行完成。

补充：

k-means 优点：

计算复杂度低，为，其中为迭代次数。
通常和要远远小于，此时复杂度相当于。

思想简单，容易实现。

k-means 缺点：

需要首先确定聚类的数量

分类结果严重依赖于分类中心的初始化。
通常进行多次k-means，然后选择最优的那次作为最终聚类结果。

结果不一定是全局最优的，只能保证局部最优。

对噪声敏感。因为簇的中心是取平均，因此聚类簇很远地方的噪音会导致簇的中心点偏移。

无法解决不规则形状的聚类。

无法处理离散特征，如：国籍、性别 等。

正确使用「K均值聚类」的Tips

输入数据一般需要做缩放，如标准化。原因很简单，K均值是建立在距离度量上的，因此不同变量间如果维度差别过大，可能会造成少数变量“施加了过高的影响而造成垄断”。

输出结果非固定，多次运行结果可能不同。首先要意识到K-means中是有随机性的，从初始化到收敛结果往往不同。一种看法是强行固定随机性，比如设定sklearn中的random state为固定值。另一种看法是，如果你的K均值结果总在大幅度变化，比如不同簇中的数据量在多次运行中变化很大，那么K均值不适合你的数据，不要试图稳定结果 [2]。

运行时间往往可以得到优化，选择最优的工具库。基本上现在的K均值实现都是K-means++，速度都不错。但当数据量过大时，依然可以使用其他方法，如MiniBatchKMeans [3]。上百万个数据点往往可以在数秒钟内完成聚类，推荐Sklearn的实现。

高维数据上的有效性有限。建立在距离度量上的算法一般都有类似的问题，那就是在高维空间中距离的意义有了变化，且并非所有维度都有意义。这种情况下，K均值的结果往往不好，而通过划分子空间的算法（sub-spacing method）效果可能更好。

运行效率与性能之间的取舍。

K值怎么确定

使用 K 均值算法，性能可能会因您使用的集群数量而有很大差异。要知道，K设置得越大，样本划分得就越细，每个簇的聚合程度就越高，误差平方和SSE自然就越小。所以不能单纯像选择初始点那样，用不同的K来做尝试，选择SSE最小的聚类结果对应的K值，因为这样选出来的肯定是你尝试的那些K值中最大的那个。

“手肘法”（Elbow Method）
为了使用肘部方法，您只需多次运行 K-means 算法，每次迭代将聚类数增加一个。记录每次迭代的损失，然后制作 num cluster vs loss 的折线图。

下面是肘部方法的简单实现：

运行此方法将输出一个类似于您在下面看到的图：

现在，为了选择正确数量的簇，我们进行目视检查。损耗曲线开始弯曲的点称为肘点。肘点代表误差和聚类数量之间的合理权衡。在此示例中，肘点位于x = 3 处。这意味着最佳聚类数为 3。

def find_optimal_num_clusters(self, data, max_K=15):
        """
        Plots loss values for different number of clusters in K-Means

        Args:
            image: input image of shape(H, W, 3)
            max_K: number of clusters
        Return:
            None (plot loss values against number of clusters)
        """
        y_val = np.empty(max_K)

        for i in range(max_K):
            cluster_idx, centers, y_val[i] = KMeans()(data, i + 1)
            
        plt.plot(np.arange(max_K) + 1, y_val)
        plt.show()
        return y_val

from sklearn.cluster 
import KMeans

loss = []
for i in range(1, 10):    
  kmeans = KMeans(n_clusters=i, max_iter=100).fit(p_list)    
  loss.append(kmeans.inertia_ / point_number / K)    
plt.plot(range(1, 10), loss)plt.show()

2.1.2 k-means++

k-means++是针对k-means中初始质心点选取的优化算法。该算法的流程和k-means类似，改变的地方只有初始质心的选取，该部分的算法流程如下

算法步骤：

从中随机选择1个样本作为初始均值向量组。
迭代，直到初始均值向量组有个向量。
假设初始均值向量组为。迭代过程如下：
- 对每个样本，分别计算其距的距离。这些距离的最小值记做。
- 对样本，其设置为初始均值向量的概率正比于。即：离所有的初始均值向量越远，则越可能被选中为下一个初始均值向量。
- 以概率分布（未归一化的）随机挑选一个样本作为下一个初始均值向量。
一旦挑选出初始均值向量组，剩下的迭代步骤与k-means 相同。

2.1.3 LVQ

(1) 算法介绍

Learning vector Quantization (LVQ) 假设数据样本带有类别标记，学习过程利用样本的这些监督信息来辅助聚类。使用通过LVQ得到的原型向量来代表整个簇的过程，称为“向量量化”（Vector Quantization），这种数据压缩方法属于“有损压缩”（Lossy Compression）。

LVQ的目标是学得一组原型向量 ${p_1,p_2,…,p_q}$，每个原型向量代表一个聚类簇。LVQ在训练过程中通过对神经元权向量（原型向量）的不断更新，对其学习率的不断调整，能够使不同类别权向量之间的边界逐步收敛至贝叶斯分类边界。算法中，对获胜神经元（最近邻权向量）的选取是通过计算输入样本和权向量之间的距离的大小来判断的。

具体算法流程图如下所示：

算法解释

算法第1行：对原型向量进行初始化。例如：对第$i, i=(1,2,…,q)$ 个簇,从类别标记为 $t_i$ 的样本中随机选取一个作为原型向量。如果类别数小于聚类数，即 k>m ，则重新从第一个类别中继续选取；
算法第2-12行：对原型向量进行迭代优化，直到算法收敛。在每一轮迭代中，算法随机选取一个有标记训练样本，找出与其距离最近的原型向量，并根据两者的类别标记是否一致来对原型向量进行相应的更新。
算法第2-5行：从样本集中随机选取一个样本 $x_j$，计算该样本与每个原型向量 $p_i$ 之间的欧式距离，并找到与该样本距离最近的原型向量 $p_{i^}$ 的类别标记 $t_{i^}$
第6-10行：如何更新原型向量。迭代过程如下：
- 从样本集中随机选取样本，挑选出距离最近的原型向量：。
- 如果的类别等于，则：，将该原型向量更靠近
- 如果的类别不等于，则：，将该原型向量更远离

在原型向量的更新过程中：

如果的类别等于，则更新后，与距离为：

即，更新后的原型向量距离更近。
如果的类别不等于，则更新后，与距离为：

即，更新后的原型向量距离更远。
- 算法第12行：若算法的停止条件已满足(例如已达到最大迭代轮数，或原型向量更新很小甚至不再更新)，则将当前原型向量作为最终结果返回。
- 在学得一组原型向量 ${p_1,p_2,…,p_q}$ 后即可实现对样本空间 $X$ 的簇划分. 对任意样本 $x$, 他将被划入与其距离最近的原型向量所代表的簇中

可能涉及到的问题：

首先，既然已经有标签数据，那么为什么还要进行聚类呢？

我们输入的先验标签数据不一定是绝对真实的取值，可能是其他分类器输出的结果，可能是片面的、残缺的，需要靠聚类进行矫正和修补。（可以将先验知识当做一个约束值，该算法相当于在已知的约束条件下求解最最优值的过程）

对于矫正作用，由于输入的只有标签值，需要靠聚类进行类别边界的拟合；对于修补作用，由于LVQ聚类算法允许聚类的簇比输入的标签的类别多，这意味着一个类别可以被重新分割成多个类别。

其次，标签值是必须的吗？

一种说法是标签值是非必须的，如果没有先验的标签值，可以输入随机的标签值。我不太认同这种做法。因为标签值是一种约束，随机的约束即相当于没有约束，那么LVQ算法其实就退化为一般的聚类的算法，甚至更加严重，随机会使得系统更加混沌，算法会因为错误的指导给出效果更差的答案。所以我更偏向于将其归为半监督的聚类算法。

其他注意事项

样本异常点对聚类有影响，一般我们需要提前剔除掉
难以应用在高维特征空间
可以多选择几个簇心，来降低压缩率，提高保持较高的精度？
为了得到更精确的代表点需要调整迭代次数和学习率，时间复杂度比较

(2) LVQ算法实现

《手写LVQ（学习向量量化）聚类算法》
《ml/lvq/lvq_test/lvq_test.py》√
《neupy/neupy/algorithms/competitive/lvq.py 》√
《Learning Vector Quantization详解》

def lvq(data: np, k_num: int, labels: list, lr=0.01, max_iter=15000, delta=1e-3):
    """
    :param data: 样本集, 最后一列feature表示原始数据的label
    :param k_num: 簇数，原型向量个数
    :param labels: 1-dimension list or array,label of the data（去重）
    :param max_iter: 最大迭代数
    :param lr: 学习效率
    :param delta: max distance for two vectors to be 'equal'.
    :return: 返回向量中心点、簇标记
    """
    # 随机初始化K个原型向量
    v = rand_initial_center(data, k_num, labels)

    # 确认是否所有中心向量均已更新
    all_vectors_updated = np.zeros(shape=(k_num,), dtype=np.bool)
    # 记录各个中心向量的更新次数
    v_update_cnt = np.zeros(k_num, dtype=np.float32)

    j = 0
    while True:
        j = j + 1
        if j%100==0:
            print("iter:", j)

        # 迭代停止条件：已到达最大迭代次数，或者原型向量全都更新过
        if j >= max_iter or all_vectors_updated.all():
            break
        # # 迭代停止条件：超过阈值且每个中心向量都更新超过5次则退出
        # if j >= max_iter and sum(v_update_cnt > 5) == k_num:
        #     break

        # 随机选择一个样本, 并计算与当前各个簇中心点的距离, 取距离最小的
        sel_sample = random.choice(data)
        min_dist = distance(sel_sample, v[0])
        sel_k = 0
        for ii in range(1, k_num):
            dist = distance(sel_sample, v[ii])
            if min_dist > dist:
                min_dist = dist
                sel_k = ii

        # 保存更新前向量
        temp_v = v[sel_k].copy()

        # 更新v：如果标签相同，则q更新后接近样本x，否则远离
        if sel_sample[-1] == v[sel_k][-1]:
            v[sel_k][0:-1] = v[sel_k][0:-1] + lr * (sel_sample[0:-1] - v[sel_k][0:-1])
        else:
            v[sel_k][0:-1] = v[sel_k][0:-1] - lr * (sel_sample[0:-1] - v[sel_k][0:-1])

        # 更新记录数组（更新后簇心基本不变，就认为更新好了）
        if distance(temp_v, v[sel_k]) < delta:
            all_vectors_updated[sel_k] = True
        # v的更新次数+1
        v_update_cnt[sel_k] = v_update_cnt[sel_k] + 1

    # 更新完毕后, 把各个样本点进行标记, 记录放在categories变量里
    m, n = np.shape(data)
    cluster_assment = np.mat(np.zeros((m, 2)), dtype=np.float32)
    for i in range(m):
        min_distji = np.inf
        min_distji_index = -1

        for j in range(k_num):
            distji = distance(data[i, :], v[j, :])
            # print(distji)
            if min_distji > distji:
                min_distji = distji
                min_distji_index = j
        cluster_assment[i, 0] = min_distji_index
        cluster_assment[i, 1] = min_distji

    return v, cluster_assment

(3) LVQ2算法改进

LVQ算法中，对于某个输入向量X，算法只对与其具有最小Euclidean距离的权向量$w_k$ 进行调整。

在LVQ2[2]中，算法还要考虑与X具有次近Euclidean距离的权向量$w_r$，X与$w_k$及$w_r$间的距离分别记为 $d_k$ 与 $d_r$。如果下述3个条件都满足的话，算法就对$w_k$及$w_r$同时进行调整，否则就按照原先的LVQ算法调整权向量$w_k$：

$w_k$及$w_r$代表不同的分类。
次近权向量$w_r$与X代表同一个分类。
$d_k$ 与 $d_r$大致相等。一般来说．如果 $d_k$ 与 $d_r$能够满足$d_k/d_r>(1一￡)$且 $d_r/d_k<(1+￡)$，我们就认为 $d_k$ 与 $d_r$是大致相等的，其中￡的取值依赖于训练例的多少。

在上述3个条件都满足的情况下，按下述公式调整$w_k$及$w_r$，使得$w_k$远离输入向量X，而$w_r$向输入向量的方向靠近：

$W_k(new)=W_k(old)一\alpha(X—W_k(old))$
$W_r(new)=W_r(old)+\alpha(X—W_r(old))$

LVQ2算法通过同时考察两个权值向量$w_k$及$w_r$，可以加快算法的收敛速度，使得各个权向量快速的向目标位置移动。

(4) LVQ2.1算法改进

LVQ2.1在LVQ2的基础上做了一些改进．LVQ2.1也是同时考察与某个输入向量X最近的两个权向量 $w_{c1},w_{c_2}$，但并不关心$w_{c1},w_{c_2}$哪一个离X更近(对应的距离分别为$d_{c1},d_{c_2}$)。当下面两个条件同时满足时将对$w_{c1},w_{c_2}$进行调整：

$w_{c1},w_{c_2}$中，有一个权向量代表的分类和X所表示的一致，而另一个不一致。
$max[d_{c_1}／d_{c_2},d_{c_2}／d_{c_1}]<(1+￡)$且$min[d_{c_1}／d_{c_2},d_{c_2}／d_{c_1}]>(1-￡)$

如果上述条件满足，不妨设 $w_{c1}$与X代表的类别相同，算法将调整权向量$w_{c1},w_{c_2}$，使得 $w_{c1}$输入向量X的方向靠近，而 $w_{c_2}$远离输入向量．调整公式为：

$W_{c_1}(new)=W_{c_1}(old)+\alpha(X—W_{c_1}(old))$
$W_{c_2}(new)=W_{c_2}(old)-\alpha(X—W_{c_2}(old))$

(5) LVQ3算法改进

LVQ3也是同时考虑与输入向量X距离最近的两个权向量 $w_{c1},w_{c_2}$。当条件 $min[d_{c_1}／d_{c_2},d_{c_2}／d_{c_1}]>(1-￡)(1+￡)$ 满足时 (￡的一个典型取值为0.2). 权向量将按照下述规则进行调整：

如果 $w_{c1},w_{c_2}$两个权向量中有一个对应的分类与输入向量X一致，另一个不一致，则权向量的调整规则同 LVQ2.1
如果 $w_{c1},w_{c_2}$代表相同的分类，则权向量 $w_{c1},w_{c_2}$均采用公式 $W_{c}(new)=W_{c}(old)+\beta(X—W_{c}(old))$ 进行调整，其中$\beta=m\alpha, 0.1<m<0.5$

LVQ3算法通过对标准LVQ算法学习过程的修改，可以使得在网络学习过程不断进行的同时，网络的权向量能够很好地反映输入空间的概率密度分布，并且防止权向量偏离最优的位置。

(6) G-LVQ

G-LVQ将遗传算法应用于LVQ算法中，以克服LVQ算法本身的一些缺陷。

2.1.4 高斯混合聚类(Mixture-of-Gaussian)

高斯混合聚类(Mixture-of-Gaussian)采用概率模型来表达聚类原型.

对于维样本空间中的随机向量，若服从高斯分布，则其概率密度函数为：

其中为维均值向量，是的协方差矩阵。的概率密度函数由参数决定。
定义高斯混合分布：。该分布由个混合成分组成，每个混合成分对应一个高斯分布。其中:
- 是第个高斯混合成分的参数。
- 是相应的混合系数，满足。
假设训练集的生成过程是由高斯混合分布给出。
令随机变量表示生成样本的高斯混合成分序号，的先验概率。
生成样本的过程分为两步：
- 首先根据概率分布生成随机变量。
- 再根据的结果，比如，根据概率生成样本。
根据贝叶斯定理，若已知输出为，则的后验分布为：

其物理意义为：所有导致输出为的情况中，发生的概率。
当高斯混合分布已知时，高斯混合聚类将样本集划分成个簇。
对于每个样本，给出它的簇标记为：

即：如果最有可能是产生的，则将该样本划归到簇。
这就是通过最大后验概率确定样本所属的聚类。
现在的问题是，如何学习高斯混合分布的参数。由于涉及到隐变量，可以采用EM算法求解。
具体求解参考EM 算法的章节部分。

2.2 基于密度的聚类

k-means算法对于凸性数据具有良好的效果，能够根据距离来讲数据分为球状类的簇，但对于非凸形状的数据点，就无能为力了，当k-means算法在环形数据的聚类时，我们看看会发生什么情况。

从上图可以看到，kmeans聚类产生了错误的结果，这个时候就需要用到基于密度的聚类方法了。基于密度的聚类(Density-based Clustering)假设聚类结构能通过样本分布的紧密程度确定.密度聚类算法从样本密度的角度来考察样本之间的可连续性，并基于可连续样本不断扩展聚类簇以获得最终的聚类结果.

基于密度的聚类(Density-based Clustering)

DBSCAN (Density-Based Spatial Clustering of Application with Noise)
OPTICS (Ordering Points To Identify the Clustering Structure)

2.2.1 DBSCAN

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种基于密度的空间聚类算法,它不需要定义簇的个数,而是将具有足够高密度的区域划分为簇,并在有噪声的数据中发现任意形状的簇,在此算法中将簇定义为密度相连的点的最大集合。

首先介绍几个概念，考虑集合 $X=\left \{x^{(1)},x^{(2)},...,x^{(n)}\right \}#id=WvKOb$ ， $\varepsilon#id=cSBrZ$ 表示定义密度的邻域半径，设聚类的邻域密度阈值为 $M#id=KESNV$ ，有以下定义：

$\varepsilon#id=tQJVL$ 邻域( $\varepsilon#id=kjQhZ$ -neighborhood）

$N_{\varepsilon }(x)=\left \{y\in X|d(x, y) < \varepsilon \right \} \\#id=zSPxt$

密度(desity) $x#id=y738D$ 的密度为

$\rho (x)=\left | N_{\varepsilon }(x)\right | \\#id=i6wfz$

核心点(core-point)
设 $x\in X#id=qDZHW$ ，若 $\rho (x) \geq M#id=kZEUo$ ，则称 $x#id=q1PI2$ 为 $X#id=yArJ9$ 的核心点，记 $X#id=EBfiT$ 中所有核心点构成的集合为 $X_c#id=RgIvj$ ，记所有非核心点构成的集合为 $X_{nc}#id=xFShV$ 。
边界点(border-point)
若 $x\in X_{nc}#id=qI4A7$ ，且 $\exists y\in X#id=Ljp87$ ，满足
$y\in N_{\varepsilon }(x) \cap X_c \\#id=FELj9$
即 $x#id=C3LHo$ 的 $\varepsilon#id=tUAlp$ 邻域中存在核心点，则称 $x#id=JBGnC$ 为 $X#id=oatxR$ 的边界点，记 $X#id=OGj7O$ 中所有的边界点构成的集合为 $X_{bd}#id=Psyte$ 。
此外，边界点也可以这么定义：若 $x\in X_{nc}#id=J5RaA$ ，且 $x#id=sLlm4$ 落在某个核心点的 $\varepsilon#id=YlxYk$ 邻域内，则称 $x#id=tMsk4$ 为 $X#id=Sp9mo$ 的一个边界点，一个边界点可能同时落入一个或多个核心点的 $\varepsilon#id=B7oOd$ 邻域。
噪声点(noise-point)
若 $x#id=ME8Pu$ 满足
$x\in X,x \notin X_{c}且 x\notin X_{bd} \\#id=M9jlO$
则称 $x#id=g0C0n$ 为噪声点。
如下图所示，设 $M=3#id=U2niB$ ，则A为核心点，B、C是边界点，而N是噪声点。

该算法的流程如下：

算法说明:

DBSCAN算法先任选数据集中的一个核心对象为 “种子 (seed)”,再由此出发确定相应的聚类簇；
第1-7行：先根据给定的邻域簇 $(c,MinPts)$ 找出所有核心对象；
第10-24行：以任一核心对象为出发点，找出由其密度可达的样本生成聚类簇，直到所有核心对象均被访问过为止.

一般来说，DBSCAN算法有以下几个特点：

需要提前确定 $\varepsilon #id=oe60x$ 和 $M#id=SzpN5$ 值

不需要提前设置聚类的个数

对初值选取敏感，对噪声不敏感

对密度不均的数据聚合效果不好

2.2.2 OPTICS

OPTICS (Ordering Points To Identify the Clustering Structure). OPTICS和DBSCAN聚类相同,都是基于密度的聚类,但是,OPTICS的好处在于可以处理不同密度的类,结果有点像基于连通性的聚类,不过还是有些区别的.

2.3 层次聚类方法

前面介绍的几种算法确实可以在较小的复杂度内获取较好的结果，但是这几种算法却存在一个链式效应的现象，比如：A与B相似，B与C相似，那么在聚类的时候便会将A、B、C聚合到一起，但是如果A与C不相似，就会造成聚类误差，严重的时候这个误差可以一直传递下去。为了降低链式效应，这时候层次聚类就该发挥作用了。

层次聚类(Hierarchical Clustering) 也称为基于连通性的聚类。这种算法试图在不同层次对数据进行划分，从而形成树形的聚类结构。

数据集的划分采用不同的策略会生成不同的层次聚类算法：

“自底向上”的聚合策略
（Agglomerative）。每一个对象最开始都是一个 cluster，每次按一定的准则将最相近的两个 cluster 合并生成一个新的 cluster，如此往复，直至最终所有的对象都属于一个 cluster。这里主要关注此类算法。
- AGNES(Agglomerative Nesting)
“自顶向下”的分拆策略
（Divisive）。最开始所有的对象均属于一个 cluster，每次按一定的准则将某个 cluster 划分为多个 cluster，如此往复，直至每个对象均是一个 cluster。

2.3.1 AGNES

(1) 算法介绍

AGNES(Agglomerative Nesting)是一种采用自底向上聚合策略的层次聚类算法，算法的步骤为：

先将数据集中的每个样本当做是一个初始聚类簇;
然后在算法运行的每一步中找出距离最近的两个点(聚类簇)进行合并为一个聚类簇;
上述过程不断重复，直至所有的样本点合并为一个聚类簇或达到预设的聚类簇个数。最终算法会产生一棵树，称为树状图(dendrogram), 树状图展示了数据点是如何合并的.

这个算法的关键是如何计算两点之间以及两个聚类簇之间的距离

如何计算两点之间的距离[距离矩阵(Metric)]：
如何计算两个聚类簇(集合)之间的距离[链接准则(Linkage criteria)]：

Complete-linkage clustering(全链接)
Single-linkage clustering(单链接)
Mean-linkage clustering(平均链接 UPGMA)
Centroid-linkage clustering(中心链接 UPGMC)
Minimum energy clustering

3 聚类效果评价指标

这里给出三个聚类效果评价指标：互信息，标准化互信息，调整互信息(MI, NMI, AMI)

互信息(Mutual information)

互信息的计算公式如下：

标准化互信息(NMI, Normalized Mutual Information)

通常采用NMI和AMI来作为衡量聚类效果的指标。

标准化互信息的计算方法如下：

调整互信息(AMI, Adjusted Mutual Information)

调整互信息的计算要复杂一些，其计算方法如下：

Python实现

Python中的 sklearn 库里有这三个指标的类，可以直接调用；

from sklearn.metrics.cluster import entropy, mutual_info_score, normalized_mutual_info_score, adjusted_mutual_info_score

MI = lambda x, y: mutual_info_score(x, y)
NMI = lambda x, y: normalized_mutual_info_score(x, y, average_method='arithmetic')
AMI = lambda x, y: adjusted_mutual_info_score(x, y, average_method='arithmetic')

A = [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3]
B = [1, 2, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 1, 1, 3, 3, 3]
#print(entropy(A))
#print(MI(A, B))
print(NMI(A, B))
print(AMI(A, B))

C = [1, 1, 2, 2, 3, 3, 3]
D = [1, 1, 1, 2, 1, 1, 1]
print(NMI(C, D))
print(AMI(C, D))

参考

#文本聚类

文本聚类算法总结

http://example.com/2021/09/06/2021-09-06-文本聚类算法总结/

作者

NSX

发布于

2021年9月6日

许可协议

K-means聚类详解上一篇

阿里云es内部技术分享摘要下一篇

正确使用kmeans聚类的姿势

1. 聚类介绍

1.1 聚类算法：

1.2 聚类的一般过程

1.3 聚类距离计算：

1.4 聚类性能度量：

2 聚类算法介绍及实现

2.1 基于原型的聚类

2.1.1 K-means

(1) 算法介绍

(2) 算法实现

2.1.2 k-means++

2.1.3 LVQ

(1) 算法介绍

(2) LVQ算法实现

(3) LVQ2算法改进

(4) LVQ2.1算法改进

(5) LVQ3算法改进

(6) G-LVQ

2.1.4 高斯混合聚类(Mixture-of-Gaussian)

2.2 基于密度的聚类

2.2.1 DBSCAN

2.2.2 OPTICS

2.3 层次聚类方法

2.3.1 AGNES

3 聚类效果评价指标

互信息(Mutual information)

标准化互信息(NMI, Normalized Mutual Information)

调整互信息(AMI, Adjusted Mutual Information)

Python实现

参考