基于混沌PSO和K均值算法的移動用戶分類

摘 要：為了克服經典K-Means算法隨機選擇初始數據中心而易陷入局部最優解和聚類結果的不確定性問題，提出了一種基于粒子群和K-Means算法的改進聚類算法以實現移動用戶分類。首先，定義了數據對象密度并采用改進的普里姆算法初始化聚類中心，然后，將此聚類中心用于初始化粒子位置，采用混沌粒子群算法尋優獲得最優解作為最終的聚類中心，最后，采用經典K-Means算法根據最終聚類中心進行聚類。仿真實驗表明文中方法能正確地實現移動用戶分類，并具有較強的全局尋優能力和較快的收斂速度，彌補了經典K-Means方法的不足，具有較強的現實意義。

關鍵詞：粒子群 K均值 分類 聚類

中圖分類號：TP391 文獻標識碼：A

1.引言

移動用戶分類是指根據用戶的屬性、偏好、需求以及價值等因素，采用相關技術對用戶進行分類，并根據分類結果為用戶進行量身定做相應的產品和服務[]。

傳統的對移動用戶進行分類的方法主要有經驗細分法和數理統計法，經驗細分法具有主觀性強的缺點，而數理統計法的分類優劣很大程度上取決于分類標準，所以兩種方法均具有片面性。

K-Means算法[2]是由MacQueen提出的一種經典的聚類算法，具有簡單、快速和有效的數據分類能力，但聚類結果的優劣常依賴于初始值，且其采用基于梯度下降的算法使其易于得到局部最優解。

為了克服K-Means聚類方法的不足，不少文獻開始對K-Means算法進行改進，文獻[3]將遺傳算法[4]的編碼、適應度、選擇、交叉和變異等用于K-Means聚類問題，提高了算法效率。文獻[5]通過在粒子群[6]中引入小概率隨機變異操作以增強種群的多樣性，并通過群體適應度方差以確定K均值的操作時機，以提高算法的收斂性和全局尋優能力。文獻[7]首先通過K-Means算法[8]獲得聚類中心初始值，在此基礎上采用蟻群算法和模擬退火算法對聚類中心進一步尋優。文獻[9]首先采用決策樹對移動通信客戶進行分類，然后再采用相異度原理對客戶進行再次分類，通過對移動客戶的屬性進行分析，來評價不同客戶的消費行為，從而尋找出高價值客戶。文獻[10]設計了基于粗糙神經網絡的客戶消費分類模型，采用粗糙集進行屬性簡約和提取規則，從而構造分類神經網絡拓撲結構，最后對網絡進行訓練和分類。文獻[11]提出了一種基于改進DBSCAN算法的電信客戶分類方法，通過為聚類分析生成增廣簇排序，而簇排序對應了各樣本點基于密度的簇結構，最終實現了電信客戶的聚類。

上述工作均對實現了對用戶的分類，具有重要的意義，本文在上述工作的基礎上，提出了一種使用混沌PSO和K-Means算法并根據用戶的消費行為對移動用戶進行分類的方法，首先采用改進的普里姆算法獲得初始聚類中心，然后采用混沌PSO對聚類中心進行優化，最后，采用K-Means算法聚類實現移動用戶分類，較好地解決了移動用戶分類問題。

2 K-Means算法

K-Means算法是一種基于距離的聚類算法，采用距離作為相似度評價指標，即如果兩個數據對象之間的距離越近，它們之間的相似度越大。

從圖1中可以看出文中方法較傳統的K-Means算法收斂速度快，并能逼近全局最優解，而在迭代同樣次數時，傳統的K-Means算法由于隨機選擇聚類中心，所以收斂速度快，但最終陷入了局部最優。

5 總結

針對移動用戶分類需求，提出了一種基于粒子群和K-Means算法的聚類方法。首先采用改進的普里姆算法進行聚類中心初始化，為了避免陷入局部最優解，采用混沌粒子群算法對聚類中心進一步進行尋優，以獲得全局最優的聚類中心，最后，再采用經典K-Means算法進行聚類。實驗表明文中方法克服了K-Means算法對于初始數據中心敏感以及易收斂于局部最優解的問題，能有效地對移動用戶進行分類以協助移動公司針對不同用戶指定相應政策。

參考文獻

[1]范英， 張忠能， 凌君逸. 聚類方法在通信行業客戶細分中的應用[J].計算機工程， 2004， 30（12）：440-441.

[2] Li M J and Ng M K， et al.. Agglomerative fuzzy K-means clustering algorithm with selection of number of clusters[J]. IEEE Transactions on Knowledge and Data Engineering， 2008， 20（11）： 1519-1534.

[3]唐朝霞.一種改進的基于遺傳算法的K均值聚類算法[J].成都大學學報， 2011， 30（2）：162-164.

[4]劉全， 王曉燕， 傅啟明， 張永剛， 章曉芳. 雙精英協同進化遺傳算法[J].軟件學報，2012，23（4）：765-775.

[5]陶新民， 徐晶， 楊立標， 劉玉. 一種改進的粒子群和K均值混合聚類算法[J].電子與信息學報， 2010， 32（1）：92-97.

[6]紀震， 周家銳， 廖慧連， 吳青華.智能單粒子優化算法[J].計算機學報， 2010， 33（3）：556-561.

[7]陶紅， 史小伍，李莎，高尚.基于蟻群和模擬退火算法的聚類新方法[J].微電子學與計算機，2011，28（12）：96-98.

[8]王會青， 陳俊杰， 郭凱. 啟發式初始化獨立的K-均值算法研究[J].2012， 48（11）：129-132.

[9]陳峰. 基于決策樹和相異度算法的移動通信客戶分類方法[J]， 計算機應用， 2009， 29（8）：2250-2256.

[10]萬映紅， 胡萬平， 曹小鵬. 基于粗糙神經網絡的客戶消費模型研究[J]. 管理工程學報， 2011，25（2）：142-148.

[11]左國才， 周榮華， 符開耀. 基于DBSCAN算法的電信客戶分類的應用研究[J].2012，26（3）：52-55.

[12]王會青， 陳俊杰， 郭凱. 啟發式初始化獨立的K-均值算法研究[J].計算機工程與應用， 2012，48（11）：129-132.

[13]單良，強浩，李軍. 基于Tent 影射的混沌優化算法[J]. 控制與決策， 2005，20（ 2） ： 179-182.