移动时间层次聚类(Travel-Time based Hierarchical Clustering,TTHC)是一种新的势能聚类算法,尽管具有较好的聚类效果,但是该算法需要人工设定聚类数目,而且在分配样本的时候仅根据相似度,忽略了距离和势能的影响.针对以上问题,提出一...
详细信息
移动时间层次聚类(Travel-Time based Hierarchical Clustering,TTHC)是一种新的势能聚类算法,尽管具有较好的聚类效果,但是该算法需要人工设定聚类数目,而且在分配样本的时候仅根据相似度,忽略了距离和势能的影响.针对以上问题,提出一种自动确定聚类中心的移动时间势能聚类算法.首先计算每个数据点的势能和相似度,然后根据相似度确定数据点的父节点,得到数据点与父节点的距离;然后,根据数据点与父节点的相似度、距离和数据点的势能得到综合考量值,根据综合考量值自动确定聚类中心;最后,将剩余数据点分配到比其势能小且与其相似度最大的数据点所属类簇,得到聚类结果.将新算法与TTHC算法进行比较,在人工数据集和真实数据集上的实验结果表明,新算法不仅能够自动确定聚类数目,而且采用了更优的分配机制,可以产生更好的聚类结果.
高维数据聚类是数据挖掘领域中的重点和难点。数据挖掘的基本起始点是假设将一个数据对象表示为一个高维特征向量,比如文本文档。传统的聚类算法对高维数据的聚类质量由于维数灾难问题而大大降低。当特征维数增长时,数据对象在高维空间中分布非常稀疏,数据对象之间趋向于等距是普遍现象。在高维数据集中,对一个簇而言,通常存在着大量不相关或是冗余的特征;而不同簇之间的相关特征子集又是不一样的。因而,在高维数据集中,发现在所有维中存在簇的可能性几乎为零。聚类这类高维数据集的技术一般称为子空间聚类或投影聚类,其目的在于从不同的特征子集中发现簇。然而,许多子空间或投影聚类算法的性能也随着子空间规模增长而迅速下降。并且,有些算法需要用户提供一些领域知识帮助调节它们的参数,比如维内数值的最大距离、输入参数的阈值、数据最小密度等,而这些参数往往很难设置。
为了避免微粒群算法(Particle Swarm Optimization:PSO)在全局优化中陷入局部极值,本论文首先设计了更加有效的微粒群优化算法变种。论文分析了标准PSO算法早熟收敛的原因,提出了自适应扩散混合变异机制微粒群算法(Particle SwarmOptimization based on Adaptive Diffusion and Hybrid Mutation:InformPSO)。结合生物群体信息扩散的习性,设计了一个考虑微粒分布和迭代次数的函数,自适应调整微粒的“社会认知”能力,提高种群的多样性;模拟了基因自组织和混沌进化规律,引入克隆选择使群体最佳微粒gBest实现遗传微变,局部增值,具有变异确定性;利用Logistic序列指导gBest随机漂移,进一步增强逃离局部极值能力。基于种群的随机状态转移过程,证明了新算法具有全局收敛性。与其它几种PSO变种相比,复杂基准函数仿真优化结果表明,新算法收敛速度快,求解精度高,稳定性好,能有效抑制早熟收敛。
其次,特殊目标函数以及编码设计使得改进的微粒群算法更适合高维数据聚类,改进的微粒群优化算法用于求解高维数据聚类存在的两个问题。第一问题是给定高维数据集中的聚类数目k,如何确定软投影聚类中的变量加权问题。该问题的主要思路是为每个簇寻找一组变量权值,一般被转化为服从许多等式约束的非线性连续函数优化问题。针对于这一问题,我们设计了一个微粒群优化算法(Particle Swarm Optimization for the Variable Weighting Problem:PSOVW)寻求软投影聚类高维数据的最优变量权值。高质量的聚类结果往往需要合适的目标函数以及高效的搜索策略。PSOVW中,我们使用了一个特殊的k-means目标加权函数,该函数倾向于计算每一类在各自相关维的类内方差和而不是不相关维的类内方差和。在优化的目标函数中,新算法同时使用了非正规化的编码来表示变量权值。这种编码将软投影聚类中原本的变量权值问题的受限于等式约束的搜索空间转换成一个冗余的封闭空间,大大便利了搜索进程。跟其它软投影聚类算法相比,PSOVW采用PSO最小化给定的目标函数,因而算法对聚类中心的初始值更不敏感。在算法产生的合成数据集和UcI数据库的实例试验中,PSOVW被证明能大大提高聚类质量。
高维数据聚类存在的第二个问题是聚类过程中如何自动确定聚类数目,该问题也被视为界约束内一个非线性连续函数的优化问题。针对于该问题,我们设计了(Automatically Determining the Number of Clusters using Particle SwarmOptimization:autoPSO)。特殊编码设计允许autoPSO在迭代中能够表示具备不同聚类数目的划分,而Davies-Bouldin(DB)这个聚类有效性函数用于评价一个数据集不同划分的质量。我们在合成的高维数据集上测试了autoPSO的性能,并将实验结果与其他聚类算法进行比较,实验结果表明,微粒群优化算法自动聚类高维数据具备可行性以及广泛的应用前景。
暂无评论