【机器学习】Python详细实现基于欧式Euclidean、切比雪夫Chebyshew、曼哈顿Manhattan距离的Kmeans聚类_使用“曼哈顿距离”计算距离矩阵,并输出 k = 3 的 k-mean分类结果python

作者：小桥流水78 | 2024-07-06 21:11:26

踩

使用“曼哈顿距离”计算距离矩阵,并输出 k = 3 的 k-mean分类结果python

1 算法过程

（1）随机选取K个簇中心点

（2）通过计算每个样本与每个簇中心点的距离，选择距离最小的簇心，将样本归类到该簇心的簇中
$min\sum_{i=1}^K \sum_{x\in c_i}dist(c_i,x)^2$

这里距离可以使用欧几里得距离（Euclidean Distance）、余弦距离（Cosine Distance）、切比雪夫距离（Chebyshew Distance）或曼哈顿距离（Manhattan Distance），计算距离之前需要先对特征值进行标准化。

3、在已经初次分配的簇中，计算该簇中所有向量的均值，作为该的簇中心点

4、重复步骤2和3来进行一定数量的迭代，直到簇中心点在迭代之间变化不大

评价指标

轮廓系数（Silhouette Coefficient），是聚类效果好坏的一种评价方式。轮廓系数的值是介于 [-1,1] ，越趋近于1代表内聚度和分离度都相对较优。

2 实现

2.1 Python代码

# kmeans算法
#  1. 初始化k个族中心
#  2. 计算每个样本与k个族中心距离，标记样本为距离最短的族
#  3. 重新确定K族中心(族中平均位置)
#  4. 循环2-3，直到前后两次所有族中心距离变化<eps
"""
# 输入：
    X: 2d数组, 形如(n_samples, m_features)，n_samples表示样本数，m_features表示特征维数
    K: int, 超参数，指定族格式
    metric：str, 距离类型，默认为欧式距离'Euler',其他暂时为实现
    eps: float, 精度（当族中心位置更新变化<eps时停止)
    random_state: 随机种子    
# 输出：
    centers: K族中心向量, 2d数组, 形如(K, m_features)
    pred: 1-d数组,长度为n_samples 
"""

import numpy as np
import random   # 用python的random模块，不用numpy的random
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from scipy.spatial.distance import pdist
from sklearn.preprocessing import StandardScaler

class kmeans:  # 创建kmeans类

    # 初始化函数
    def __init__(self, X=None, K=2, metric='Euler',eps=1e-6, init_centers=None, random_state=None):
        self.X = X
        self.K = K
        self.metric = metric
        self.eps = eps
        self.centers = init_centers
        self.random_state = random_state


    # 距离函数
    def calc_dist(self, x, c):
        dist_list = []
        for i in range(c.shape[0]):
            v = c[i]
            # 欧式距离
            if self.metric == 'Euler':
                lp = 2
                distance = np.power(np.power(x-v, lp), 1/lp).sum()
                dist_list.append(distance)
            # 切比雪夫距离
            elif self.metric == 'Chebyshew':
                distance = abs((x)-v).max()
                dist_list.append(distance)
            # 曼哈顿距离
            elif self.metric == 'Manhattan':
                distance = sum(abs(x-v))
                dist_list.append(distance)
            # jaccard距离
            elif self.metric == 'Jaccard':
                matV = np.vstack([x, v])
                distance = pdist(matV, 'jaccard')
                dist_list.append(distance)
            # 余弦距离
            elif self.metric == 'Cosine':
                distance = np.dot(x, v) /(np.linalg.norm(x)*np.linalg.norm(v))
                dist_list.append(distance)
        return dist_list

    # 迭代(训练)
    def fit(self, X):
        # 样本
        if X is not None:
            self.X = X
        # 样本形状
        n_samples, n_features = self.X.shape

        # 设置随机种子
        if self.random_state is not None:
            random.seed(self.random_state)

        # 初始化聚类中心
        if self.centers is None:
            # 随机选取簇心（这点可改进，比如kmeans++就是在此改进的）
            idx = idx = random.sample(range(n_samples), self.K)
            self.centers = X[idx, :]

        # 初始样本的族标记-1
        pred = np.array([-1]*n_samples)

        iter = 0
        stop = False  # 结束标志
        while (not stop):
            iter += 1
            print(iter)
            for i in range(n_samples):
                dists = self.calc_dist(X[i, :], self.centers)
                pred[i] = np.argmin(dists)

            # 重新确定族中心
            new_centers = np.zeros((self.K, n_features))
            for k in range(self.K):
                new_centers[k, :] = X[pred == k, :].mean(axis=0)

            # 判断停止条件
            delta = abs(new_centers - self.centers)
            flg = delta < self.eps
            stop = flg.all()
            self.centers = new_centers

        return pred, self.centers

    # 族预测
    def predict(self, X):
        # 遍历所有样本，划分族
        pred = np.array([-1]*n_samples)
        for i in range(n_samples):
            dists = self.calc_dist(X[i, :], self.centers)
            pred[i] = np.argmin(dists)
        return pred


if __name__ == "__main__":


    # 生成数据
    n_samples = 1500
    random_state = 170
    X, y = make_blobs(n_samples=n_samples, random_state=random_state)

    # 调用kmeans
    metric_dist = 'Cosine'
    model = kmeans(X, K=3, metric=metric_dist, eps=1e-3, random_state=1)

    ss = StandardScaler()
    X_n = ss.fit_transform(X)
    pred, centers = model.fit(X_n)
    n_samples, _ = X.shape
    # 评价指标：轮廓系数，【-1 1】越接近1 ，聚类效果越好
    score = silhouette_score(X, pred)

    # 族预测，如果仅是训练数据，直接用fit(X)返回的族划分
    # pred = model.predict(X)
    plt.scatter(X[:, 0], X[:, 1], c=pred)
    plt.title("{}—kmeans".format(metric_dist))
    plt.show()
    print()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143