Python
的scipy
库中实现了层次聚类的方法,下面就几个主要函数进行分析。
1、使用示例
from scipy.spatial import distance
from scipy.cluster import hierarchy
# N维数据的空间距离矩阵Y
Y = distance.pdist(np.array(X), metric='euclidean')
# 执行层次聚类
Z = hierarchy.linkage(Y, method='average', metric='euclidean')
# 从给定链接矩阵定义的层次聚类中形成平面聚类,res为长度为n的数组
res = hierarchy.fcluster(Z, t=Y.max()*(0.5), criterion='distance')
2、主要函数
1. linkage()
执行层次/聚集聚类
scipy.cluster.hierarchy.linkage(y, method='single', metric='euclidean', optimal_ordering=False)
参数:
y
:可以是一维的凝聚聚类矩阵或者是2维的观测矢量数组。压缩(凝聚)距离矩阵是包含距离矩阵上三角的平面阵列。这是pdist
返回的形式。也可以是m
个n
维的观测矢量构成的mxn
的数组。若为压缩距离矩阵的所有元素必须是有限的,即没有NaN
或infs
。method
:str
,可选。要使用的链接算法。metric
:str或函数
,可选。在y
是观察向量集合的情况下使用的距离度量;否则忽略。optimal_ordering
:bool
,可选。如果为True
,则将对链接矩阵进行重新排序,以使连续的叶子之间的距离最小,当可视化数据时,这将导致更直观的树结构。默认为False
,因为此算法可能很慢,尤其是在大型数据集上。另请参见optimum_leaf_ordering
函数。
返回值:
(n-1)x4
的矩阵,分层聚类编码为链接矩阵。
该矩阵表示树状图,其中第一个和第二个元素是每个步骤中合并的两个聚类,第三个元素是这些聚类之间的距离,第四个元素是新聚类的大小-包含的原始数据点数。
method
方法:
single
:,这也称为最近点算法complete
:,也被称为Farthest Point
算法或Voor Hees
算法average
:,这也称为UPGMA
算法weighted
:,这也叫做WPGMA
centroid
:,也被称为UPGMC
算法median
:与centroid
方法相同,当两个簇s
和t
被结合为一个簇u
,s
和t
的质心平均值给出新质心u
,这也称为WPGMC
算法ward
:使用Ward
方差最小化算法,
请注意
- 对于
“single”
方法,实现了基于最小生成树的优化算法。它具有时间复杂度。对于“complete”
,“average”
,“weighted”
和“ward”
方法,将执行称为最近邻居链的算法。它还具有时间复杂度。对于其他方法,采用时间复杂度的朴素算法。所有算法都使用内存。 - 仅当使用欧几里德成对度量标准时,才正确定义方法
“centroid”
,“median”
和“ward”
。如果将y
作为预先计算的成对距离传递,则用户有责任确保这些距离实际上是欧几里得,否则产生的结果将不正确。
示例:
from scipy.cluster.hierarchy import dendrogram, linkage
from matplotlib import pyplot as plt
X = [[i] for i in [2, 8, 0, 4, 1, 9, 9, 0]]
Z = linkage(X, 'ward')
fig = plt.figure(figsize=(25, 10))
dn = dendrogram(Z)
plt.show()
2. pdist()
n
维空间中观察值之间的成对距离。
scipy.spatial.distance.pdist(X, metric='euclidean', *args, **kwargs)[source]
参数:
X
:ndarray
,一个mxn
的数组metric
:str
或函数,可选,使用的距离度量。距离函数可以是braycurtis
,canberra
,chebyshev
,cityblock
,correlation
,cosine
,dice
,euclidean
,hamming
,jaccard
,jensenshannon
,kulsinski
,mahalanobis
,matching
,minkowski
,rogerstanimoto
,russellrao
,seuclidean
,sokalmichener
,sokalsneath
,sqeuclidean
,yule
。*args
:tuple
,不推荐使用,其他参数应作为关键字参数传递**kwargs
:dict
,可选。metric
额外的参数。具体可参考相应的mertic
文档。一部分可能的参数:
返回值:
Y
:ndarray
,返回一个简化的距离矩阵Y
,对于每个i
和j
(其中i <j <m
),其中m
是原始观测值的数量。计算度量dist(u = X [i],v = X [j])
并将其存储在条目ij
中。
以下是常见的调用约定:
-
Y=pdist(X, 'euclidean')
使用欧几里得距离(2-范数)作为点之间的距离度量来计算
m
个点之间的距离。这些点在矩阵X
中排列为m
个n
维行向量。 -
Y = pdist(X, 'minkowski', p=2.)
使用
Minkowski
距离计算距离, -
Y = pdist(X, 'cityblock')
计算点之间的城市街区或曼哈顿距离
-
Y = pdist(X, 'seuclidean', V=None)
计算标准化的欧几里得距离
-
Y = pdist(X, 'sqeuclidean')
计算向量之间的平方欧几里德距离,
-
Y = pdist(X, 'cosine')
计算向量
u``和v
之间的余弦距离, -
Y = pdist(X, 'correlation')
计算向量
u
和v
之间的相关距离。 -
Y = pdist(X, 'hamming')
计算归一化的汉明距离,或两个不同向量
u
和v
之间的不同的元素的比例。为了节省内存,矩阵X
可以是布尔类型。 -
Y = pdist(X, 'jaccard')
计算点之间的
Jaccard
距离 -
Y = pdist(X, 'chebyshev')
计算点之间的切比雪夫距离,两个n向量
u
和v
之间的切比雪夫距离是它们各自元素之间的最大norm-1距离,更准确地说,距离是 -
Y = pdist(X, 'canberra')
计算点之间的堪培拉距离,
3. fcluster()
从给定链接矩阵定义的层次聚类中形成平面聚类
scipy.cluster.hierarchy.fcluster(Z, t, criterion='inconsistent', depth=2, R=None, monocrit=None)
参数:
Z
:ndarray
,linkage
函数返回的矩阵编码的层次聚类t
:scalar
,对于criteria
是inconsistent
,distance
,或monocrit
,这是形成扁平集群所使用的阈值;对于maxclust
或maxclust_monocrit
,这是请求最大聚类数目。criterion
:str
,可选。使用的准则。inconsistent
:默认值,如果群集节点及其所有后代的不一致值小于或等于t,则其所有叶后代都属于同一平面群集。如果没有非单例群集满足此条件,则将每个节点分配给自己的群集。distance
:形成扁平聚类,以便每个扁平聚类中的原始观测值的同感距离不大于t
maxclust
:找到最小阈值r
,以使同一平面簇中任意两个原始观测值之间的显色距离不大于r
且不超过t
个平面簇。monocrit
:maxclust_monocrit
:
depth
:int
,可选。执行不一致计算的最大深度。对于其他标准没有任何意义。默认为2R
:ndarray
, 可选,用于“inconsistent”
准则的不一致矩阵。如果未提供,则计算此矩阵。monocrit
:ndarray
,可选。长度为n-1
的数组。monocrit [i]
是对非单一i
进行阈值处理的统计信息。单临界向量必须是单调的,即给定具有索引i
的节点c
,对于与c
以下的节点相对应的所有节点索引j
,
返回值:
fcluster
:ndarray
,长度为n
的数组, T[i]
是原始观测值i
所属的平面簇数。
scipy.cluster.hierarchy.fcluster
可用于展平树状图,从而将原始数据点分配给单个群集。
示例
from scipy.cluster.hierarchy import ward, fcluster
from scipy.spatial.distance import pdist
X = [[0, 0], [0, 1], [1, 0],
[0, 4], [0, 3], [1, 4],
[4, 0], [3, 0], [4, 1],
[4, 4], [3, 4], [4, 3]]
Z = ward(pdist(X)) #等同于Z = linkage(X, 'ward')
>>> Z
array([[ 0. , 1. , 1. , 2. ],
[ 3. , 4. , 1. , 2. ],
[ 6. , 7. , 1. , 2. ],
[ 9. , 10. , 1. , 2. ],
[ 2. , 12. , 1.29099445, 3. ],
[ 5. , 13. , 1.29099445, 3. ],
[ 8. , 14. , 1.29099445, 3. ],
[11. , 15. , 1.29099445, 3. ],
[16. , 17. , 5.77350269, 6. ],
[18. , 19. , 5.77350269, 6. ],
[20. , 21. , 8.16496581, 12. ]])
# 阈值t太小,无法允许数据中的任何两个样本形成聚类,因此返回了12个不同的聚类。
>>> fcluster(Z, t=0.9, criterion='distance')
array([ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], dtype=int32)
# 阈值高得多,最多可连接8个数据点-因此此处返回了4个簇。
>>> fcluster(Z, t=3, criterion='distance')
array([1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4], dtype=int32)
4. dendrogram()
将分层聚类绘制为树状图。
scipy.cluster.hierarchy.dendrogram(Z, p=30, truncate_mode=None, color_threshold=None, get_leaves=True, orientation='top', labels=None, count_sort=False, distance_sort=False, show_leaf_counts=True, no_plot=False, no_labels=False, leaf_font_size=None, leaf_rotation=None, leaf_label_func=None, show_contracted=False, link_color_func=None, ax=None, above_threshold_color='b')
树状图说明了如何通过在非单例聚类及其子代之间绘制U形链接来构成每个聚类。 U链接的顶部指示群集合并。U形链接的两个分支指示合并了哪些集群。U形链接的两条腿的长度表示子群集之间的距离。它也是两个子类中原始观测值之间的距离。
参数
Z
:ndarray
,链接矩阵编码分层聚类以呈现为树状图,linkage
函数的输出值。p
:int
,可选。truncate_mode
的参数truncate_mode
:str
,可选,当从中得出链接的原始观察矩阵很大时,树状图可能很难读取。截断用于压缩树状图。有几种模式:None
:不执行截断(默认)lastp
:链接中形成的最后p
个非单簇是链接中唯一的非叶节点,它们对应于Z
中的行Z[n-p-2:end]
。所有其他非单例簇都收缩到叶节点中。level
:显示的树状图树不超过p个级别。“level”包括从上一次合并起具有p个合并的所有节点.
color_threshold
:double
,可选get_leaves
:bool
,可选orientation
:str
,可选,绘制树状图的方向,可以是以下任意字符串:top
:在顶部绘制根,并绘制向下的后代链接。 (默认)bottom
:在底部绘制根,并绘制向上的后代链接。left
:在左侧绘制根,在右侧绘制后代链接。right
:在右侧绘制根,在左侧绘制后代链接。
labels
:ndarray
,可选。默认情况下,标签为None
,因此原始观测值的索引用于标记叶子节点。否则,这是一个n大小的列表(或元组)。labels[i]
值是仅在第i
个叶子节点下对应于原始观察值而不是非单个聚类的文本。count_sort
:str
或bool
,可选。对于每个节点n
,此参数确定了绘制n
的两个后代链接的顺序(从左到右)。该参数可以是以下任意值:False
:ascending
或True
:首先绘制簇中原始对象最少的子项。descending
:首先绘制其簇中原始对象数最大的子项。
注意: distance_sort和count_sort不能都为True
distance_sort
:str
或bool
,可选。show_leaf_counts
:bool
,可选。如果为True
,则表示k>1
原始观测值的叶节点将用括号中包含的观测值数量标记。no_plot
:bool
,可选,为True
时,不执行最终渲染。如果仅需要为渲染计算的数据结构,或者如果matplotlib
不可用,则这很有用。no_labels
:bool
,可选,设置为True时,在树状图的渲染中,叶节点旁边没有标签。leaf_rotation
:double
,可选。指定旋转叶子标签的角度(以度为单位)。如果未指定,则旋转基于树状图中的节点数(默认为0)above_threshold_color
:str
,可选。该matplotlib颜色字符串可设置color_threshold
上方链接的颜色。默认值为b
。
返回值:
R
:dict
,计算以绘制树状图的数据结构字典,它具有以下键:color_list
:颜色名称列表。第k个元素代表第k个链接的颜色。icoord
和dcoord
:列表中的每个元素都是列表。ivl
:与叶节点相对应的标签列表leaves
:
示例:
from scipy.cluster import hierarchy
import matplotlib.pyplot as plt
ytdist = np.array([662., 877., 255., 412., 996., 295., 468., 268.,
400., 754., 564., 138., 219., 869., 669.])
Z = hierarchy.linkage(ytdist, 'single')
plt.figure()
dn = hierarchy.dendrogram(Z)
# 现在绘制给定的轴,改善配色方案,并同时使用垂直和水平方向:
hierarchy.set_link_color_palette(['m', 'c', 'y', 'k'])
fig, axes = plt.subplots(1, 2, figsize=(8, 3))
dn1 = hierarchy.dendrogram(Z, ax=axes[0], above_threshold_color='y',
orientation='top')
dn2 = hierarchy.dendrogram(Z, ax=axes[1],
above_threshold_color='#bcbddc',
orientation='right')
hierarchy.set_link_color_palette(None) # reset to default after use
plt.show()