层次聚类-scipy实现

3,424 阅读9分钟

Pythonscipy库中实现了层次聚类的方法,下面就几个主要函数进行分析。

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返回的形式。也可以是mn维的观测矢量构成的mxn的数组。若为压缩距离矩阵的所有元素必须是有限的,即没有NaNinfs
  • methodstr,可选。要使用的链接算法。
  • metricstr或函数,可选。在y是观察向量集合的情况下使用的距离度量;否则忽略。
  • optimal_orderingbool,可选。如果为True,则将对链接矩阵进行重新排序,以使连续的叶子之间的距离最小,当可视化数据时,这将导致更直观的树结构。默认为False,因为此算法可能很慢,尤其是在大型数据集上。另请参见optimum_leaf_ordering函数。

返回值

(n-1)x4的矩阵,分层聚类编码为链接矩阵。

该矩阵表示树状图,其中第一个和第二个元素是每个步骤中合并的两个聚类,第三个元素是这些聚类之间的距离,第四个元素是新聚类的大小-包含的原始数据点数。

method方法:

  • singled(u,v)=min(dist(u[i], v[j])),这也称为最近点算法
  • completed(u,v)=max(dist(u[i],v[j])),也被称为Farthest Point算法或Voor Hees算法
  • averaged(u,v)=\sum_{ij} \frac{d(u[i],v[j])}{|u|*|v|},这也称为UPGMA算法
  • weightedd(u,v)=(dist(s,v)+dist(t,v))/2,这也叫做WPGMA
  • centroiddist(s,t)=\parallel c_s-c_t\parallel_2,也被称为UPGMC算法
  • mediand(s,t)centroid方法相同,当两个簇st被结合为一个簇ust的质心平均值给出新质心u,这也称为WPGMC算法
  • ward:使用Ward方差最小化算法,

请注意

  • 对于“single”方法,实现了基于最小生成树的优化算法。它具有时间复杂度O(n^2)。对于“complete”“average”“weighted”“ward”方法,将执行称为最近邻居链的算法。它还具有时间复杂度O(n^2)。对于其他方法,采用O(n^3)时间复杂度的朴素算法。所有算法都使用O(n^2)内存。
  • 仅当使用欧几里德成对度量标准时,才正确定义方法“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,对于每个ij(其中i <j <m),其中m是原始观测值的数量。计算度量dist(u = X [i],v = X [j])并将其存储在条目ij中。

以下是常见的调用约定:

  1. Y=pdist(X, 'euclidean')

    使用欧几里得距离(2-范数)作为点之间的距离度量来计算m个点之间的距离。这些点在矩阵X中排列为mn维行向量。

  2. Y = pdist(X, 'minkowski', p=2.)

    使用Minkowski距离计算距离, \parallel u-v \parallel_p, p\ge1

  3. Y = pdist(X, 'cityblock')

    计算点之间的城市街区或曼哈顿距离

  4. Y = pdist(X, 'seuclidean', V=None)

    计算标准化的欧几里得距离

  5. Y = pdist(X, 'sqeuclidean')

    计算向量之间的平方欧几里德距离,\parallel u-v \parallel_2^2

  6. Y = pdist(X, 'cosine')

    计算向量u``和v之间的余弦距离,1-\frac{u·v}{\parallel u\parallel_2 \parallel v\parallel_2}

  7. Y = pdist(X, 'correlation')

    计算向量uv之间的相关距离。1-\frac{(u-\bar{u})·(v-\bar{v})}{\parallel (u-\bar{u}) \parallel_2 \parallel(v-\bar{v}) \parallel_2)}

  8. Y = pdist(X, 'hamming')

    计算归一化的汉明距离,或两个不同向量uv之间的不同的元素的比例。为了节省内存,矩阵X可以是布尔类型。

  9. Y = pdist(X, 'jaccard')

    计算点之间的Jaccard距离

  10. Y = pdist(X, 'chebyshev')

    计算点之间的切比雪夫距离,两个n向量uv之间的切比雪夫距离是它们各自元素之间的最大norm-1距离,更准确地说,距离是d(u,v)=\max_i |u_i-v_i|

  11. Y = pdist(X, 'canberra')

    计算点之间的堪培拉距离, d(u,v)= \sum_ {i}\frac {|u_i-v_i|}{|u_i|+|v_i|}

3. fcluster()

从给定链接矩阵定义的层次聚类中形成平面聚类

scipy.cluster.hierarchy.fcluster(Z, t, criterion='inconsistent', depth=2, R=None, monocrit=None)

参数:

  • Z:ndarraylinkage函数返回的矩阵编码的层次聚类
  • t:scalar,对于criteriainconsistent, distance,或monocrit,这是形成扁平集群所使用的阈值;对于maxclustmaxclust_monocrit,这是请求最大聚类数目。
  • criterion:str,可选。使用的准则。
    • inconsistent:默认值,如果群集节点及其所有后代的不一致值小于或等于t,则其所有叶后代都属于同一平面群集。如果没有非单例群集满足此条件,则将每个节点分配给自己的群集。
    • distance:形成扁平聚类,以便每个扁平聚类中的原始观测值的同感距离不大于t
    • maxclust:找到最小阈值r,以使同一平面簇中任意两个原始观测值之间的显色距离不大于r且不超过t个平面簇。
    • monocrit:
    • maxclust_monocrit:
  • depth:int,可选。执行不一致计算的最大深度。对于其他标准没有任何意义。默认为2
  • R:ndarray, 可选,用于“inconsistent”准则的不一致矩阵。如果未提供,则计算此矩阵。
  • monocrit:ndarray,可选。长度为n-1的数组。 monocrit [i]是对非单一i进行阈值处理的统计信息。单临界向量必须是单调的,即给定具有索引i的节点c,对于与c以下的节点相对应的所有节点索引jmonocrit[i]>=monocrit[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:strbool,可选。对于每个节点n,此参数确定了绘制n的两个后代链接的顺序(从左到右)。该参数可以是以下任意值:
    • False:
    • ascendingTrue:首先绘制簇中原始对象最少的子项。
    • descending:首先绘制其簇中原始对象数最大的子项。

注意: distance_sort和count_sort不能都为True

  • distance_sort:strbool,可选。
  • 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个链接的颜色。
    • icoorddcoord:列表中的每个元素都是列表。
    • 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()