聚类算法

聚类的概念：

1. 聚类是一个无监督问题，我们在分类的时候没有哪一类的标签了

2. 聚类：相似的东西分到了一组

3. 难点：如何评估，如何调参

   

K-MEANS算法

基本概念

1. 要得到簇的个数，需要指定K值，例如上图所示，它的K值就是3

2. 质心：均值，即向量各维度取平均即可，就是各个簇最中心的点

3. 距离的度量：这里有两种方法：

   • 欧氏距离：sqrt[(x1-x2)^2 + (y1-y2)^2 ……]
   • 余弦相似度：以原点为起始点，需要比较的两个点为终止点，做向量，求这两个向量的余弦，余弦约小这两个点越相似
   • 我们一般使用欧氏距离来计算两点的距离
   • 我们在计算的时候应该先吧数据标准化，为了防止不同维度上数据差距，导致的误差，标准化之后，可以让他们变化范围尽可能的缩小，不影响我们计算

4. 要优化的目标：

   ?

   其中最外层的是从1 到 K 相加， 最里层是每一个类中每一个点到质心的距离

   我们想要的是 在每一个类中属于该类的点到该类的质心的距离和最小

工作流程

1. 

   这是我们的初始数据分布图。现在假设我们把它分为两类 K = 2

2. 

   当我们确定分完的类数之后，会随机生成K个点 然后 开始遍历我们的每一个数据点，分别到这K个点的距离，取较小的哪一个然后把它分为哪一类

3. 

   这是我们分完之后出现的类别，计算完之后会初步分成两类

4. 

   ? 分完之后我们就要跟新 质点， 寻找每一类的中心点然后把哪一个点设置为新的质点

5. 

   然后重新进行距离的计算，从新分类

6. 

   分完类之后从新更新质点， 然后在分类，直到质点稳定为止

优势和劣势

• 优势：

  • 简单，快速，适合常规数据集

• 劣势：

  • K值难以确定，如果给你一个分布不均匀的数据集的化，我们很难确定我们要分为几类，我们上面的数据集，是一个特例

  • 复杂度与样本呈现线性关系，因为我们每一次进行迭代的时候会算所有数据到样本点之间的距离，所以我们分的类越多，计算复杂度越高

  • 很难发现任意形状的簇

    

DBSCAN 算法

基本概念：（Density-Based Spatial Clustering of Applications with Noise）

1. 核心对象：若某个点的密度达到算法设定的阈值则其为核心点。（即r邻域内点的数量不小于minPts）

2. 邻域内的距离阈值：设定的半径r

3. 直接密度可达：若点p在点q的r邻域内，且q是核心点，则p-q是直接密度可达

4. 密度可达：若有一个点的序列为q0,q1,q2,q3...qk,对任意的qi - qi-1是直接密度可达的，则称从q0到qk是密度可达的，这实际上是直接密度可达的“传播”

   

   就像这个图我设置其中A表示的红点 都是密度可达的， 其中 BC 表示边界点 N 表示离群点

5. 密度相连，若从某个核心点出发点q和点k都是密度可达的，则称点q和点k是密度相连的

6. 边界点：属于某一个类的非核心点，不能够发展下线了

7. 噪声点：不属于任何一类簇的点，从任何一个核心点出发都是密度不可达的

工作流程

1. 参数的输入
   • 参数D：输入数据集
   • 参数ε ： 指定半径
   • Minpts：密度阈值
2. 工作流程
   1. 标记所有的对象为unvisited(未被访问的)
   2. Do
   3. 随机选择一个 unvisited对象p
   4. 标记p为visited
   5. if p的ε邻域内至少有MinPts个对象
      1. 创建一个新簇C，并把p添加到C中
      2. 令N为p的ε邻域中对象的集合
      3. For N中的每一个点p
         1. if p 是unvisited的
            1. 标记p为visited
            2. if p的ε邻域内至少有Minpta个对象，把这些对象添加到N中
            3. 如果p还不是任何簇中的成员，把p添加到C
      4. EndFor
      5. 输入C
   6. Else 标记p为噪声
   7. Until 没有标记为unvisited的对象
3. 参数的选择
   1. 半径ε可以根据K距离来设定：照突变点，
      1. K距离：给定数据集P = {p(i); i = 0,1,...n},计算p(i)到集合D中子集S中所有点之间的距离，距离按照从小到大的顺序排序，d(k)就被称为k-距离
   2. MinPts：k-距离中的值，一般取小一些，多次尝试

优势和劣势

1. 优势：

   • 不需要指定簇的个数

   • 可以发现任意形状的簇

   • 擅长找到离群点（检测任务）

   • 两个参数就够了

     

2. 劣势：

   • 高维数据有点困难（需要先降维）
   • 参数难以选择（参数对结果的影响非常大）
   • Sklearn 中效率比较慢（数据削减工作）

K-Means算法的实现

我们先创建一个K-Meansl类

import numpy as np

"""
    k - means 算法实现流程
    1. 先创建一个k-means类，这个类的初始化参数是 数据集，要分类的个数
    2. 创建训练函数（通过训练函数来找到最优的质点），需要的参数是数据集和最大迭代次数
    3. 辅助函数：
        从数据集中随机招数 分类个数的 随机数充当质点
        计算所有样本分别属于哪一类
        计算所有样本到这三个质点中的最短距离
"""


class K_Means:
    def __init__(self, data, num_category):
        self.data = data
        self.num_category = num_category

    # 开始训练数据
    def train(self, data, max_iterations):
        print(data[1])

        # 获取 类的个数 的随机点
        centroids = K_Means.random_point(data, self.num_category)

        for i in range(max_iterations):
            # 获取所有数据点分别属于哪一类
            data_category = K_Means.calculation_data_category(data, centroids)
            # 更新质点：
            centroids = K_Means.update_center(data, data_category, self.num_category)
        return centroids, data_category

    @staticmethod
    def random_point(data, num_category):
        # 获取参数的个数
        num_examples = data.shape[0]
        # 这里使用 permutation 函数 这个函数相比于 shuffle的优势在于
        # permutation函数参数可以是标量值，数组，列表，以及元组， 返回值是乱序后的数组
        # shuffle 函数 参数必须是数组或列表，不返回， 是在元数据上进行修改
        point_ids = np.random.permutation(num_examples)

        # 获取num_category个 随机值
        center_point_ids = point_ids[0:num_category]

        return data[center_point_ids]

    # 计算数据集分别属于哪一个类别
    @staticmethod
    def calculation_data_category(data, centroids):
        num_examples = data.shape[0]
        data_category = np.empty((num_examples, 1))
        for i in range(num_examples):
            # 获取当前点最近的一个类
            index = K_Means.calculation_min_distance(data, i, centroids)
            # 分类
            data_category[i] = index
        return data_category

    @staticmethod
    def calculation_min_distance(data, i, centroids):
        num_category = len(centroids)
        distance = np.zeros((num_category, 1))
        for index in range(num_category):
            distance_diff = data[i, :] - centroids[index, :]
            distance[index] = np.sum(distance_diff ** 2)
        return np.argmin(distance)

    @staticmethod
    def update_center(data, data_category, num_category):
        num_feature = data.shape[1]
        centroids = np.empty((num_category, num_feature))
        for i in range(num_category):
            closest_ids = data_category == i
            centroids[i] = np.mean(data[closest_ids.flatten(), :], axis=0)
        return centroids

测试：

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt

from K_Means.k_means import K_Means

data = pd.read_csv("../data/iris.csv")

type_data = ["setosa", "versicolor", "virginica"]
# data = data[["petal_length", "petal_width"]]
#
# data = np.array(data)
k_means = K_Means(data, 3)

max_iterations = 50

x_axis = "petal_length"
y_axis = "petal_width"

centroids, data_category = k_means.train(np.array(data[[x_axis, y_axis]]), max_iterations)

plt.figure(figsize=(20,8), dpi=80)
plt.subplot(121)
for i in range(3):
    plt.scatter(data[x_axis][data["class"] == i], data[y_axis][data["class"] == i], label=i)
plt.legend()
plt.title("label known")

plt.subplot(122)
for centroid_id, centroid in enumerate(centroids):
    current_examples_index = (data_category == centroid_id).flatten()
    plt.scatter(data[x_axis][current_examples_index], data[y_axis][current_examples_index], label=centroid_id)

for centroid in centroids:
    plt.scatter(centroid[0], centroid[1],c="black", marker="x")
plt.legend()
plt.title("label unknown")

plt.show()