基于核密度估計的K-means聚類優化

熊開玲，彭俊杰，楊曉飛，黃 俊

(1.上海大學 計算機工程與科學學院，上海 200444；2.中國科學院 上海高等研究院 公共安全中心，上海 201210)

基于核密度估計的K-means聚類優化

熊開玲1，彭俊杰1，楊曉飛2，黃 俊2

(1.上海大學 計算機工程與科學學院，上海 200444；2.中國科學院 上海高等研究院 公共安全中心，上海 201210)

K-means聚類算法作為一種經典的聚類算法，應用領域十分廣泛；但是K-means在處理高維及大數據集的情況下性能較差。核密度估計是一種用來估計未知分布密度函數的非參數估計方法，能夠有效地獲取數據集的分布情況。抽樣是針對大數據集的數據挖掘的常用手段。密度偏差抽樣是一種針對簡單隨機抽樣在分布不均勻的數據集下容易丟失重要信息問題的改進方法。提出一種利用核密度估計結果的方法，選取數據集中密度分布函數極值點附近的樣本點作為K-means初始中心參數，并使用核密度估計的分布結果，對數據集進行密度偏差抽樣，然后對抽樣的樣本集進行K-means聚類。實驗結果表明，使用核密度估計進行初始參數選擇和密度偏差抽樣能夠有效加速K-means聚類過程。

K-means聚類；密度偏差抽樣；核密度估計；數據挖掘

0 引 言

隨著互聯網、物聯網等產業的發展，各種各樣包含高維和海量的大規模數據集被生成。針對大規模數據的數據分析也變得越來越普遍[1]。K-means聚類算法作為一種應用廣泛的經典聚類算法，在面對大規模結構復雜的數據時，與其他數據挖掘方法一樣，表現得不太理想，主要集中在面對大數據時計算開銷和時間開銷成倍的增長和選擇初始參數時變得極為困難兩個問題上[2]。……