1、模式相似性测度
1.1 距离测度
- 欧氏距离:注意物理量单位统一(即需要注意归一化处理)
- 马氏距离:
$$
D^2=(X-M)^TC^{-1}(X-M)
$$
特点:对于一切非奇异线性变化都是不变的,说明它不受特征量纲的影响,故是平移不变的。C是矢量集的协方差矩阵,故马氏距离排除了模式样本之间的相关性。C=I时候,马氏距离=欧氏距离。
问题:实际问题中难以计算
明式距离:
$$
D_i(X_i,X_j)=\sum_{k=1}^{n}(|x_{ik}-x_{jk}|^m)^{1/m}
$$
m=2时,欧氏距离m=1时,街坊距离
1.2 相似测度
略
2. 聚类算法
- Kmeans要熟悉编程和流程
- DBSCAN流程
from sklearn import datasets
import numpy as np
import random
import matplotlib.pyplot as plt
import time
import copy
def find_neighbor(j, x, eps):
N = list()
for i in range(x.shape[0]):
temp = np.sqrt(np.sum(np.square(x[j]-x[i]))) # 计算欧式距离
if temp <= eps:
N.append(i)
return set(N)
def DBSCAN(X, eps, min_Pts):
k = -1
neighbor_list = [] # 用来保存每个数据的邻域
omega_list = [] # 核心对象集合
gama = set([x for x in range(len(X))]) # 初始时将所有点标记为未访问
cluster = [-1 for _ in range(len(X))] # 聚类
for i in range(len(X)):
neighbor_list.append(find_neighbor(i, X, eps))
if len(neighbor_list[-1]) >= min_Pts:
omega_list.append(i) # 将样本加入核心对象集合
omega_list = set(omega_list) # 转化为集合便于操作
while len(omega_list) > 0:
gama_old = copy.deepcopy(gama)
j = random.choice(list(omega_list)) # 随机选取一个核心对象
k = k + 1
Q = list()
Q.append(j)
gama.remove(j)
while len(Q) > 0:
q = Q[0]
Q.remove(q)
if len(neighbor_list[q]) >= min_Pts:
delta = neighbor_list[q] & gama
deltalist = list(delta)
for i in range(len(delta)):
Q.append(deltalist[i])
gama = gama - delta
Ck = gama_old - gama
Cklist = list(Ck)
for i in range(len(Ck)):
cluster[Cklist[i]] = k
omega_list = omega_list - Ck
return cluster
X1, y1 = datasets.make_circles(n_samples=2000, factor=.6, noise=.02)
X2, y2 = datasets.make_blobs(n_samples=400, n_features=2, centers=[[1.2, 1.2]], cluster_std=[[.1]], random_state=9)
X = np.concatenate((X1, X2))
eps = 0.08
min_Pts = 10
begin = time.time()
C = DBSCAN(X, eps, min_Pts)
end = time.time()
plt.figure()
plt.scatter(X[:, 0], X[:, 1], c=C)
plt.show()
关于效率:
find_neighbor可以替换为:
N = list()
temp = np.sum((x-x[j])**2, axis=1)**0.5
N = np.argwhere(temp <= eps).flatten().tolist()
- K中心点算法