第一题：使用sklearn的DBSCAN和AgglomerativeClustering完成聚类
实验内容：
1. 导入模块
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
import warnings
warnings.filterwarnings('ignore')
2. 生成数据集
from sklearn import datasets
X1, y1 = datasets.make_circles(n_samples = 1500, factor = 0.5, noise = 0.05, random_state = 32)
X2, y2 = datasets.make_moons(n_samples = 1500, noise = 0.05, random_state = 32)
colors = np.array(['#377eb8', '#ff7f00', '#4daf4a', '#f781bf', '#a65628', '#984ea3', '#999999', '#e41a1c', '#dede00'])
plt.title('dataset1')
plt.scatter(X1[:, 0], X1[:, 1], s = 10, c = colors[y1])
plt.title('dataset2')
plt.scatter(X2[:, 0], X2[:, 1], s = 10, c = colors[y2])
3. 导入模型
from sklearn.cluster import DBSCAN, AgglomerativeClustering
4. 训练模型
dbscan = DBSCAN(eps = 0.1)
dbscan.fit(X1)
密度聚类模型使用模型的labels_属性就可以获得聚类后的类标记
dbscan.labels_
层次聚类的linkage参数表示我们要用哪种距离（最小、最大、平均）进行聚类。这里我们选择single，表示最小距离。complete表示最大距离，average表示平均距离。
注意：single参数是在sklearn 0.20版本才加入的！
agg = AgglomerativeClustering(n_clusters = 2, linkage="single")
agg.fit(X1)
5. 聚类结果可视化
plt.figure(figsize = (8, 4))
plt.subplot(121)
plt.title('DBSCAN dataset1')
plt.scatter(X1[:, 0], X1[:, 1], s = 10, c = colors[dbscan.labels_])
plt.subplot(122)
plt.title('AGG dataset1')
plt.scatter(X1[:, 0], X1[:, 1], s = 10, c = colors[agg.labels_])
6. 指标计算
我们这里选用两个外部指标，FMI和NMI。
互信息(mutual information)表示了两个分布的一致程度。归一化的互信息(NMI)将互信息值映射到0到1的空间内。值越高，说明两个分布的一致性越高。
FMI是Fowlkes-Mallows index，使用precision和recall计算得到，其值域也是0到1，越大说明聚类效果越和参考模型相近。
from sklearn.metrics import normalized_mutual_info_score
from sklearn.metrics import fowlkes_mallows_score
normalized_mutual_info_score(y1, dbscan.labels_)
normalized_mutual_info_score(y1, agg.labels_)
fowlkes_mallows_score(y1, dbscan.labels_)
fowlkes_mallows_score(y1, agg.labels_)
Test
请你使用密度聚类和高斯混合模型在数据集X2上进行聚类，绘制聚类后的效果。计算FMI和NMI值，填入下标
双击此处填写
()
| 算法 | FMI | NMI |
|---|---|---|
| 密度聚类 | 0.9987 | 0.9934 |
| 高斯混合模型 | 0.7475 | 0.3952 |
from sklearn.mixture import GaussianMixture
# 密度聚类 (DBSCAN)
dbscan = DBSCAN(eps=0.1)
dbscan_labels = dbscan.fit_predict(X2)
# 高斯混合模型 (Gaussian Mixture Model)
gmm = GaussianMixture(n_components=2, random_state=32)
gmm_labels = gmm.fit_predict(X2)
# 绘制密度聚类效果
plt.figure(figsize=(12, 5))
plt.subplot(1, 2, 1)
plt.scatter(X2[:, 0], X2[:, 1], c=colors[dbscan_labels], cmap='viridis', s=50)
plt.title('DBSCAN Clustering')
# 绘制高斯混合模型效果
plt.subplot(1, 2, 2)
plt.scatter(X2[:, 0], X2[:, 1], c=colors[gmm_labels], cmap='viridis', s=50)
plt.title('Gaussian Mixture Model Clustering')
plt.show()
# 计算 FMI 和 NMI 值
fmi_dbscan = fowlkes_mallows_score(y2, dbscan_labels)
nmi_dbscan = normalized_mutual_info_score(y2, dbscan_labels)
fmi_gmm = fowlkes_mallows_score(y2, gmm_labels)
nmi_gmm = normalized_mutual_info_score(y2, gmm_labels)
print(f"密度聚类 - Fowlkes Mallows Index: {fmi_dbscan:.4f}")
print(f"密度聚类 - Normalized Mutual Info: {nmi_dbscan:.4f}")
print()
print(f"高斯混合模型 - Fowlkes Mallows Index: {fmi_gmm:.4f}")
print(f"高斯混合模型 - Normalized Mutual Info: {nmi_gmm:.4f}")
第二题：实现K-means
实验内容：
我们要实现一个K-means算法，也称为原型聚类算法。
## 初始化
K-means在实现的时候，首先需要选取类簇中心。类簇中心的选取方法有很多，我们这里使用最简单的方法，随机选取。也就是，从给定的待聚类的样本中，随机选取 $K$ 个样本，作为 $K$ 个类簇的中心。
## 优化
选取类中心后，就需要不断的调成类中心的位置，开始优化过程，优化主要分为两步：
### 第一步
计算所有样本到 $K$ 个类中心的距离。每个样本，选择距自己最近的类中心作为自己属于的类簇。（这里的距离我们选择欧式距离）
### 第二步
针对第一步分出来的 $K$ 个类簇，计算每个类簇内样本的均值，将计算得到的 $K$ 个均值向量，作为这 $K$ 个类簇新的中心。
### 然后循环第一步和第二步，直至一定的迭代次数，或类中心无显著的位置改变为止。
1. 导入模块
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
import warnings
warnings.filterwarnings('ignore')
2. 生成数据集
from sklearn.datasets import make_blobs
X, y = make_blobs(n_samples = 1500, random_state = 170)
这里的X和y分别代表样本和对应的真实标记。
使用plt.scatter绘制散点图，参数c是一个np.ndarray，表示类别，相同的值会有相同的颜色。
plt.scatter(X[:, 0], X[:, 1], c = y)
3. 欧式距离的实现
给定向量 x ∈ R m x \in \mathbb{R}^m x∈Rm， y ∈ R m y \in \mathbb{R}^m y∈Rm，两个向量的欧式距离定义为：
E ( x , y ) = ∑ i = 1 m ( x i − y i ) 2 E(x, y) = \sqrt{\sum^m_{i = 1} (x_i - y_i)^2} E(x,y)=i=1∑m(xi−yi)2
其中, i i i 表示向量的第 i i i 个分量。
我们要实现一个可以计算多个样本组成的矩阵 X X X，与某一个类中心 y y y 之间欧氏距离的函数。
给定输入矩阵 X ∈ R n × m X \in \mathbb{R}^{n \times m} X∈Rn×m，其中 n n n 是样本数， m m m 是特征数，给定输入的类簇中心 y ∈ R m y \in \mathbb{R}^m y∈Rm。
我们要计算 n n n 个样本到某一类簇中心 y y y 的欧式距离，最后的结果是 E ∈ R n E \in \mathbb{R}^{n} E∈Rn，每个元素表示矩阵 X X X 中的每个样本到类中心 y y y 的欧式距离。
def compute_distance(X, y):
'''
计算样本矩阵X与类中心y之间的欧氏距离
Parameters
----------
X, np.ndarray, 样本矩阵 X, 维度：(n, m)
y, np.ndarray, 类中心 y，维度：(m, )
Returns
----------
distance, np.ndarray, 样本矩阵 X 每个样本到类中心 y 之间的欧式距离，维度：(n, )
'''
# YOUR CODE HERE
y= np.tile(y, (X.shape[0], 1))
distance = np.sum(((X-y)**2),axis=1)**0.5
return distance
# 测试样例
print(compute_distance(np.array([[0, 0], [0, 1]]), np.array([0, 1]))) # [ 1. 0.]
print(compute_distance(np.array([[0, 0], [0, 1]]), np.array([1, 1]))) # [ 1.41421356 1. ]
下面开始实现K-means聚类算法
class myKmeans:
def __init__(self, n_clusters, max_iter = 100):
'''
初始化，三个成员变量
Parameters
----------
n_clusters: int, 类簇的个数
max_iter, int, default 100, 最大迭代轮数，默认为100
'''
# 表示类簇的个数
self.n_clusters = n_clusters
# 表示最大迭代次数
self.max_iter = int(max_iter)
# 类簇中心
self.centroids = None
def choose_centroid(self, X):
'''
选取类簇中心
Parameters
----------
X: np.ndarray, 样本矩阵X，维度：(n, m)
Returns
----------
centroids: np.ndarray, 维度：(n_clusters, m)
'''
centroids = X[np.random.choice(np.arange(len(X)), self.n_clusters, replace = False), :]
return centroids
def compute_label(self, X):
'''
给定样本矩阵X，结合类中心矩阵self.centroids，计算样本矩阵X内每个样本属于哪个类簇
Parameters
----------
X: np.ndarray, 样本矩阵X，维度：(n, m)
Returns
----------
labels: np.ndarray, 维度：(n, )
'''
# 将每个样本到每个类簇中心的距离存储在distances中，每行表示当前样本对于不同的类中心的距离
distances = np.empty((len(X), self.n_clusters))
# 遍历类中心，对每个类中心，计算所有的样本到这个类中心的距离
for index in range(len(self.centroids)):
# 计算样本矩阵X所有样本到当前类中心的距离，存储在distances中的第index列中
# YOUR CODE HERE
distances[:, index] = compute_distance(X, self.centroids[index])
# 取distances每行最小值的下标，这个下标就是这个样本属于的类簇的标记
# YOUR CODE HERE
labels = np.argmin(distances, axis=1)
# 返回每个样本属于的类簇的标记
return labels
def fit(self, X):
'''
聚类，包含类中心初始化，类中心优化两个部分
Parameters
----------
X: np.ndarray, 样本矩阵X，维度：(n, m)
'''
# 类中心随机初始化
self.centroids = self.choose_centroid(X)
# 优化self.max_iter轮
for epoch in range(self.max_iter):
# 计算当前所有样本的属于哪个类簇
labels = self.compute_label(X)
# 重新计算每个类簇的类中心
for index in range(self.n_clusters):
# 重新计算第 index 个类中心，对属于这个类簇的样本取均值
# YOUR CODE HERE
self.centroids[index, :] = X[labels == index].sum(axis=0) / X[labels == index].shape[0]
4. 聚类
# 初始化一个3类簇的模型
model = myKmeans(3)
# 对X进行聚类，计算类中心
model.fit(X)
# 计算X的类标记
prediction = model.compute_label(X)
5. 聚类结果可视化
# 使用我们的预测结果上色
plt.scatter(X[:, 0], X[:, 1], c = prediction)
6. 评价指标
这里，我们选用两个外部指标，FMI和NMI。
from sklearn.metrics import normalized_mutual_info_score
from sklearn.metrics import fowlkes_mallows_score
print(normalized_mutual_info_score(y, prediction))
print(fowlkes_mallows_score(y, prediction))
Test
使用下面提供的数据，完成以下实验：
- 使用myKmeans和层次聚类算法(AgglomerativeClustering)对该数据进行聚类。
- 计算出两个模型的FMI和NMI值，并对聚类结果可视化。
- 分析为什么两个模型的聚类效果会出现如此的不同。
要求：
- 层次聚类的连接方式选择’single’，即使用两个类簇之间的最小距离
- 类簇个数设定为2
完成下表的填写：
双击此处填写
| 算法 | FMI | NMI |
|---|---|---|
| myKmeans | 0.4996 | 0.0003 |
| AgglomerativeClustering | 1.0000 | 1.0000 |
from sklearn.datasets import make_circles
X, y = make_circles(n_samples = 1500, factor = .5, noise = .05, random_state = 32)
plt.scatter(X[:, 0], X[:, 1], c = y)
# 初始化一个2类簇的模型
model_test = myKmeans(2)
# 对X进行聚类，计算类中心
model_test.fit(X)
# 计算X的类标记
prediction = model_test.compute_label(X)
plt.figure(figsize=(12, 4))
plt.subplot(1, 2, 1)
plt.scatter(X[:, 0], X[:, 1], c=y, cmap='viridis', s=40)
plt.title("True Clusters")
plt.subplot(1, 2, 2)
plt.scatter(X[:, 0], X[:, 1], c=prediction, cmap='viridis', s=40)
plt.title("Agglomerative Clustering")
plt.show()
# 计算评估指标
fmi1 = fowlkes_mallows_score(y, prediction)
nmi1 = normalized_mutual_info_score(y, prediction)
print(f"K-means - Fowlkes Mallows Index: {fmi1:.4f}")
print(f"K-means - Normalized Mutual Info: {nmi1:.4f}")
# YOUR CODE HERE
agg2 = AgglomerativeClustering(n_clusters=2, linkage='single')
labels2 = agg2.fit_predict(X)
plt.figure(figsize=(12, 4))
plt.subplot(1, 2, 1)
plt.scatter(X[:, 0], X[:, 1], c=y, cmap='viridis', s=40)
plt.title("True Clusters")
plt.subplot(1, 2, 2)
plt.scatter(X[:, 0], X[:, 1], c=labels2, cmap='viridis', s=40)
plt.title("Agglomerative Clustering")
plt.show()
# 计算评估指标
fmi2 = fowlkes_mallows_score(y, labels2)
nmi2 = normalized_mutual_info_score(y, labels2)
print(f"层次聚类 - Fowlkes Mallows Index: {nmi2:.4f}")
print(f"层次聚类 - Normalized Mutual Info: {nmi2:.4f}")
