欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

聚类方法的原理以及python实现

程序员文章站 2022-05-20 19:53:34
...

相似度或距离

1、闵可夫斯基距离

dij=(k=1mxkixkjp)1pd_{ij}=\Bigg(\sum_{k=1}^m|x_{ki}-x_{kj}|^p\Bigg)^{\frac{1}{p}}
在这里,p1p\geqslant1

p=2p=2时称为欧式距离
dij=(k=1mxkixkj2)12d_{ij}=\Bigg(\sum_{k=1}^m|x_{ki}-x_{kj}|^2\Bigg)^{\frac{1}{2}}
p=1p=1时称为曼哈顿距离
dij=k=1mxkixkjd_{ij}=\sum_{k=1}^m|x_{ki}-x_{kj}|
p=p=\infty时称为切比雪夫距离,取各个坐标数值差的绝对值的最大值,即:
dij=maxkxkixkjd_{ij}=\max_k|x_{ki}-x_{kj}|

2、马哈拉诺比斯距离

马氏距离考虑各个分量(特征)之间的相关性并与各个分量的尺度无关。
定义:给定一个样本集合XXX=[xij]m×nX=[x_{ij}]_{m\times n},其协方差矩阵记作SS,则样本xix_i与样本xjx_j之间的马哈拉诺比斯距离dijd_{ij}定义为
dij=[(xixj)TS1(xixj)]12d_{ij}=[(x_i-x_j)^TS^{-1}(x_i-x_j)]^{\frac{1}{2}}
SS为单位矩阵时,也就是说样本数据的各个分量相互独立并且每个分量的方差为1时,马氏距离就是欧氏距离。

3、相关系数

相关系数的绝对值约接近1,表示样本约相似;越接近0,表示样本约不相似。
定义xix_ixjx_j之间的相关系数为:
rij=k=1m(xkixi)(xkjxj)[k=1m(xkixi)2k=1m(xkjxj)2]12r_{ij}=\frac{\sum_{k=1}^m(x_{ki}-\overline x_i)(x_{kj}-\overline x_j)}{\Big[\sum_{k=1}^m(x_{ki}-\overline x_i)^2\sum_{k=1}^m(x_{kj}-\overline x_j)^2\Big]^{\frac{1}{2}}}
其中
xi=1mk=1mxki,     xj=1mk=1mxkj\overline x_i=\frac{1}{m}\sum_{k=1}^mx_{ki},\,\,\,\,\,\overline x_j=\frac{1}{m}\sum_{k=1}^mx_{kj}

4、夹角余弦

夹角余弦越接近于1,表示样本越相似;越接近于0,表示样本越不相似。
两个样本xix_ixjx_j的夹角余弦定义sijs_{ij}如下:
sij=k=1mxkixkj[k=1mxki2k=1mxkj2]12s_{ij}=\frac{\sum_{k=1}^mx_{ki}x_{kj}}{\Big[\sum_{k=1}^mx_{ki}^2\sum_{k=1}^mx_{kj}^2\Big]^{\frac{1}{2}}}
其实就是求解余弦的公司:内积除以模的乘积

层次聚类算法

层次聚类开始将每个样本各自分到一类,之后将相距最近的两类合并,建立一个新的类,重复此操作知道满足停止条件,得到层次化的类别。

import numpy as np
from sklearn.datasets import make_classification
import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import linkage, dendrogram

X, y = make_classification(100, n_features=2, n_redundant=0, n_classes=3, n_clusters_per_class=1, random_state=1)
# plt.scatter(X[:, 0], X[:, 1], c=y)
# plt.show()


class HC:
    def __init__(self, X):
        self.X = X
        self.n = X.shape[0]
        self.m = X.shape[1]
        self.cluster = []
        for i in range(self.n):
            self.cluster.append([i])

    def calculate_distance(self):
        n = len(self.cluster)
        D = np.zeros((n, n))
        for i in range(n):
            for j in range(n):
                t = []
                for k1 in self.cluster[i]:
                    for k2 in self.cluster[j]:
                        t.append(np.dot(self.X[k1]-self.X[k2], self.X[k1]-self.X[k2]))
                D[i][j] = min(t)
        for i in range(n):
            D[i][i] = 999999  # 将自身与自身的距离设置为一个很大的常数,以方便之后的计算
        return D



HC = HC(X)
while len(HC.cluster) > 1:
#    print(HC.cluster)
    D = HC.calculate_distance()
    index = np.unravel_index(np.argmin(D), D.shape)
    HC.cluster[index[0]] = HC.cluster[index[0]] + HC.cluster[index[1]]
    print(HC.cluster[index[0]])
    del HC.cluster[index[1]]

plt.figure(figsize=(20,6))
Z = linkage(X, method='ward', metric='euclidean')
p = dendrogram(Z, 0)
plt.show()


最终的输出结果如下:
聚类方法的原理以及python实现
其中。每一行为这一步聚在一起的类,知道最后所有的样本都聚集成为1类。

层次聚类的示意图为:
聚类方法的原理以及python实现

k均值聚类

k均值聚是基于样本集合划分的聚类算法。k均值聚类将样本的集合划分为k个子集,构成k个类,将n个样本分到k个类中,每个样本到其所属的中心的距离最小,并且每个样本只属于一个类。
代码如下:

import numpy as np
from sklearn.datasets import make_classification
import matplotlib.pyplot as plt

X, y = make_classification(100, n_features=2, n_redundant=0, n_classes=3, n_clusters_per_class=1, random_state=1)


class KMean:
    def __init__(self, X, k):
        self.X = X
        self.k = k
        self.n = X.shape[0]
        self.m = X.shape[1]
        self.centers = [X[0], X[1], X[2]]
        self.y = np.ones((self.n, 1))

    def classifier(self):
        for i in range(self.n):
            t = []
            for j in range(self.k):
                t.append(np.dot(self.X[i] - self.centers[j], self.X[i] - self.centers[j]))
            mi = min(t)
            index = t.index(mi)
            self.y[i] = index

    def change_center(self):
        data = np.hstack((self.X, self.y))
        for i in range(self.k):
            t = np.where(data[:, 2] == i)
            X = data[t, :2]
            center = np.sum(X, axis=1)
            self.centers[i] = np.squeeze(center/X.shape[1])



K = KMean(X, 3)
for i in range(10):
    K.classifier()
    K.change_center()

plt.scatter(X[:, 0], X[:, 1], c=np.squeeze(K.y))
plt.show()

运行结果如下:
聚类方法的原理以及python实现
将所给样本分为了三个类别。
可以原数据集生成时进行对比,如下图:
聚类方法的原理以及python实现
可见,分类效果已经十分理想!