Hierarchical Clustering 层次聚类 试图在不同的层次上对数据集进行划分,从而形成树形的聚类结构。层次聚类一般可以分为如下两类:
自底向上 最开始时每个样本都是一个单独的簇,然后在每一次迭代中合并两个距离最近的簇为一个簇,不断进行此类操作,直到簇的个数到达预先设定的值。其中代表性的算法便是AGNES (AGglomera tive NESting),算法流程如下所示:
输入:包含n个样本的数据集,终止条件簇的数目k 输出:k个簇
将每个样本当成一个初始簇 Repeat - 根据两个簇中最近的数据点找到最近的两个簇 - 合并两个簇,生成新的簇的集合 Until 达到定义的簇的数目
AGNES算法中最关的在于如何度量簇之间的距离,因为簇是样本的集合,所以簇之间距离的度量可以转化为样本之间距离的度量。假设有两个簇C i C_{i} Ci和C j C_{j} Cj,可以定义如下的几种距离:
最小距离 :d min ( C i , C j ) = min p ⊂ C i , q ∈ C j ∣ p − q ∣ d_{\min }\left(C_{i}, C_{j}\right)=\min _{p \subset C_{i}, q \in C_{j}}|p-q| dmin(Ci,Cj)=minp⊂Ci,q∈Cj∣p−q∣,对应的为单连接算法,如果两个最近的簇之间的距离超过了用户给定的阈值时,聚类结束;最大距离 :d max ( C i , C j ) = max p ∈ C i , q ∈ C j ∣ p − q ∣ d_{\max }\left(C_{i}, C_{j}\right)=\max _{p \in C_{i, q} \in C_{j}}|p-q| dmax(Ci,Cj)=maxp∈Ci,q∈Cj∣p−q∣,对应的为全连接算法,如果两个簇之间的最大距离超过了用户给定的阈值时,聚类结束;均值距离 :d mean ( C i , C j ) = ∣ p ‾ − q ‾ ∣ , # ∓ p ‾ = 1 ∣ C i ∣ ∑ p ∈ C i p , q ‾ = 1 ∣ C j ∣ ∑ q ∈ C j q d_{\text {mean}}\left(C_{i}, C_{j}\right)=|\overline{p}-\overline{q}|, \# \mp \overline{p}=\frac{1}{\left|C_{i}\right|} \sum_{p \in C_{i}} p, \overline{q}=\frac{1}{\left|C_{j}\right|} \sum_{q \in C_{j}} q dmean(Ci,Cj)=∣p−q∣,#∓p=∣Ci∣1∑p∈Cip,q=∣Cj∣1∑q∈Cjq,其中p ‾ \overline{p} p和q ‾ \overline{q} q为簇的均值中心平均距离 :d a v g ( C i , C j ) = 1 ∣ C i ∣ ∣ C j ∣ ∑ p ∈ C i q c C j ∣ p − q ∣ d_{a v g}\left(C_{i}, C_{j}\right)=\frac{1}{\left|C_{i}\right|\left|C_{j}\right|} \sum_{p \in C_{i} q c C_{j}}|p-q| davg(Ci,Cj)=∣Ci∣∣Cj∣1∑p∈CiqcCj∣p−q∣下面给出一个形象化的小栗子
自顶向下 开始时将所有的样本看作一个簇,然后不断的分裂,直到簇的个数到达预先设定的值。其中,BIRCH 算法便是其中最著名的一个,它的全称为利用层次方法的平衡迭代规约和聚类(Balanced Iterative Reducing and Clustering Using Hierarchies) ,使用层次方法来聚类和规约数据,使用聚类特征树(CF树)来表示聚类的层次结构。而且只需要扫描一遍数据库就能进行聚类,时间开销小,适合于数据集较大的情形。
在CF树中,每一个聚类特征使用一个三元组表示:C F = < n , L S , S S > CF=<n,LS,SS> CF=<n,LS,SS>:
n:CF中拥有的样本的数量 LS:CF中拥有的样本个特征维度的向量 SS:CF中拥有的样本各特征维度的平方和 使用这样的结构有如下的诸多优点:
可以推导出簇的许多有用的统计量 只需固定大小的空间来存储聚类特征 聚类特征满足线性可加性 BIRCH主要包括两个阶段:
阶段一:扫描数据库,建立一棵存放于内存的初始CF树, 阶段二:采用某个其它的聚类算法对CF树的叶节点进行聚类,比如典型的划分方法 下面通过一个例子看一下如何构建CF树。首先放入第一个样本,此时样本数量为1,CF树的根节点也为A
然后继续放入下一个样本,因为此时它和第一个样本点都在半径为T T T的超球体中,所以它们位于同一个簇,CF树的形状不发生变化,只需更新n = 2 n=2 n=2
接着继续放入第三个样本,发现它不在位于以第一个样本点为中心、半径为T T T的超球体中,所以需要新建一个三元组存储它的信息,此时CF结构发生改变,拥有两个节点
接着放入第四个样本点的时候,我们发现和B在半径小于T的超球体,所以它和B位于同一个簇中,CF树的整体结构不变
假设我们规定叶子节点中最大的CF数为3,那么目前CF树的情况如下所示,其中L N 1 LN1 LN1中有3个CF,已满足最大数量限制,L N 2 、 L N 3 LN2、LN3 LN2、LN3各有两个。如果此时来了一个样本s c 8 sc8 sc8,它恰好位于L N 1 LN1 LN1的超球体中,但是L N 1 LN1 LN1中已经有了s c 1 、 s c 2 、 s c 3 sc1、sc2、sc3 sc1、sc2、sc3,无法继续添加
此时唯一的办法就是分裂L N 1 LN1 LN1,将s c 8 sc8 sc8和较近的s c 1 sc1 sc1放入同一个叶子节点,另外两个放入另一个叶子节点,这样L N 1 LN1 LN1就分裂为L N 1 ′ LN1' LN1′和L N 1 ′ ′ LN1'' LN1′′两个叶子节点。
但是在将LN1分裂为两个叶子节点后,根节点此时有4个叶子节点,如果同样的要求根节点拥有的最大CF数为3的话,也需要将根节点进行分裂
优点 :
节约内存,所有的样本都在磁盘上,CF-树仅仅存了CF节点和对应的指针。 聚类速度快,只需要一遍扫描训练集就可以建立CF-树,CF-树增删改都很快 可以识别噪声点,还可以对数据集进行初步分类的预处理 缺点 :
由于CF-树对每个节点的CF个数有限制,导致聚类的结果可能和真实的类别分布不同 如果数据集的分布簇不是类似于超球体,则聚类效果不好 详细介绍可见:
BIRCH聚类算法原理
https://medium.com/datadriveninvestor/how-the-simplest-clustering-algorithm-work-with-code-b8af21aabda2
https://github.com/genomexyz/machine_learning
https://www.digitalvidya.com/blog/the-top-5-clustering-algorithms-data-scientists-should-know/
https://www.analyticsvidhya.com/blog/2016/11/an-introduction-to-clustering-and-different-methods-of-clustering/
https://www.toptal.com/machine-learning/clustering-algorithms
https://www.researchgate.net/publication/220571682_An_overview_of_clustering_methods?enrichId=rgreq-cfd3626a26962e98fbf5195019cf33dd-XXX&enrichSource=Y292ZXJQYWdlOzIyMDU3MTY4MjtBUzo5OTA2MjMzNDM2MTYwOUAxNDAwNjI5NzA5NTI2&el=1_x_2&_esc=publicationCoverPdf
http://www2.stat.duke.edu/~rcs46/lectures_2017/10-unsupervise/10-hc.pdf
http://snap.stanford.edu/class/cs345a-2010/slides/12-clustering.pdf
https://arxiv.org/ftp/arxiv/papers/1205/1205.1117.pdf
http://www.mit.edu/~9.54/fall14/slides/Class13.pdf
http://www.iula.upf.edu/materials/040701wanner.pdf
来源:
https://www.icode9.com/content-4-651001.html
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请
点击举报 。