事件图谱应用的一个重要组成部分是事件演化挖掘，从技术实现上来看，文本聚类是实现话题发现的第一个阶段性工作。文本聚类的目的是把不同的文本（资讯和标题），按照它们的相似与相异度分割成不同的类簇，确保相同簇中的数据尽可能相似，而不同簇里的数据尽可能相异。

本篇文章从聚类的定义、常用的聚类算法、聚类算法实例来讲解聚类。

聚类

什么是聚类？

聚类(Clustering)是按照某个特定标准(如距离)把一个数据集分割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大，同时不在同一个簇中的数据对象的差异性也尽可能地大。也即聚类后同一类的数据尽可能聚集到一起，不同类数据尽量分离。

聚类和分类的区别？

分类：通过学习来得到样本属性与类标号之间的关系。(有监督学习）就是我们根据已知的一些样本（包括属性与类标号）来得到分类模型（即得到样本属性与类标号之间的函数），然后通过此目标函数来对只包含属性的样本数据进行分类。

聚类：指事先并不知道任何样本的类别标号，希望通过某种算法来把一组未知类别的样本划分成若干类别，聚类的时候，我们并不关心某一类是什么，我们需要实现的目标只是把相似的东西聚到一起，这在机器学习中被称作无监督学习。

聚类算法

聚类算法：K-means聚类

k-means算法以k作为参数，把N个样本对象分成K个簇，使簇内具有较高的相似度，而簇间的相似度较低。

算法流程：

选择 K 个初始质心(K需要用户指定），初始质心随机选择即可，每一个质心为一个类
对剩余的每个样本点，计算它们到各个质心的欧式距离，并将其归入到相互间距离最小的质心所在的簇。
在所有样本点都划分完毕后，根据划分情况重新计算各个簇的质心所在位置，然后迭代计算各个样本点到各簇质心的距离，对所有样本点重新进行划分。
重复第二、三步，直到质心不在发生变化。

下面用一张图来说明

聚类算法：DBSCAN聚类

DBSCAN是一种基于密度的聚类算法，可以根据样本分布的紧密程度决定，同一类别的样本之间是紧密相连的，不同类别样本联系是比较少的。

重要参数：

eps (ε)：一种距离度量，用于定位任何点的邻域内的点。
minPts：聚类在一起的点的最小数目，超过这一阈值才算是一个族群

算法流程：

算法通过任意选取数据集中的一个点（直到所有的点都访问到）来运行。
如果在该点的“ε”半径范围内至少存在“minPoint”点，那么认为所有这些点都属于同一个聚类。
通过递归地重复步骤1、步骤2 对每个相邻点的邻域计算来扩展聚类。

下面用一张图来说明

聚类算法：层次聚类

层次聚类算法有两种类型：凝聚的（Agglomerative）层次聚类和分裂的（Divisive）层次聚类。

凝聚的 - 从下至上的聚类：将每一个数据样本作为一个独立的簇。在每一次迭代中将相似的簇合并起来，直到整个数据集结成成一个簇或多个簇。

分裂的 - 从上至下的聚类：将所有的数据样本作为一个整体的簇。在每一次迭代中把最不相似的簇分离出整体。最后我们将得到K个簇。

这里以从下至上的层次聚类来讲解

算法流程：

给定要聚类的N的对象以及N*N的距离矩阵(或者是相似性矩阵), 层次式聚类方法的基本步骤如下:

将每个对象归为一类, 共得到N类, 每类仅包含一个对象. 类与类之间的距离就是它们所包含的对象之间的距离。
找到最接近的两个类并合并成一类, 于是总的类数少了一个。
重新计算新的类与所有旧类之间的距离。

重复第2步和第3步, 直到最后合并成一个类为止(此类包含了N个对象).

根据步骤3的不同, 类与类之间的距离计算有三种方法: single-linkage, complete-linkage 以及 average-linkage 。

1.Single Linkage 这个算法是以类之间的最短距离为衡量标准的这个算法将以点Pi到点Pj的距离作为类C1和类C2的距离

2.Complete Linkage 它是以类之间的最长距离为衡量标准的这个算法将以点Pi到点Pj的距离作为类C1和类C2的距离

3.Average Linkage 这个算法是计算两个类之间所有点的距离的平均算C1和C2里3个点的两两距离，然后把他们累加求平均

聚类算法：Single-pass

Single-pass”这个算法的名字，大概是“只遍历一回”。它不需要向k-means那样迭代每一个样本的状态，计算速度非常快。，它可以很好的应用于在线事件监测等社交媒体大数据领域，特别适合流式数据（Streaming Data），比如微博的帖子信息，因此适合对实时性要求较高的文本聚类场景。

算法流程：

遍历第1篇文档，没有与其他簇匹配，以1号文档为核心定义了一个新的簇

遍历第2篇文档，它和1号簇非常匹配，认为它俩描述了同一个主题，因此把2号文档添加到了1号簇中

然后是3号文档。它和所有的簇都不够匹配，描述了一个新的主题。因此，我以3号文档为核心定义了一个新的簇

聚类算法示例

K-means聚类算法示例

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
from sklearn.datasets import make_blobs   #生成数据函数
from sklearn import metrics#生成平面数据点+标准化
n_samples = 1500
X,y = make_blobs(n_samples=n_samples,centers=4,random_state=170)
X = StandardScaler().fit_transform(X)  #标准化#调用kmeans包
Kmeans=KMeans(n_clusters=4,random_state=170)
Kmeans.fit(X)#可视化效果
plt.figure(figsize=(12,6))
plt.subplot(121)
plt.scatter(X[:,0],X[:,1],c='r')
plt.title("聚类前数据图")
plt.subplot(122)
plt.scatter(X[:,0],X[:,1],c=Kmeans.labels_)
plt.title("聚类后数据图")
plt.show()

运行结果：

DBSCAN聚类示例

import numpy as np
from sklearn.cluster import DBSCAN
from sklearn import metrics
from sklearn.datasets._samples_generator import make_blobs
from sklearn.preprocessing import StandardScaler
import matplotlib.pyplot as plt
import seaborn as sns  # 可视化库# 生成聚类中心点
centers = [[1, 1], [-1, -1], [1, -1]]
# 生成样本数据集
X, labels_true = make_blobs(n_samples=750, centers=centers, cluster_std=0.4, random_state=0)
# 画布设置
fig = plt.figure(figsize=(12, 5))
fig.subplots_adjust(left=0.02, right=0.98, bottom=0.05, top=0.9)
ax = fig.add_subplot(1, 2, 1)
row, _ = np.shape(X)
# 画子图，未聚类点
for i in range(row):ax.plot(X[i, 0], X[i, 1], '#4EACC5', marker='.')# StandardScaler 标准化处理。且是针对每一个特征维度来做的，而不是针对样本。
X = StandardScaler().fit_transform(X)
# 调用密度聚类  DBSCAN
db = DBSCAN(eps=0.3, min_samples=10).fit(X)
# print(db.labels_)  # db.labels_为所有样本的聚类索引，没有聚类索引为-1
# print(db.core_sample_indices_) # 所有核心样本的索引core_samples_mask = np.zeros_like(db.labels_, dtype=bool)  # 设置一个样本个数长度的全false向量
core_samples_mask[db.core_sample_indices_] = True  # 将核心样本部分设置为true
labels = db.labels_n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0)
# 获取聚类个数。（聚类结果中-1表示没有聚类为离散点）# 模型评估
print('估计的聚类个数为: %d' % n_clusters_)
print("同质性: %0.3f" % metrics.homogeneity_score(labels_true, labels))  # 每个群集只包含单个类的成员。
print("完整性: %0.3f" % metrics.completeness_score(labels_true, labels))  # 给定类的所有成员都分配给同一个群集。
print("V-measure: %0.3f" % metrics.v_measure_score(labels_true, labels))  # 同质性和完整性的调和平均
print("调整兰德指数: %0.3f" % metrics.adjusted_rand_score(labels_true, labels))
print("调整互信息: %0.3f" % metrics.adjusted_mutual_info_score(labels_true, labels))
print("轮廓系数: %0.3f" % metrics.silhouette_score(X, labels))sns.set(font='SimHei', style='ticks')unique_labels = set(labels)
colors = [plt.cm.Spectral(each) for each in np.linspace(0, 1, len(unique_labels))]ax = fig.add_subplot(1, 2, 2)
for k, col in zip(unique_labels, colors):if k == -1:  # 聚类结果为-1的样本为离散点# 使用黑色绘制离散点col = [0, 0, 0, 1]class_member_mask = (labels == k)  # 将所有属于该聚类的样本位置置为truexy = X[class_member_mask & core_samples_mask]  # 将所有属于该类的核心样本取出，使用大图标绘制ax.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=tuple(col), markeredgecolor='k', markersize=14)xy = X[class_member_mask & ~core_samples_mask]  # 将所有属于该类的非核心样本取出，使用小图标绘制ax.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=tuple(col), markeredgecolor='k', markersize=6)plt.title('Estimated number of clusters: %d' % n_clusters_)
sns.despine()
plt.show()

运行结果：

从下至上层次聚类示例

import numpy as np
from scipy.cluster.hierarchy import dendrogram, linkage, fcluster
from matplotlib import pyplot as plt
data = np.array([[1, 2], [2, 3], [-3, 3], [-2, -1], [5, -1]])
# 画点
plt.scatter(x=data[:, 0:1], y=data[:, 1:2], marker='.', color='red')
n = np.arange(data.shape[0])
for i, txt in enumerate(n):plt.annotate(txt, (data[i:i + 1, 0:1], data[i:i + 1, 1:2]))
plt.show()
# linkage方法用于计算两个聚类簇s和t之间的距离d(s,t)
# 层次聚类编码为一个linkage矩阵。
Z = linkage(data, 'average')
print("聚类过程：", Z)
# 将层级聚类结果以树状图表示出来
dn = dendrogram(Z)
plt.show()

运行结果：