聚类分析中如何度量两个对象之间的相似性呢?一般有两种方法,一种是对所有对象作特征投影,另一种则是距离计算。前者主要从直观的图像上反应对象之间的相似度关系,而后者则是通过衡量对象之间的差异度来反应对象之间的相似度关系。
机器学习常见距离计算
机器学习常见距离
一般来说,有两种类型的层次聚类方法:
- 凝聚层次聚类:采用自底向上策略,首先将每个对象作为单独的一个原子簇,然后合并这些原子簇形成越来越大的簇,直到所有的对象都在一个簇中(层次的最上层),或者达到一个终止条件。绝大多数层次聚类方法属于这一类。
- 分裂层次聚类:采用自顶向下策略,首先将所有对象置于一个簇中,然后逐渐细分为越来越小的簇,直到每个对象自成一个簇,或者达到某个终止条件,例如达到了某个希望的簇的数目,或者两个最近的簇之间的距离超过了某个阈值.
举例:下图描述了一种凝聚层次聚类算法AGNES(Agglomerative Nesting)和一种分裂层次聚类算法DIANA(Divisive Analysis)对一个包含五个对象的数据集合{a,b,c,d,e}的处理过程:
初始,AGNES将每个对象自为一簇,然后这些簇根据某种准则逐步合并,直到所有的对象最终合并形成一个簇。
例如,如果簇C1中的一个对象和簇C2中的一个对象之间的距离是所有属于不同簇的对象间欧氏距离中最小的,则C1和C2合并。
在DIANA中,所有的对象用于形成一个初始簇。
根据某种原则(如,簇中最近的相邻对象的最大欧氏距离),将该簇分裂。簇的分裂过程反复进行,直到最终每个新簇只包含一个对象。
在凝聚或者分裂层次聚类方法中,用户可以定义希望得到的簇数目作为一个终止条件。
聚类中常用的距离计算公式
四个广泛采用的簇间距离度量方法如下,其中Pi,Pj是两个簇中的两个对象或点,mi是簇Ci的均值,而ni是簇Ci中对象的数目。
簇间最小距离:dmin(Ci,Cj)=minp∈Ci,p′∈Cj∣p−p′∣
含义:簇类C1和C2的距离由该两个簇的最近样本决定。
使用该度量方法作为计算两个簇间的距离的算法又称单连接算法。
簇间最大距离:dmax(Ci,Cj)=maxp∈Ci,p′∈Cj∣p−p′∣
含义:簇类C1和C2的距离由该两个簇的最远样本决定。
使用该度量方法作为计算两个簇间的距离的算法又称最近邻聚类算法。
簇间平均距离:
dist average (C1,C2)=∣C1∣∙∣C2∣1Pi∈C1,Pj∈C2∑ dist (Pi,Pj)
含义:簇类C1和C2的距离等于两个簇类所有样本对的距离平均。
使用该度量方法作为计算两个簇间的距离的算法又称最远邻聚类算法。
簇间样本间中心距离:dcen(Ci,Cj)=dist(μi,μj),其中μ=∣C∣1∑1≤i≤∣C∣xi 被称作簇C的中心点。
簇内距离度量方法:
簇内平均距离:avg(C)=∣C∣(∣C∣−1)2∑1≤i<j≤∣C∣dist(xi,xj)
簇内最小距离:diam(C)=max1≤i<j≤∣C∣dist(xi,xj)
资源推送
分类:
-
根据簇间距离计算方法分类:
- 当算法使用最小距离 dmin(Ci,Cj)衡量簇间距离时,有时称它为最近邻聚类算法。此外,如果当最近的簇之间的距离超过某个任意的阈值时聚类过程就会终止,则称其为单连接算法。
- 当一个算法使用最大距离dmax(Ci,Cj) 度量簇间距离时,有时 称为最远邻聚类算法。此外,果当最近簇之间的最大距离超过某个任意阈值时聚类过程便终止,则称其为全连接算法。
举例:
给出在二维平面的5个点,每个点代表一个样本数据,记录x1,x2两个特征的计量值。
- 将五个样本都分别看成是一个簇,生成距离矩阵,最靠近的两个簇是3和4,因为他们具有最小的簇间距离D(3,4)=5.0。 n 第一步:合并簇3和4,得到新簇集合1,2,(34),5。
- 更新举例矩阵
D(1,(34))=min(D(1,3),D(1,4))=min(20.6,22.4)=20.6D(2,(34))=min(D(2,3),D(2,4))=min(14.1,11.2)=11.2D(5,(34))=min(D(3,5),D(4,5))=min(25.0,25.5)=25.0
除此之外,其他簇间的举例不变。
更新后举例举证。修改后的距离矩阵如图 所示,在四个簇1,2,(34),5中,最靠近的两个簇是1和5, 它们具有最小簇间距离D(1,5)=7.07
同上更新距离矩阵,取得最近距离簇是 (34)与 2
度量方法的选择
- 最小和最大度量代表了簇间距离度量的两个极端。它们趋向对离群点或噪声数据过分敏感。
- 使用均值距离和平均距离是对最小和最大距离之间的一种折中方法,而且可以克服离群点敏感性问题。
- 尽管均值距离计算简单,但是平均距离也有它的优势,因为它既能处理数值数据又能处理分类数据
层次聚类的优缺点
- 一旦合并或分裂执行,就不能修正。也就是说,如果某个合并或分裂决策 在后来证明是不好的选择,该方法无法退回并更正。
- 不具有很好的可伸缩性,因为合并或分裂的决定需要检查和估算大量的对象或簇。