一种自动搜索阈值的层次聚类方法

机器学习 2881 Views

该技术可以可以自动搜索文本层次聚类方法中,每次迭代的相似性阈值参数,其基本思想是:对于一个簇集,通过计算两两簇之间的相似性可以获得这个簇集的相似性分布,它一定程度上反映了簇集中各个簇之间的疏密程度。获得相似性分布曲线后可以利用曲线拟合的手段确定曲线中趋势变化的拐点,通过拐点的位置来确定较合适的相似性阈值。

获得一个簇集的相似性分布曲线的方法如下:对于一个簇集C={C1,C2,

C3 …. Cn},定义成s(Ci,Cj)为簇Ci与Cj之间的相似性。计算任意两个簇之间的相似性可以获得相似性集合,我们将该集合所有样本构成的分布做为该簇集的相似性分布。通过将相似性取值作为横轴,在相似性分布集合中相似性等于一个特定值的簇对的数量作为纵轴,我们可以画出该簇集的相似性分布曲线。

一般利用上面方法产生的相似性分布曲线都会存在一些锯齿,不平滑,如果直接搜索拐点难免会发现一些无效的拐点。对于给定的一系列点坐标(x1,y1),(x2,y2),…,(xm,ym),假设将用曲线P(X) = anxn+ an-1xn-1 +…+a0来拟合这些点.

解上述方程组即可得到拟合的方程P(x).求方程的二阶导数P″(x)并令其等于零,解得x即为曲线的拐点,用与该x值相对应的y值作为阈值.

自动阈值选取主要应用在“细化簇的生成”部分,类似于DBSCAN中确定簇的方法.简单的实验可以证明,在DBSCAN中确定适当的阈值是很困难的,即使确定了适当的阈值,聚类的效果也很差.所以,自动阈值确定在簇的确定中要优于人工指定阈值.

您可以查找公众号:hlju_nlp 或扫描如下二维码,即可关注“黑龙江大学自然语言处理实验室”:

如未说明则本站原创,转载请注明出处:NULL » 一种自动搜索阈值的层次聚类方法