论文部分内容阅读
聚类分析是数据挖掘研究中重要的方法之一,它在发现数据内在结构特征方面有着重要作用。聚类是一种无监督的学习方法,它已经广泛应用在模式识别、商务智能、图像分析、信息检索和生物信息学等众多领域。
现在已有很多种成熟的聚类算法,包括划分聚类和层次聚类等。然而这些方法大部分都需要人为的提供像聚类类簇数这样的参数,比如,划分聚类需要预先知道聚类的类簇数,层次聚类需要知道聚类的终止点,此外还有基于网格聚类需要预先知道网格大小的阈值参数等等。然而这样的参数在实际应用中是很难得到的,这就大大的限制了聚类分析在现实中的应用。因此,对一个给定系统进行聚类时,一个基本而困难的问题就是如何确定聚类类簇数。
为了数据驱动地确定聚类数,一个好的聚类有效性指标(CVI: ClusterValidity Index)是必不可少的,它可以用来评价在聚类过程中得到的聚类结果(Clustering Result)的好坏。Yao等人提出的决策粗糙集模型对于分类有更好的理解,它是一个典型的概率型粗糙集模型,引入了贝叶斯理论来获得最小损耗的决策。
本文通过扩展决策粗糙集模型提出了一种在层次聚类算法框架下的自动确定聚类数的新方法。首先,我们扩展了决策粗糙集模型,用代价(risk)的概念来描述对象之间的关系,进而描述聚类结果的好坏。而以这个代价作为描述某个聚类结果的聚类有效性评价指标,在文中称为基于DTRS的聚类有效性函数。然后,根据此评价函数,基于凝聚型层次聚类算法框架,将聚类过程中的每个聚类结果的代价值描绘为曲线,我们发现并证明了该曲线最多只有一个极值点。所以,我们根据曲线的变化趋势,就可以找出最佳聚类数和对应的聚类结果,从而实现自动的确定聚类数。最后,我们根据在算法有效性证明过程中得到的性质,改进了算法的聚类效率,大大降低了算法的时间复杂度,实现了高效、准确的确定聚类数。