实验项目六  基于K-means和DBSCAN的聚类分析

实验目的

1. 通过不同数据集，学会调用k-means、DBSCAN算法
2. 能够自己编写k-means算法

算法原理

1、k-means算法原理

K-Means是一种基于距离的聚类算法，将距离比较近的数据点看作相似的点，将它们归为一类。对于给定样本集，按照样本之间的距离大小，将样本集划分为K KK个簇。目标是让簇内的点尽量连接在一起，而让簇间的距离尽量大。

①、首先，随机确定k个初始点的质心；

②、然后将数据集中的每一个点分配到一个簇中，即为每一个点找到距其最近的质心，并将其分配给该质心所对应的簇；

③、对每一个簇，计算簇中所有点的均值并将均值作为质心（例：在三维空间里，计算各个点的x的均值得到x1，y的均值得到y1，z的均值得到z1，以此得到新的坐标点 x1,y1,z1,然后重新计算各个点距离最近的族）

④、重复步骤（2），（3），直到没有变化为止

  2、DBSCAN算法原理

DBSCAN是一种基于密度的聚类算法，可以通过样本分布的紧密程度决定，同一类别的样本之间是紧密相连的，不同样本是是分离的。它将特征空间中足够密集的点划分为同一个簇，簇的形状可以是任意的，而且数据点中有噪声点的话，不会将这些点划分给某个簇。

3、手肘法

手肘法的基本思想是，对于不同的聚类数量k，计算聚类结果的评估指标（如误差平方和SSEP。然后，通过绘制聚类数量与评估指标之间的关系曲线，我们可以找到一个”肘点“，即曲线出现明显弯曲的位置。该肘点对应的聚类数量被认为是最佳的聚类数量。

4、轮廓系数法

轮廓系数法是一种常用的聚类验证方法，用于衡量聚类结果的质量。

轮廓系数的计算公式为：s= (b-a)/max(a,b)

其中，a是指的簇内平均距离，b指的簇间平均距离，s的取值范围在[-1,1]，s接近于1，表明聚类结果较优；s接近于0，表明聚类结果不明确；s接近于-1，表明聚类结果较差。

实验内容

一、人工数据集

代码

from numpy import unique,where from matplotlib import pyplot as plt from sklearn.cluster import KMeans,DBSCAN from sklearn import datasets plt.rcParams['font.sans-serif']=['SimHei']  #设置字体 plt.rcParams['axes.unicode_minus']=False    #设置字体 #可视化展示 def data_show(X,y):     plt.scatter(X[:,0],X[:,1],c=y,cmap='rainbow')     plt.title("原数据可视化")     plt.show()     def K_means(X,k):     #kmeans训练，n_clusters:聚类中心数量，fit函数预测     y_pred=KMeans(n_clusters=k,random_state=9).fit_predict(X)     #可视化展示     plt.scatter(X[:,0],X[:,1],c=y_pred)     plt.title("K-means聚类后的可视化")     plt.show()     def _DBSCAN(X):     #esp为领域半径，min_samples为成为核心对象的在领域半径内最少点数     model=DBSCAN(eps=0.3,min_samples=10)     #模型拟合与聚类预测     yhat=model.fit_predict(X)     #去除重复的聚类核心，检索唯一群集     clusters=unique(yhat)     #为每个群集的样本创建散点图     for clusters in clusters:#获取此群集的示例的行索引         row_ix=where(yhat==clusters)         plt.scatter(X[row_ix,0],X[row_ix,1])     plt.title("DBSCAN聚类后的可视化")     plt.show()     def test(X,y):     data_show(X,y)     K_means(X,3)     K_means(X,4)     _DBSCAN(X) if __name__ == '__main__':     n_samples=1500 #样本量     # 生成两个簇月亮数据集，加上随机噪声noise     X_moons,y_moons=datasets.make_moons(n_samples=n_samples,noise=0.05)     #生成三个簇的数据     X_blobs,y_blobs=datasets.make_blobs(n_samples=n_samples)     test(X_blobs,y_blobs) test(X_moons,y_moons

图1 聚类前三个簇数据                 图2 聚类前月亮数据集

图3 k为3，Kmeans聚类后三个簇数据      图4 k为3，kmeans聚类后月亮数据集

图5 k为4，Kmeans聚类后三个簇数据      图6 k为4，kmeans聚类后月亮数据集

根据图3、4、5、6可知，KMeans算法对于make_blobs()生成的球形簇的聚类效果更加好，而对make_moons()生成的月亮形簇的聚类效果并不理想。这是因为KMeans算法仅考虑到最近簇中心的距离，无法处理非球形的簇，所以它对月亮形簇进行了错误的分类。此外，对于三个球形簇，k值选为3的聚类效果比k值选为4的聚类效果更好，因此k值的选择十分重要。

根据图7、8可知，DBSCAN算法对两种类型的簇的聚类效果都不错，因为它不断根据给定的eps和min_samples确定所有的核心点，并对每一个核心点查找密度可达的样本生成聚类簇，从而达到良好的聚类效果。左图中，DBSCAN对于球形簇的聚类，eps设置为1，导致一个簇样本量过大；右图中，DBSCAN对于月亮形簇的聚类，eps设置为0.3，聚类效果很好。此外，若是eps设置得过小，则意味着没有点是核心样本，可能会导致所有点被标记为噪声；若是eps设置得过大，则可能导致所有点形成单个簇。因此，eps的设定尤为重要，对于不同的样本需要进行相应的更改。

      

图7 DBSCAN聚类后三个簇数据          图8 DBSCAN聚类后月亮数据集

二、真实数据集

代码

from sklearn.datasets import load_iris

import pandas as pd

import matplotlib.pyplot as plt

plt.rcParams['font.sans-serif']=['SimHei']  #设置字体

plt.rcParams['axes.unicode_minus']=False    #设置字体

def sklearn_to_df(sklearn_dataset): #将数据集转为DataFrame类型

    df = pd.DataFrame(sklearn_dataset.data, columns=sklearn_dataset.feature_names)

    df['target'] = pd.Series(sklearn_dataset.target) #创建标签并存入df['target']

return df

def iris_box(data): #检查数据完整性,将4维特征使用箱图进行可视化：

    columns = data.feature_names

    iris = pd.DataFrame(data.data, columns=columns)

    iris.plot.box(title="iris")

    plt.grid(linestyle="--", alpha=0.3)

    plt.show()

import numpy as np

def PCA(X, n_components):

    x_mean = np.mean(X, axis=0)     # 中心化数据

    x_centered = X - x_mean

    cov_matrix = np.cov(x_centered, rowvar=False)     # 计算协方差矩阵

    eigenvalues, eigenvectors = np.linalg.eig(cov_matrix)     # 计算特征值和特征向量

    index = np.argsort(-eigenvalues)     # 对特征值进行排序

    # 选择best_component个主成分计算载荷矩阵

    P = np.array(eigenvectors.T[index[:n_components]]).T

    T = np.dot(x_centered, P)     # 计算得分矩阵

    return T,P

def PCA_Show(X, Y):

    x = np.array(X)[:, 0]

    y = np.array(X)[:, 1]

    plt.scatter(x, y, c=Y)

    plt.title('PCA降维后的iris数据集')

    plt.show()

from sklearn import cluster

from sklearn.neighbors import kneighbors_graph

from sklearn.cluster import KMeans,DBSCAN

from numpy import unique,where

def K_means(X,k):

    #kmeans训练，n_clusters:聚类中心数量，fit函数预测

    y_pred=KMeans(n_clusters=k,random_state=9).fit_predict(X)

    plt.scatter(X[:,0],X[:,1],c=y_pred)     #可视化展示

    plt.title("K-means聚类后的可视化")

    plt.show()

def _DBSCAN(X):

    model=DBSCAN(eps=0.3,min_samples=10) #esp为领域半径，min_samples为成为核心对象的在领域半径内最少点数

    yhat=model.fit_predict(X)     #模型拟合与聚类预测

    clusters=unique(yhat) #去除重复的聚类核心，检索唯一群集

    for clusters in clusters:#获取此群集的示例的行索引

        row_ix=where(yhat==clusters)

        plt.scatter(X[row_ix,0],X[row_ix,1])     #为每个群集的样本创建散点图

    plt.title("DBSCAN聚类后的可视化")

    plt.show()

def test(X,y):

    K_means(X,3)

    K_means(X,4)

    _DBSCAN(X)

from sklearn import datasets, metrics

def k_Kmeans(X, y):

    RMSE = []  # 存放每次结果的误差平方和

    for k in range(1, 9):

        estimator = KMeans(n_clusters=k)  # 构造聚类器

        estimator.fit(X)

        mse = metrics.v_measure_score(y, estimator.labels_)

        RMSE.append(mse)

    X = range(1, 9)

    plt.xlabel('簇k的值')

    plt.ylabel('每个簇值的误差平方和')

    plt.title('选取最合适的簇值')

    plt.plot(X, RMSE, 'o-')

    plt.show()

def score_bar(X, y):

    RMSE = []

    bandwidth = cluster.estimate_bandwidth(X, quantile=0.3)

    connectivity = kneighbors_graph(X, n_neighbors=10, include_self=False)

    connectivity = 0.5 * (connectivity + connectivity.T)

    # 构造聚类器

    estimator_kmeans = cluster.KMeans(n_clusters=2)

    estimator_dbscan = cluster.DBSCAN(eps=.2)

    # 逐一计算v_measure_score

    labels = [estimator_kmeans, estimator_dbscan]

    for estimator in labels:

        estimator.fit(X)

        mse = metrics.v_measure_score(y, estimator.labels_)

        RMSE.append(mse)

    clustering_names = ['KMeans', 'DBSCAN']     # 可视化

    plt.bar(clustering_names, RMSE, 0.4, color="blue")

    plt.xlabel('聚类器名字')

    plt.ylabel("聚类器性能")

    plt.title("聚类器性能对比柱状图")

    plt.show()

if __name__ == '__main__':

    iris_data = load_iris()      # 载入iris数据集

    df_iris = sklearn_to_df(iris_data)  # 调用sklearn_to_df转换数据类型

    df_iris.info()  # 查看数据基本信息

    iris_box(iris_data)  # 四维箱图

    x = iris_data.data  # x为iris数据

    y = iris_data.target  # y为iris标签特征

    T, P = PCA(x, 2) # 将数据降至2维

    PCA_Show(T, y) # 输出降至二维后的散点图

    test(T,y)   # 进行K-means、DBSCAN聚类分析

    k_Kmeans(T, y)     #选取最合适的簇值

score_bar(T, y)     #聚类器性能对比

图9、iris数据集情况                  图10、箱图可视化属性值

数据完整性可由info()函数现实的结果Non-Null Count得知，每一个属性对应的数据都为150个样本，non-null即为无缺失，数据完整。箱图中，对于每一个属性，横线自上而下对应的纵坐标分别为上限、上四分位数、中位数、下四分位数、下限，小圆圈为异常值，可以看到数据异常值很少。

          

图11、PCA降维后的iris数据集         图12、k=3时k-means聚类

      

图13、k=4时 k-means聚类                    图14、DBSCAN聚类

可以看到k=3时k-means聚类比较符合事实，k=4时k-means聚类和DBSCAN聚类效果不太好。

     

图15、k-means聚类时选择最合适的簇   图16、聚类器性能对比柱状图

从图15可以看到k值为3时是最合适的簇，图16也可以得到结论对于iris数据集使用k-means数据集效率比较高。

三、复现k-means算法

伪代码

kmeans()：

input: data, k, max_iter

output: centroids, cluster_assignment, sse

steps: 1、centroids = data[np.random.choice(data.shape[0], k, replace=False)] 2、cluster_assignment = -np.ones（） 3、for i in range(max_iter): 4、   broad_centroids = centroids[:, np.newaxis] 5、   distances = np.sqrt(((data - broad_centroids) ** 2).sum(axis=2)) 6、   new_cluster_assignment = np.argmin(distances) 7、   if np.array_equal(new_cluster_assignment, cluster_assignment) 8、       sse = ((data - centroids[new_cluster_assignment]) ** 2).sum() 9、   for j in range(k): 10        centroids[j] = data[new_cluster_assignment == j].mean(axis=0) 11、cluster_assignment = new_cluster_assignment 12、sse = ((data - centroids[new_cluster_assignment]) ** 2).sum()

SSE():

input: data

output:k

steps: 1、Ks = range(1, 11) 2、    sses = [] 3、    for k in Ks: 4、        sse = kmeans(data, k)[2] 5、        sses.append(sse)

silhouette ()：

input: data

output: show()

steps: 1、silhouette_scores = [] 2、    for k in range(2, 10): 3、        y_pred = KMeans(n_clusters=k, random_state=9).fit_predict(x) 4、        silhouette_scores.append(silhouette_score(x, y_pred))

代码

import numpy as np

import matplotlib.pyplot as plt

from sklearn.datasets import load_iris

from sklearn.decomposition import PCA

from sklearn.metrics import silhouette_score

from sklearn.cluster import KMeans

plt.rcParams['font.sans-serif'] = 'SimHei'  # 使图形中的中文正常编码显示（黑体）

plt.rcParams['axes.unicode_minus'] = False  # 使坐标轴刻度表签正常显示正负号

def kmeans(data, k, max_iter=300):

    # 从数据中随机选择k个样本作为初始的聚类中心点

    centroids = data[np.random.choice(data.shape[0], k, replace=False)] #centroids :k个聚类中心点的坐标

    # 初始化每个样本所属的簇的标签为-1

    cluster_assignment = -np.ones(data.shape[0], dtype=int)

    for i in range(max_iter):

        # 计算每个样本到k个聚类中心点的距离

        broad_centroids = centroids[:, np.newaxis]

        distances = np.sqrt(((data - broad_centroids) ** 2).sum(axis=2))

        # 通过最小距离确定每个样本所属的簇的标签

        new_cluster_assignment = np.argmin(distances, axis=0)

        # 如果聚类结果不再改变，则直接返回

        if np.array_equal(new_cluster_assignment, cluster_assignment):

            sse = ((data - centroids[new_cluster_assignment]) ** 2).sum()

            return centroids, cluster_assignment, sse

        # 更新聚类中心点的坐标

        for j in range(k):

            centroids[j] = data[new_cluster_assignment == j].mean(axis=0)

        # 更新每个样本所属的簇的标签

        cluster_assignment = new_cluster_assignment

    sse = ((data - centroids[new_cluster_assignment]) ** 2).sum()

    return centroids, cluster_assignment, sse

def SSE(data): #手肘法

    # 计算不同k值下的SSE值

    Ks = range(1, 11)

    sses = []

    for k in Ks:

        sse = kmeans(data, k)[2]

        sses.append(sse)

    # 可视化SSE

    plt.plot(Ks, sses, 'bx-')

    plt.xlabel('簇的值')

    plt.ylabel('SSE')

    plt.title('手肘法选择最适合k')

    plt.show()

    k = eval(input("请输入合适的k:"))

    return k

def silhouette(x): #轮廓系数法

    silhouette_scores = []

    for k in range(2, 10):

        y_pred = KMeans(n_clusters=k, random_state=9).fit_predict(x)

        silhouette_scores.append(silhouette_score(x, y_pred))

    print(silhouette_scores)

    plt.plot(range(2, 10), silhouette_scores, 'bx-')

    plt.xlabel('簇的值')

    plt.ylabel('轮廓系数')

    plt.title('轮廓系数方法')

    plt.show()

# 可视化结果

def draw(data,centroids, cluster_assignment, k):

    colors = ['r', 'g', 'b', 'c', 'm', 'y', 'k', 'w']

    for i in range(k):

        plt.scatter(data[cluster_assignment == i, 0],data[cluster_assignment == i, 1],c=colors[i], label=f'簇 {i + 1}')

    plt.scatter(centroids[:, 0],centroids[:, 1],marker='x',c='k',s=100,label='中心点')

    plt.legend()

    plt.show()

if __name__ == '__main__':

    iris_data = load_iris()  #导入数据集

    x = iris_data.data  # x为iris数据

    y = iris_data.target  # y为iris标签特征

    data = PCA(n_components=2).fit_transform(x) #预处理：PCA降维

    k=SSE(data) #选择最适合k簇

    silhouette(data)

    centroids, cluster_assignment, see = kmeans(data, k)   # kmeans聚类

draw(data,centroids, cluster_assignment, k) #可视化

图17 手肘法选择最合适的簇值      图18轮廓系数法选择最合适的簇值

通过SSE图可明显看出拐点（肘部）的簇数量是3，与鸢尾花数据集的类别是吻合的。

图19 3个簇的k-means聚类分析

实验心得

1、k-means与DBSCAN的区别

①、K-Means是基于划分的聚类，DBSCAN是基于密度的聚类。

②、K-Means需要指定聚类簇数k，并且初始聚类中心对聚类影响很大。K-Means把任何点都归到了某一个类，对异常点比较敏感。DBSCAN能剔除噪声，需要指定邻域距离阈值ϵ和样本个数阈值Min，可以自动确定簇个数，不需要输入类别k。

③、K-Means可以发现不是明显分离的簇，即便簇有重叠也可以发现，但是DBSCAN会合并有重叠的簇。

④、K-Means很难处理非球形的簇和不同大小的簇。DBSCAN可以处理不同大小或形状的簇，并且不太受噪声和离群点的影响。当簇具有很不相同的密度时，两种算法的性能都很差。

⑤K-Means只能用于具有明确定义的质心（比如均值或中位数）的数据。DBSCAN要求密度定义（基于传统的欧几里得密度概念）对于数据是有意义的。

2、对于各样本点到质心的距离计算，我采用了欧氏距离，欧氏距离为k—means算法的最常用距离计算方式。

        # 计算每个样本到k个聚类中心点的距离

        broad_centroids = centroids[:, np.newaxis]

    distances = np.sqrt(((data - broad_centroids) ** 2).sum(axis=2))

在计算距离时，我想通过Numpy广播机制来简化代码，高效计算，但这要求维数相同，且各维度的长度相同。所以我首先将centroids数组从原来的一维数组扩展为二维数组，使其能够与data数组进行逐元素的操作。这里使用了NumPy的广播规则，该规则会自动将较小的数组沿着缺失的维度进行扩展，以使得两个数组具有相同的形状。然后，计算data中每个数据点与每个质心之间的差值的平方，此时得到一个shape:（2，150，2）数组，使用sum函数在第二个维度上对所有差值的平方进行求和，最后取平方根。这样就得到了一个二维数组，其中第一维(行)表示centroids数组中的每个质心，第二维（列）表示data数组中的每个元素表示一个质心和一个数据点之间的欧式距离。

3、通过本次实验，我了解了如何使用python产生不同的数据簇，也初步理解了K-means、DBSCAN算法的基本原理、区别以及适用的数据簇类型。此外，我对数据可视化、数据基础信息获取、箱图、K-means算法的k值选取、聚类性能评估产生了初步的认识。

学会了如何将使用K-means和DBSCAN算法对数据进行聚类，了解到K-means算法只适用于球形簇，而DBSCAN算法的适用领域更大。此外，我还了解到K-means算法需要选取适合的k值，这个可以通过手肘法和轮廓系数法获得，而DBSCAN算法需要设置适合的eps，才能获得更好的聚类性能。学会了使用metrics.v_measure_score函数来计算聚类效益，通过这样的分析可以确定数据簇应当采用哪一种算法进行聚类，也可以帮助判断算法参数的选择。