引力势能聚类算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇引力势能聚类算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：总结密度聚类算法存在的共性问题，即聚类之前的参数设定困难，据此提出密度聚类算法的改进目标。模拟万有引力势能的物理模型，结合核密度估计的概念，构建引力势能影响函数与引力势能密度函数，从而创造引力势能聚类算法，该算法能够克服聚类算法中的参数设定困难。详细介绍了该算法的基本原理、参数设定、聚类评判依据，算法步骤，并通过实际应用案例展示该算法在聚类分析和异常分析中的作用。

关键词：聚类；密度；引力势能；参数设定；异常分析

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2013）08-1889-05

放眼当今世界，聚类算法百花齐放。遗憾的是，多数算法要求用户在缺乏先验知识的条件下输入某些参数，这些参数设定往往带有盲目性，却显著影响聚类结果。此外，现实中的数据集很难找出全局最优参数能够反映聚类结构的本质特征。

相较之下，密度聚类算法具有许多优良特性，例如能发现任意形状的簇，适于处理噪声，对记录输入顺序不敏感，容易理解和使用范围广泛等等。但在聚类前，仍不免需要输入一些对结果敏感的参数。该文选择密度聚类算法作为研究方向，致力于找出更有效的算法模型，解决参数设定盲目性的难题。

1 密度聚类算法的共性问题

以上分析为密度聚类算法指明了改革方向，该文需要设计一种新算法：有能力发现任意形状的簇；允许各簇的密度级别差异悬殊；具有噪声处理能力；尽可能不依赖输入参数；由算法自动确定聚簇的结构、数目、形状、密度和规模。总而言之是要找到一种能够自动确定聚类结构的模型，实现聚类自动化。

2 引力势能聚类算法

为解决聚类参数预设的困难，前人已针对多种聚类算法进行过大量改进尝试，但都不算特别成功，看来仅仅改进和修正是很难在聚类自动化方面有所突破的。下面介绍的引力势能聚类算法（Gravitational Potential Energy Clustering Algorithm，缩写为GPECA），正是从自然界基本规律中获得启发，创造而成的。

2.1 GPECA基本原理

2.6 GPECA逐步说明

STEP1是基于相异度的聚类算法的通用过程。

STEP4计算[EC1]和[εC1]是作者经多次不同特性的数据集聚类试验后总结出的技巧，该技巧旨在保持同一聚簇成员的统一特性。不直接使用聚簇边缘成员自身的[Ex]和[εx]参与聚簇判定，可以有效避免极端情况下产生下述错误：因密度逐渐稀疏过渡而将两个或多个不同密度区域连成一片聚簇。

STEP9从定义出发，最终确定整个聚类结构和噪声集合。

2.7 算法性能分析

3 算法验证

评价本案例的分析效果：①完成了预期的分析目标；②所获得的38个聚类，虽然包含企业数目差距悬殊的不同聚类规模，而且这些聚类难以给出明确的特征定义，但确实客观反映了这些重点企业的整体分布情况和各自特点；③聚类总数和异常企业比例在分析人员可接受的范围之内；④采用异常指数可以进一步分析各种不同的异常企业问题究竟出在哪里，但异常原因的归纳还不够精细。⑤经重点企业问卷调查和对有严重偷漏税嫌疑的部分企业抽样稽查，证明上述推断准确率超过90%。

反观采用DBSCAN分析，若每次设定不同的[ε]和MinPts参数，则每次聚类结果都显著不同。多次迭代聚类的结果有：

聚类总数大于80个，异常比例49%；或者聚类总数大于300个，异常比例28%；或者仅有1个聚类，异常点仅6个。这些结果无法综合研究，既不利于分类管理，也不利于异常分析。

综上，GPECA能很好地完成税源分类管理、重点税源监控和税务稽查选案三项重要工作，在纳税评估应用中非常有效。

4 结束语

GPECA是一种新颖的密度聚类算法，它可以基本解决多数聚类算法中的参数设定和全局最优参数选择问题。此外，基于客观聚类的结果之上，还能进一步进行异常分析。本算法适用于对中型数据集执行聚类分析和异常分析。

参考文献：

[1] Soman K P， Diwakar S， Ajay V. Insight into Data Mining： Theory and Practice[M]. India： Prentice Hall of India， 2006.

[2] 张兴会.数据仓库与数据挖掘技术[M].北京：清华大学出版社，2011.

[3] Ankerst M， Breunig M M， Kriegel H P. Optics： Ordering Points to Identify the Clustering Structure[C]. Proceeding ACM SIGMOD International Conference on Management of Data， Philadelphia， PA， USA， 1999：46-60.

[4] Terrell G R， Scott D t. Variable Kernel Density Estimation. Ann Statistics[C]，1992，1236-1265.

[5] 余小高，余小鹏.基于距离和密度的无监督聚类算法的研究[J].计算机应用与软件，2010（7）：122-125.

[6] Ronald Lane Reese. University Physics[M]. Brooks/Cole-Thomson Learning，2002.

[7] Ian H Witten， Frank E. Data Mining： Practical Machine Learning Tools and Techniques[M]. Third Edition， New Zealand， 2011.

[8] Park H S， Jun C H， A simple and fast algorithm for K-medoids clustering， Expert Systems with Applications，2009（2）：3336-3341.

[9] Breunig M M， Kriegel H P， Ng R T， Sander J. LOF： Identifying Density-based Local Outliers[C]， ACM SIGMOD Record 29：93.