专题三：机器学习基础- 无监督学习 聚类算法

tjz001

K-means聚类算法

道理及算法流程

K-means算法是一种常用的基于距离的聚类算法。其基本思想是将样本数据划分为K个类别，使得每个数据点与其所属类此外聚类中心之间的距离最小化，从而达到聚类的目的。具体流程如下：

• 随机选择K个点作为初始聚类中心。
  
• 计算每个数据点与K个聚类中心的距离，并将其归到距离比来的聚类中心的类别中。
  
• 更新聚类中心的位置，将每个聚类中心的位置移动到其类别中所有点的均值位置。
  
• 反复第2和第3步，直到聚类中心不再改变或达到最大迭代次数。
  

K-means算法的优化

K-means算法有以下几个优化方式：

• 随机初始点的选择：可以通过多次随机初始化，选择最小化方针函数的初始化点。
  
• 聚类中心的数量选择：可以通过肘部法例或轮廓系数等方式确定聚类中心的数量。
  
• 迭代遏制的条件：可以通过设置最大迭代次数或设置聚类中心的变化阈值等方式来决定遏制迭代。
  

K-means算法的评估指标

K-means算法的常用评估指标包罗：

• SSE（Sum of Squared Errors）：所有样本点到其所属聚类中心的距离的平方和。
  
• Silhouette系数：计算样本点的聚类效果，取值范围在[-1, 1]之间，值越大暗示聚类效果越好。
  

层次聚类算法

道理及算法流程

层次聚类算法又被称为分级聚类算法，其基本思想是将样本分为分歧的类别，并将类别进行分层次展示。该算法分为两种，一种是自下而上的聚合算法，另一种是自上而下的分裂算法。这里介绍一下自下而上的聚合算法。
层次聚类算法的基本流程如下：

• 将每个样本作为一个初始簇
  
• 计算两个最相似簇之间的相似度
  
• 将最相似的两个簇合并成一个新的簇
  
• 反复法式2和法式3，直到所有样本都被合并到一个簇中
  

层次聚类算法的优化

层次聚类算法的优化主要表此刻两个方面：

• 相似度度量方式的优化：选择合适的相似度度量方式可以提高聚类算法的准确性，凡是采用欧氏距离或余弦相似度进行计算。
  
• 层次聚类的策略优化：在层次聚类算法中，最重要的就是合并簇的策略。常见的策略包罗单连通性、完全连通性、平均连通性等，具体选择哪种策略需要按照实际问题和数据特征进行考虑。
  

层次聚类算法的评估指标

层次聚类算法的评估指标包罗聚类效果和聚类质量两个方面。
聚类效果主要指聚类成果的可视化呈现，通过对聚类成果进行不雅察看和分析，判断聚类成果是否符合实际情况。
聚类质量主要指聚类算法的准确性和不变性，常用的评价指标包罗轮廓系数、Calinski-Harabasz指数、Davies-Bouldin指数等。
密度聚类算法

密度聚类算法是一种基于样本之间的密度来划分簇的聚类算法。对比于K-means和层次聚类算法，它对簇的形状、大小没有先验假设，而且可以发现任意形状的簇。常见的密度聚类算法有DBSCAN和OPTICS算法。
DBSCAN算法

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)算法是一种基于密度的聚类算法，它将必然密度范围内的样本分为同一簇，同时还可以识别出噪声点。
DBSCAN算法主要需要设置两个参数，一个是密度半径(eps)，暗示在这个半径范围内的样本都属于同一簇；另一个是最小样本数(min_samples)，暗示一个簇中最少要有多少个样本。DBSCAN算法的基本流程如下：

• 随机选择一个未被访谒的点p
  
• 搜索p的ε-邻域，如果p的ε-邻域内的点的个数小于min_samples，那么将p标识表记标帜为噪声点。否则将p作为第一个簇的种子点，并标识表记标帜为已访谒。
  
• 以p为中心，继续搜索p的ε-邻域内的点，将这些点插手到第一个簇中，标识表记标帜为已访谒。
  
• 对于第一个簇中的所有点，依次执行法式2、3，直到第一个簇无法再添加新的点为止。
  
• 选择一个未被访谒的点q，反复法式2~4，直到所有的点都被访谒过。
  

DBSCAN算法的长处是可以发现任意形状的簇，而且可以识别出噪声点。但它的错误谬误是对参数的设置斗劲敏感，分歧的参数设置会导致分歧的聚类成果。
下面是使用sklearn库实现DBSCAN算法的代码：

1. from sklearn.cluster import DBSCAN
2. from sklearn.datasets import make_blobs
4. # 生成模拟数据
5. X, y = make_blobs(n_samples=1000, centers=4, random_state=42)
7. # 构建模型
8. dbscan = DBSCAN(eps=0.5, min_samples=5)
10. # 模型拟合
11. dbscan.fit(X)
13. # 获取预测成果
14. labels = dbscan.labels_
16. # 输出聚类成果和噪声点个数
17. n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0)
18. n_noise_ = list(labels).count(-1)
19. print('Estimated number of clusters: %d' % n_clusters_)
20. print('Estimated number of noise points: %d' % n_noise_)

复制代码

OPTICS算法

OPTICS（Ordering Points To Identify the Clustering Structure）算法是一种基于密度的聚类算法，它可以发现任意形状的聚类，而且不需要预先指定聚类个数。与DBSCAN算法类似，OPTICS算法同样可以识别噪声点和离群点。分歧之处在于，OPTICS算法不需要指定半径参数，而是通过成立基于密度可达的点序来发现聚类布局。
OPTICS算法的核心思想是通过定义可达距离（reachability distance）来度量两个样本之间的距离，而不是简单的欧式距离或曼哈顿距离等。对于样本$i$和样本$j$，可达距离reachability_distancei,j的计算方式为：
reachability_distancei,j​=max{core_distancej​,dist(i,j)}
此中，core_distance j ​是样本$j$的核心距离，即样本$j$在以样本$j$为中心，半径为$\epsilon$的超球体内包含的样本数量达到了某个设定的阈值，而dist(i,j)是欧式距离。
对于样本$i$，其邻域$\epsilon$范围内的点调集为N ，而以样本$i$为核心的密度可达距离reachability_distance i​为：


OPTICS算法的主要法式如下：

• 对数据集中的每个样本点，计算其与其他样本点的可达距离，并按照可达距离的大小进行排序。
  
• 以任意一个样本点开始，从小到大遍历已排序的样本点列表。对于每个点p，计算其与已措置的点$q$之间的核心距离core_distance_p，并计算p的可达距离reachability_distance_p。
  
• 在措置完所有样本点后，按照可达距离$reachability_distance$将样本点组织成一个可视化的图形布局，从而得到聚类成果。
  

下面给出使用Python实现OPTICS算法的示例代码：

1. from sklearn.cluster import OPTICS
2. from sklearn.datasets import make_blobs
4. # 创建一个模拟数据集
5. X, y = make_blobs(n_samples=1000, centers=5, random_state=42)
7. # 初始化OPTICS聚类器
8. optics = OPTICS()
10. # 对数据进行聚类
11. optics.fit(X)
13. # 打印出每个样本的聚类标签
14. print(optics.labels_)

复制代码

在这个示例中，我们使用Scikit-learn库中的OPTICS聚类器对一个模拟数据集进行聚类。首先，我们使用make_blobs函数生成一个包含1000个样本和5个聚类中心的数据集。然后，我们初始化OPTICS聚类器并对数据进行聚类。最后，我们打印出每个样本的聚类标签。
请注意，这里的聚类标签与K-means和层次聚类算法分歧，它是一组整数，此中-1暗示离群点。因为OPTICS算法不需要事先指定聚类数量，所以聚类标签的数量取决于数据集的复杂性和噪声程度。