一種局部概率引導的優化K-means++算法

王海燕,崔文超,許佩迪,李 闖

(1.長春大學 計算機科學技術學院,長春 130022；2.吉林大學 理論化學研究所,長春 130021;3.吉林師范大學 計算機學院,吉林 四平 136000)

1 引言與預備知識

聚類分析(cluster analysis)[1]又稱群分析,是研究分類問題的一種統計分析方法,是數據挖掘領域中重要的無監督機器學習方法.聚類算法用途廣泛,如區分消費群體、獲取消費趨勢、輿情分析及幫助市政規劃等.常見的聚類算法有劃分法、層次法、密度法、圖論法、網格法和模型法等,其中劃分法應用廣泛.K-means聚類是經典的劃分聚類算法,具有方法簡單、效率高的特點.

隨著K-means算法的廣泛應用,其缺陷逐漸凸顯[2]：1) 聚類中心數目K需要在聚類分析前確定,而這在實際應用中很難估計；2) 初始聚類中心需要人為選取,而不同的初始聚類可能導致不同的聚類結果.針對K-means算法的不足,目前已有許多改進算法：成衛青等[3]基于數據實例間的最大最小距離選取初始聚類中心,基于誤差平方和(SSE)選擇相對最稀疏的簇分裂,并根據SSE變化趨勢停止簇分裂從而自動確定簇數；蔣麗等[4]提出了一種改進的K-means聚類算法,先根據類簇指標確定需要聚類的個數K,再采用基于密度的思想,實驗證明改進后的算法比原K-means聚類算法準確性更高；針對第二項不足,周愛武等[5]通過基于評價距離確定初始聚類中心,優化后的算法針對存在孤立點的數據效果明顯；Gu[6]采用減法聚類的算法確定初始聚類中心；鮑雷[7]針對傳統K-means聚類算法在數據聚類分析時……