聚类方法的原理以及python实现
程序员文章站
2022-05-20 19:53:34
...
相似度或距离
1、闵可夫斯基距离
在这里,
当时称为欧式距离:
当时称为曼哈顿距离:
当时称为切比雪夫距离,取各个坐标数值差的绝对值的最大值,即:
2、马哈拉诺比斯距离
马氏距离考虑各个分量(特征)之间的相关性并与各个分量的尺度无关。
定义:给定一个样本集合,,其协方差矩阵记作,则样本与样本之间的马哈拉诺比斯距离定义为
当为单位矩阵时,也就是说样本数据的各个分量相互独立并且每个分量的方差为1时,马氏距离就是欧氏距离。
3、相关系数
相关系数的绝对值约接近1,表示样本约相似;越接近0,表示样本约不相似。
定义与之间的相关系数为:
其中
4、夹角余弦
夹角余弦越接近于1,表示样本越相似;越接近于0,表示样本越不相似。
两个样本与的夹角余弦定义如下:
其实就是求解余弦的公司:内积除以模的乘积
层次聚类算法
层次聚类开始将每个样本各自分到一类,之后将相距最近的两类合并,建立一个新的类,重复此操作知道满足停止条件,得到层次化的类别。
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()
最终的输出结果如下:
其中。每一行为这一步聚在一起的类,知道最后所有的样本都聚集成为1类。
层次聚类的示意图为:
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()
运行结果如下:
将所给样本分为了三个类别。
可以原数据集生成时进行对比,如下图:
可见,分类效果已经十分理想!
上一篇: ES6学习(数值扩展)
下一篇: 数据结构——字典树