-
- 基于密度的聚类算法
- 1. 算法简介
- 2. 参数说明及定义
- 3. 关键问题分析
- 4. 代码实现(python)
- 5. 实验结果
- 6. 参考文献
- 备注
- 基于密度的聚类算法
基于密度的聚类算法
1. 算法简介
基本思想：聚类中心的周围具有一些列低密度的点，并且它与其它高密度的点具有较大的间距。
The algorithm has its basis in the assumptions that cluster centers are surrounded by neighbors with lower local density and that they are at a relatively large distance from any points with a higher local density.
与降维算法LDA（线性判别分析）异曲同工之妙，它的降维思想是不同类别之间的类间间距大，同类数据之间类内间距小。算法的聚类中心选取原则如下：
- 聚类中心处的密度最大
- 聚类中心间的间距大
算法通过设计合适的密度函数与距离函数来实现无监督聚类。该算法不需要事先提供聚类中心的个数，能够自适应的选取聚类中心数目。
2. 参数说明及定义
-
数据维度说明
定义数据集的维度为 Rm⋅n R m ⋅ n ，其中 m m 为数据集数目，nn为样本特征维度。
-
dij d i j : 距离函数
衡量样本 xi x i 与样本 xj x j 之间的相似度，样本特征维度假设为 n n 。代码中以欧式距离作为距离函数，其定义如下：
dij=∑k=0n(xik−xjk)2dij=∑k=0n(xki−xkj)2
-
密度函数(local density) p p :文中提供了两种计算方式
Cut off kernel
pi=∑j=0 j≠imχ(dij−dc)pi=∑j=0 j≠imχ(dij−dc)
χ(x)={01x≥0x<0 χ ( x ) = { 0 x ≥ 0 1 x < 0
Gaussian kernel
pi=∑j=0 j≠ime(−dijdc)2 p i = ∑ j = 0 j ≠ i m e ( − d i j d c ) 2
-
类间距离函数 δ δ : 表示与高密度点的最短距离
δi={maxjdijminj: pj<pidijpi is highest pointelse δ i = { max j d i j p i i s h i g h e s t p o i n t min j : p j < p i d i j e l s e
假设点 i i 是聚类中心，那么比它密度大的点都可能是聚类中心。则类间距离的最大值是它与其它聚类中心之间的最短距离。但是当该点密度最大时，我们无法确定其它可能的聚类中心点，也就无法得到最大类间距离。因此可以定义为它与其它点的最大距离最为其最大类间距离。
-
γγ: 用于综合考虑密度 p p 、间距δδ对结果的影响
文中定义 γi=pi∗δi γ i = p i ∗ δ i ，也可以自己定义其它的转换关系。
3. 关键问题分析
-
如何选择 dc d c ?
dc d c 是算法的核心参数，对算法的结果至关重要。论文中提供了选取 dc d c 的原则：
As a rule of thumb, one can choose dc so that the average number of neighbors is around 1 to 2% of the total number of points in the data set.
简而言之就是平均每个数据在其 dc d c 邻域内包含1%到2%个样本总数的点。 dc d c 邻域内所有数目 totle t o t l e 为：
totle=∑i=1m∑j=1m1{dij<dc}−m t o t l e = ∑ i = 1 m ∑ j = 1 m 1 { d i j < d c } − m
mean_nums=totlem m e a n _ n u m s = t o t l e m
rate=mean_numsm r a t e = m e a n _ n u m s m
通过采用二分查找可快速找出使得rate值在0.01与0.02之间的 dc d c 值。在实际中这个值对结果影响很大，可以根据作者提供的区间，进行再一步搜索。
-
如何自动选择中心点数目?
论文选取中心点的方式是采用设定局部密度与最短距离来刷选的，即设定好密度、最短距离的阈值来刷选处符合条件的聚类中心。
基于密度的聚类算法 图1 密度距离散点图
从下图中可以看出有三个明显的离群点，通过简单的筛选可以确定中心点，从而带到自动筛选中心点数目。
基于密度的聚类算法 - 如何判断离群点?
The points of the cluster whose density is higher than rb r b are consid- ered part of the cluster core (robust assignation). The others are considered part of the cluster halo (suitable to be considered as noise).
即需要选取一个合适 rb r b 值，有文中意思 rb r b 应该是聚类中心的类半径。即与聚类中心的间距在 rb r b 为其类边界点。类边界的确定应当是哪些点属于某一个聚类中心，但在其临域 dc d c 中存在属于其它聚类中心的点。可以利用这个性质来求出具体的 rc r c 值。
4. 代码实现(python)
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
def read_text_file(filename):
"""
读取文本数据
:param filename: 输入文件地址
:return: array 数组
"""
df = pd.read_table(filename, header=None, encoding='gb2312', delim_whitespace=True)
return df.values
def get_euclidean_metric(X):
"""
获的欧式距离矩阵
:param X: 不包含label的数据
:return: 输出m*m的矩阵，m为样本个数。矩阵值为各个点之间的距离
"""
sample_nums, feature_nums = X.shape
result_matrix = np.zeros(shape=[sample_nums, sample_nums])
matrix = lambda x:(np.transpose([x])-x)**
for index in range(feature_nums):
result_matrix += matrix(X[:,index])
return result_matrix
def distance_matrix(X, with_label = False,mode='euclidean'):
"""
求解样本间距矩阵
:param X: 输入数据，数组
:param with_label: 数据是否包含标签，bool值
:param mode: 度量函数，目前只写了欧式距离函数，可自行添加
:return:距离矩阵、labels（如愿数据不包含label，则label值默认为0）
"""
distance = None
labels = np.zeros([X.shape[]])
if with_label:
labels = X[:,-]
X = X[:,:-]
if mode == 'euclidean':
distance = get_euclidean_metric(X)
else:
pass
return distance, labels
def get_dc(distance):
"""
自动选择dc值
:param distance: 距离举证
:return: dc值
"""
min_dis =
max_dis = np.max(distance)
dc = (max_dis+min_dis)/
sample_nums = distance.shape[]
while True:
nums = np.sum(distance<dc)-sample_nums
mean_nums = nums/sample_nums/
if mean_nums < *sample_nums:
min_dis = dc
elif mean_nums > *sample_nums:
max_dis = dc
else:
break
dc = (max_dis + min_dis) /
return dc
def get_local_density_sigma(distance, dc, kernel = 'gaussian'):
"""
求解局部密度
:param distance: 距离矩阵
:param dc: dc
:param kernel: 求解模式
:return: 各个点局部密度
"""
density, density_matrix = None, None
if kernel == 'gaussian':
density_matrix = np.exp(-(distance/dc)**)
density = np.sum(density_matrix,axis=)-
elif kernel == 'cut_off':
density_matrix = np.ones(distance.shape)[distance<dc]
density = np.sum(density_matrix, axis=)-
return density
def get_sigma(distance, density):
"""
求解sigma值
:param distance: 距离矩阵
:param density: 密度值
:return: delta 各点离与最高密度点的距离
"""
sample_nums = len(density)
sigma = []
for index in range(sample_nums):
max_density = max(density)
if max_density == density[index]:
sigma.append(np.max(distance[index,:]))
else:
label = density > density[index]
sigma.append(np.min(distance[index,label]))
return sigma
def auto_select_centre(distance,density,sigma):
"""
自动选取聚类中心。原文根据设置密度，最短距离的阈值来选择。暂未编写
:param distance:距离矩阵
:param density:密度
:param sigma:最短距离
:return: 聚类中心值
"""
return
def auto_classfy(distance, density, sigma, peaks):
"""
根据自动求解的聚类中心，进行聚类。可自动剔除异常点
:param distance:距离矩阵
:param density:密度
:param sigma:最小距离
:param peaks:聚类中心数目
:return:聚类结果（数据对应类别）
"""
value = sigma*density
sort_index = np.argsort(-value)
init_label = np.zeros(value.shape,dtype=np.int)
index_density = np.argsort(-density)
for index,value in enumerate(index_density[:]):
density_greater_distance = distance[value,:][index_density[:index+]]
index_density_greater_distance = np.argmin(density_greater_distance)
init_label[value] = index_density[index_density_greater_distance]
class_label = np.zeros(density.shape,dtype=np.int)-
for index,value in enumerate(sort_index[:peaks]):
class_label[value] = index
for value in index_density:
if class_label[value] == -:
class_label[value] = class_label[init_label[value]]
return class_label
def density_peak_cluster(X):
"""
密度聚类函数，自动对数据进行聚类。无需指定聚类中心数目，能够自动处理异常点。
:param X: 样本数据
:return: 局部密度、最短距离、原始标签、聚类算法处理标签
"""
distance, labels = distance_matrix(X,True)
dc = get_dc(distance)
local_density = get_local_density_sigma(distance,dc)
sigma = get_sigma(distance,density=local_density)
peaks = auto_select_centre(distance,local_density,sigma)
class_label = auto_classfy(distance, local_density, sigma, peaks)
return local_density, sigma, labels, class_label
def plot_scatter(X, density, sigma,labels,class_label):
fig = plt.figure()
ax_1 = fig.add_subplot(, , )
ax_1.scatter(X[:,], X[:,], c=labels)
ax_1.set_xlabel('x')
ax_1.set_ylabel('y')
ax_2 = fig.add_subplot(, , )
ax_2.scatter(density,sigma,alpha=)
ax_2.set_xlabel('p')
ax_2.set_ylabel('$\delta$')
value = density * sigma
value_sorted = -np.sort(-value)
ax_3 = fig.add_subplot(, , )
ax_3.scatter(range(len(value_sorted)),value_sorted,alpha=)
ax_3.set_xlabel(u'number')
ax_3.set_ylabel(u'$\gamma$')
ax_4 = fig.add_subplot(, , )
ax_4.scatter(X[:, ], X[:, ], c=class_label, alpha=)
ax_1.set_xlabel('x')
ax_1.set_ylabel('y')
plt.show()
if __name__ == "__main__":
X = read_text_file('./data/spiral.txt')
local_density, sigma, labels, class_label = density_peak_cluster(X)
plot_scatter(X, local_density, sigma,labels,class_label)
5. 实验结果
- 左上：原始带标签数据散点图
- 右上：密度-距离散点图
- 左下： γ γ 降序散点图
- 右下：密度聚类算法处理散点图
6. 参考文献
[1]. Clustering by fast search and find of density peaks
[2]. https://blog.csdn.net/itplus/article/details/38926837
备注
GitHub 地址：存放了代码与对应的数据
代码中还有两个地方没有实现，五一再实现。
- 自动选择聚类中心数目
- 确定聚类中心半径 rc r c