目录
先前的文章中介绍了基于密度的聚类方法。
在算法中，还定义了如下一些概念：
基于密度的聚类算法通过寻找被低密度区域分离的高密度区域，并将高密度区域作为一个聚类的“簇”。在算法中，聚类“簇”定义为：由密度可达关系导出的最大的密度连接样本的集合。
算法流程
在算法中，由核心对象出发，找到与该核心对象密度可达的所有样本形成“簇”。算法的流程为：
重复以上过程
伪代码：
首先将数据集D中的所有对象标记为未处理状态
for（数据集D中每个对象p） do
if （p已经归入某个簇或标记为噪声） then
continue;
else
检查对象p的Eps邻域 NEps(p) ；
if (NEps(p)包含的对象数小于MinPts) then
标记对象p为边界点或噪声点；
else
标记对象p为核心点，并建立新簇C, 并将p邻域内所有点加入C
for (NEps(p)中所有尚未被处理的对象q) do
检查其Eps邻域NEps(q)，若NEps(q)包含至少MinPts个对象，则将NEps(q)中未归入任何一个簇的对象加入C；
end for
end if
end if
end for代码：
# -*- coding: utf-8 -*-
import numpy as np
def distance(data):
'''计算样本点之间的距离
:param data(mat):样本
:return:dis(mat):样本点之间的距离
'''
m, n = np.shape(data)
dis = np.mat(np.zeros((m, m)))
for i in range(m):
for j in range(i, m):
# 计算i和j之间的欧式距离
tmp = 0
for k in range(n):
tmp += (data[i, k] - data[j, k]) * (data[i, k] - data[j, k])
dis[i, j] = np.sqrt(tmp)
dis[j, i] = dis[i, j]
return dis
def find_eps(distance_D, eps):
'''找到距离≤eps的样本的索引
:param distance_D(mat):样本i与其他样本之间的距离
:param eps(float):半径的大小
:return: ind(list):与样本i之间的距离≤eps的样本的索引
'''
ind = []
n = np.shape(distance_D)[1]
for j in range(n):
if distance_D[0, j] 1 and len(ind) = MinPts + 1:
types[0, i] = 1
for x in ind:
sub_class[0, x] = number
# 判断核心点是否密度可达
while len(ind) > 0:
dealt[ind[0], 0] = 1
D = dis[ind[0],]
tmp = ind[0]
del ind[0]
ind_1 = find_eps(D, eps)
if len(ind_1) > 1: # 处理非噪音点
for x1 in ind_1:
sub_class[0, x1] = number
if len(ind_1) >= MinPts + 1:
types[0, tmp] = 1
else:
types[0, tmp] = 0
for j in range(len(ind_1)):
if dealt[ind_1[j], 0] == 0:
dealt[ind_1[j], 0] = 1
ind.append(ind_1[j])
sub_class[0, ind_1[j]] = number
number += 1
# 最后处理所有未分类的点为噪音点
ind_2 = ((sub_class == 0).nonzero())[1]
for x in ind_2:
sub_class[0, x] = -1
types[0, x] = -1
return types, sub_class优缺点总结
优点：
缺点：
今天要学习的是。单从名字上看，两者必然存在一定的关系。我们先来看看官方的介绍：
– -Based of with Noise. over and the to find a that gives the best over . This to find of ( ), and be more to .
从介绍中我们可以知道是算法与基于层次聚类算法结合而来的。算法的原理是：对于聚类中的每个对象，在给定的半径邻域内的数据对象必须超过某个阀值。其算法简洁，对噪声点不敏感，而且可以发现任意形状的簇，但还是存在不足之处：
算法是对算法的一种改进，但并不是没有缺点。比如其对于边界点的处理方面效果却不是很理想。
的使用方式
import hdbscan
clusterer = hdbscan.HDBSCAN(min_cluster_size=5, gen_min_span_tree=True)
clusterer.fit(test_data)上述代码非常的简单，但中间可以把它拆成如下几个步骤：
为了找到簇，我们希望在一片稀疏的噪音海洋中找到密度更高的孤岛。 聚类算法的核心是单链接聚类，它对噪声非常敏感： 一个位于错误位置的单个噪声数据点可以充当岛屿之间的桥梁，将它们粘合在一起。 显然，我们希望我们的算法对噪声是鲁棒的，所以我们需要找到一种方法，以帮助”降低海平面”之前运行一个单一的连接算法。
我们如何在不进行聚类的情况下描述“海洋”和“陆地”?我们只要能够得到一个密度的估计，我们就可以把密度较低的点看作是“海洋”。 这里的目标不是完全区分”海洋”和”陆地”，只是为了使我们的簇核心对噪音更加健壮。 因此，鉴于”海洋”的定义，我们希望降低海平面。就实际目的而言，这意味着使”海洋”中的点彼此之间和”陆地”之间的距离更远。
然而，这只是设想。它在实践中是如何工作的？我们需要一个非常低成本的密度估计，最简单的是到 kth 最近邻距离。将其称为为针对点 x 的参数 k 定义的核心距离（定义为当前点到其第k近的点的距离），并表示为：
现在我们需要一种方法，以低密度(相应的高核心距离)分散点。要做到这一点，简单的方法是定义一个新的点之间的距离度量，我们将调用相互可达距离。 我们将相互可达距离定义如下：
式中，d(a,b)是a与b的原始距离。在该式中密集点（核心距离较低）彼此保持相同的距离，但较稀疏的点被推开，以使其核心距离至少远离任何其他点。 这实际上”降低了海平面”，稀疏的”海洋”指向外界，而”陆地”则没有受到影响。这里需要注意的是，这显然取决于k的选择，较大的k值将更多的点解释为处于“海洋”中。所有这些用一张图片来说都比较容易理解，我们使用 k 值为5，然后对于给定的一个点，我们可以画一个核心距离的圆，作为与第六个最近邻接触的圆(包括点本身) ，如下所示:
再选择另外一个点，我们可以做同样的事情，这一次用一组不同的邻居（其中一个甚至包含我们选择的第一个点）：
我们可以再用另一组六个最近邻，和另一个半径略有不同的圆：
现在，如果我们想知道蓝点和绿点之间的相互可达距离，我们可以先画一个箭头，给出绿点和蓝点之间的距离：
它穿过蓝色的圆圈，但不是绿色的圆圈——绿色的核心距离大于蓝色和绿色之间的距离。因此，我们需要将蓝色和绿色之间的相互可达距离标记为大于等于绿色圆的半径。另外，从红色到绿色的相互反应距离就是从红色到绿色的距离，因为这个距离大于两个核心距离：
一般来说，有潜在的理论来证明，相互可达距离作为一种变换，可以很好地允许单链接聚类更接近水平集的层次结构，无论我们采样的点的实际密度分布是什么。
建立最小生成树
现在我们在数据上有了一个新的相互可达性度量，我们希望开始在稠密数据上寻找孤岛。 当然，密集区域是相对的，不同的岛屿可能有不同的密度。 从概念上讲，我们将要做的是: 将数据看作一个加权图，其中数据点为顶点，任意两点之间的边的权重等于这些点之间的相互可达距离。
现在考虑一个阈值，从高开始，逐步降低。 删除任何重量超过该阈值的边。 当我们删除边时，我们将开始断开图形的连接组件。 最终，我们将在不同的阈值水平上得到一个连接组件的层次结构(从完全连接到完全不连接)。在实践中，这是非常低效的：我们有
个边，并且不期望连接的组件算法运算那么多次。正确的做法是找到一个最小的边集合，这样从集合中删除任何边都会导致组件断开。幸运的是，图论为我们提供了这样一个东西: 图的最小生成树。
我们可以通过Prim 算法非常有效地构建最小生成树树-我们一次构建一条边，总是添加最小的权重边，将当前的树连接到树中还没有的顶点。您可以看到下面构造的树。注意这是相互可达距离的最小生成树，它不同于图中的纯距离。 在这个例子中，k 值为5。
构建簇层次结构
给定最小生成树，下一步是将其转换为连接组件的层次结构。这很容易以相反的顺序完成：根据距离对树的边进行排序(按增加的顺序)，然后遍历，为每条边创建一个新的合并的簇。这里唯一困难的部分是确定每个将2个簇接在一起的边，但可以通过联合查找数据结构很容易实现。
压缩簇层次结构
簇抽取的第一步是将庞大而复杂的簇层次结构压缩到一个更小的树中。正如上面的层次结构中看到的，通常情况下簇拆分是从一个簇中分离出一个或两个点，而不是将其视为一个簇拆分为两个新的簇。为了使这个具体化，我们需要一个最小簇大小的概念，我们将它作为的一个参数。一旦我们有了最小簇大小的值，我们现在就可以遍历层次结构，并在每次分割时询问是否有一个由分割创建的新簇的点数少于最小簇大小。如果我们有少于最小的簇大小的点，我们声明它是’从簇中剔除的点’，并有较大的簇保留父簇的身份。另一方面，如果拆分为两个簇，每个簇至少与最小簇大小一样大，那么我们认为簇拆分就是让这个拆分保留在树中。在遍历了整个层次结构之后，我们最终得到了一个拥有少量节点的小得多的树，每个节点都有关于该节点的簇大小如何随着不同距离减小的数据.我们可以将其可视化为一个树状图，类似于上面的树状图，用线的宽度来表示簇中的点数。但是，当点被剔除时，该宽度随线的长度而变化。
提取簇
直观地说，我们希望选择的簇能够持续存在并且有更长的生命周期; 短命的簇可能仅仅是单链接方法的产物。在前面的图中，我们可以说，我们要选择那些簇有最大面积的情节油墨。 为了创建一个平面集群，我们需要添加一个进一步的要求，如果您选择了一个簇，那么您就不能选择它的后代的任何簇。事实上，关于应该做什么的直观概念正是所做的。
参考链接：
使用实例
import numpy as np
import pandas as pd
import hdbscan
import matplotlib.pyplot as plt
import matplotlib.cm as cm
from math import pi, cos, sin, atan2, sqrt
def get_centroid(cluster):
x = y = z = 0
coord_num = len(cluster)
for coord in cluster:
lat = coord[0] * pi / 180
lon = coord[1] * pi / 180
a = cos(lat) * cos(lon)
b = cos(lat) * sin(lon)
c = sin(lat)
x += a
y += b
z += c
x /= coord_num
y /= coord_num
z /= coord_num
lon = atan2(y, x)
hyp = sqrt(x * x + y * y)
lat = atan2(z, hyp)
return [lat * 180 / pi, lon * 180 / pi]
df = pd.read_excel("test.xlsx")
hotel_df = df[['latitude', 'longitude']]
hotel_df = hotel_df.dropna(axis=0, how='any')
hotel_coord = hotel_df.values
hotel_dbsc = hdbscan.HDBSCAN(metric="haversine", min_cluster_size=int(len(hotel_df) / 50)).fit(np.radians(hotel_coord))
hotel_df['labels'] = hotel_dbsc.labels_
hotel_df['probab'] = hotel_dbsc.probabilities_
hotel_df.loc[hotel_df['probab'] < 0.5, 'labels'] = -1 # HDBSCAN边界可能存在问题，将置信度<0.5的设为为噪音点
cluster_list = hotel_df['labels'].value_counts(dropna=False)
center_coords = []
for index, item_count in cluster_list.iteritems():
if index != -1:
df_cluster = hotel_df[hotel_df['labels'] == index]
center_coord = get_centroid(df_cluster[["latitude", "longitude"]].values)
center_lat = center_coord[0]
center_lon = center_coord[1]
center_coords.append(center_coord)
center_coords = pd.DataFrame(center_coords, columns=['latitude', 'longitude'])
print(center_coords)
# 可视化
fig, ax = plt.subplots(figsize=[20, 12])
facility_scatter = ax.scatter(hotel_df['longitude'], hotel_df['latitude'], c=hotel_df['labels'], cmap=cm.Dark2,
edgecolor='None',
alpha=0.7, s=120)
centroid_scatter = ax.scatter(center_coords['longitude'], center_coords['latitude'], marker='x', linewidths=2,
c='k', s=50)
ax.set_title('Facility Clusters & Facility Centroid', fontsize=30)
ax.set_xlabel('Longitude', fontsize=24)
ax.set_ylabel('Latitude', fontsize=24)
ax.set_xlim(120, 122)
ax.set_ylim(30, 33)
ax.legend([facility_scatter, centroid_scatter], ['Facilities', 'Facility Cluster Centroid'], loc='upper right',
fontsize=20)
plt.show()参数选择
：一个类中至少要有个样本，这个参数越大，最终的聚类种类数会越少。使用时必须设置大于1，否者会报错。
：一个点邻域范围内至少有个样本，才会被视为核心点；提供的的值越大，聚类越保守，将更多的点声明为噪声，并且聚类将被限制在逐渐密集的区域。
silon：在某些情况下，我们希望选择一个较小的，因为即使是很少点的组也可能对我们感兴趣。 但是，如果我们的数据集还包含对象集中度很高的分区，则此参数设置可能会导致大量的微簇。 为silon选择一个值有助于我们合并这些区域中的集合。 换句话说，它确保了低于给定阈值的集合不会进一步分裂。
alpha：默认情况下，alpha设置为1.0。 增加alpha将使聚类更加保守，但范围会更紧密。
注意：调整alpha将导致重新计算单个链接树的难度。
参考资料：
项目地址：
官方文档：
发表回复