K-means算法的優(yōu)化及應用

方詩喬 胡佩玲 黃瑩瑩 張昕

摘? 要：針對K-means算法易受初始值和異常點影響，以及聚類數(shù)選取依靠人工經驗和初始聚類中心選取隨機等缺點，提出一種基于改進Canopy算法的K-means聚類算法。首先將初始數(shù)據(jù)集進行預處理和分類，然后選取特殊的閾值利用改進的Canopy算法得到聚類數(shù)和初始聚類中心，再運行K-means算法實現(xiàn)最終聚類。經檢驗得知，改進后的算法減少了對人工選擇的依賴，并且聚類準確度有了明顯的提高。最后將改進后的算法應用于顧客細分實例，取得了良好的分類效果，證明了優(yōu)化算法的實用性。

關鍵詞：Canopy算法；主成分分析法；局部密度；顧客細分

中圖分類號：TP301.6? ? 文獻標識碼：A? 文章編號：2096-4706（2023）06-0111-05

Optimization and Application of K-means Algorithm

FANG Shiqiao， HU Peiling， HUANG Yingying， ZHANG Xin

（College of Mathematics and Informatics， South China Agricultural University， Guangzhou? 510642， China）

Abstract： In view of the shortcomings of K-means algorithm that is easily affected by initial values and outliers， and that the selection of clustering number depends on artificial experience and the selection of initial clustering center is random， a K-means clustering algorithm based on improved Canopy algorithm is proposed. First， the initial data set is preprocessed and classified， and then a special threshold is selected to obtain the number of clusters and the initial cluster center using the improved Canopy algorithm， and then the K-means algorithm is run to achieve the final clustering. The test shows that the improved algorithm reduces the dependence on manual selection， and the clustering accuracy has significantly improved. Finally， the improved algorithm is applied to a customer segmentation example， and good classification results are obtained， which proves the practicability of the optimized algorithm.

Keywords： Canopy algorithm; principal component analysis; local density; customer segmentation

0? 引? 言

為滿足聚類的不同需求，聚類分析的常用方法一般可劃分為五類：基于劃分的聚類算法、基于層次的聚類算法、基于密度的聚類算法、基于網(wǎng)格的聚類算法和基于模型的聚類算法[1]。其中K-means算法是最經典的無監(jiān)督劃分算法，它具有算法思想簡單、收斂速度快、對大規(guī)模數(shù)據(jù)集處理效率高等特點，被廣泛運用于商業(yè)、電子商務、大數(shù)據(jù)挖掘等領域。

Canopy算法是一種簡單、快捷的對象聚類算法，一般用在K-means算法之前的粗聚類。它可以減少相似樣本的計算量，但是由于聚類中心的選取是隨機的，故聚類效果可能受到噪聲點或離群點的影響。此外，閾值T1、T2的取值也會影響Canopy的重疊率，影響最終的聚類效果。

針對Canopy-Kmeans聚類算法[2]初始聚類中心選取隨機、算法受噪聲點影響等問題，陳勝發(fā)等人提出了基于密度權重的Canopy的改進K-medoids算法[3]用于提高精確度；王海燕等人提出了Canopy+_K-means算法[4]從閾值獲取方式和初始聚類中心的選取兩方面進行了改進；魯茜提出一種利用距離分布直方圖改進Canopy算法中閾值T1、T2取值的算法[5]。這些算法在尋優(yōu)性能上確有提高，但在聚類準確度和算法復雜程度方面仍有待改進。

本文提出基于數(shù)據(jù)預處理，優(yōu)化Canopy算法閾值選取和聚類中心更新的算法，得到一種新的Canopy-Kmeans-pro算法，綜合實例數(shù)據(jù)和現(xiàn)實應用雙方面驗證，該改進后的算法在聚類準確率、聚類效果上均有改善，且具備一定的現(xiàn)實意義。

1? 數(shù)據(jù)預處理

設X=x1， x2，…， xn是包含n個樣本對象的數(shù)據(jù)集，每個樣本對象有m維特征屬性。其中xij（i=1， 2，…， n，j=1， 2，…， m）是第i個數(shù)據(jù)對象的第j維屬性。

首先對Xn×m作歸一化處理：

其中? 是Xn×m矩陣中每行數(shù)據(jù)的最小值， 是Xn×m矩陣中每行數(shù)據(jù)的最大值，得到歸一化數(shù)據(jù)矩陣Yn×m。

再對矩陣Yn×m運用PCA主成分分析法，將原始的高維數(shù)據(jù)集降為簡單的二維數(shù)據(jù)集，得到數(shù)據(jù)矩陣Dn×2。

2? 優(yōu)化算法

2.1? 相關概念

定義1：數(shù)據(jù)對象xi和xj之間的歐式距離為zij：

得到距離矩陣Zn×n，其中zii=0，zij=zji。

定義2：設每個數(shù)據(jù)對象到其他數(shù)據(jù)對象的距離為第p小的距離的平均值為z0，其中參數(shù)為p：

定義3：數(shù)據(jù)對象xi的局部密度[6]為ρi：

其中函數(shù) 。

平均密度為 ：

定義4：若數(shù)據(jù)對象xi不是局部密度最大的點，則si表示xi到局部密度比它大的點的距離的最小值；若數(shù)據(jù)對象xi是局部密度最大的點，則si表示xi到其他點距離的最大值。

平均距離為 ：

定義5：若數(shù)據(jù)對象xi滿足? 且 ，即該數(shù)據(jù)對象的局部密度較大且與比它具有更大局部密度的對象的距離也較大，則認為這類數(shù)據(jù)點更有機會成為聚類中心[7]，因此將滿足這兩個條件的數(shù)據(jù)點的全體稱為預備聚類中心集Hp×2。不同原始數(shù)據(jù)集的Hp×2可能具有不同的維度p。

定義6：預備聚類中心集Hp×2的均值點為 ：

定義7：預備聚類中心集Hp×2中每個數(shù)據(jù)點hi到均值點? 的距離bi為：

定義8：預備聚類中心集Hp×2中數(shù)據(jù)點hi到均值點? 距離的方差為s2：

其中 。

2.2? 改進Canopy算法

取閾值 ，

滿足T1＞T2。

其中，L1=max（bi），L2=min（bi）。

輸入：預備聚類中心集Hp×2={h1， h2，…， hp}，閾值T1和T2。

輸出：聚類數(shù)k和初始聚類中心center={c1， c2，…， ck}。

步驟1：從預備聚類中心集Hp×2中選擇局部密度ρ最大的數(shù)據(jù)對象作為第一個聚類中心c1，將它添加到center={c1}后從Hp×2中刪除。

步驟2：計算Hp×2中剩余數(shù)據(jù)對象到center中各點的距離，以c1為例：

（1）若數(shù)據(jù)點hi到c1的距離大于T1，則將hi作為一個新的聚類中心c2添加到center中，并將hi從Hp×2中刪除；

（2）若距離大于T2且小于T1，則將hi劃分到c1所在的類C1中，然后計算類C1中所有數(shù)據(jù)點的均值點作為新的c1；

（3）若距離小于T2，則將hi劃分到c1所在的類C1中，然后計算類C1中所有數(shù)據(jù)點的均值點作為新的c1，并將hi從Hp×2中刪除。

步驟3：重復步驟2，直到預備聚類中心集Hp×2為空[6]。

2.3? 改進K-means算法

輸入：聚類數(shù)k和初始聚類中心center={c1， c2，…， ck}

輸出：k個聚簇

步驟1：計算Dn×2中每個數(shù)據(jù)對象到初始聚類中心c1， c2，…， ck的距離，并將該對象劃分到離其最近的聚類中心所屬的集合。

步驟2：分別計算k個集合中數(shù)據(jù)點的中位數(shù)，作為更新后的聚類中心c1， c2，…， ck。

步驟3：重復步驟2，直到所有的聚類中心相鄰兩次迭代結果的改變量不超過0.01。

3? 仿真實驗

本文實驗均在MATLAB 2020a軟件環(huán)境下，操作系統(tǒng)為Intel（R）Core（TM） i5-8265U CPU @處理器，主頻1.60 GHz，內存8 GB的計算機中進行。

為了驗證本文算法的有效性，從UCI數(shù)據(jù)集中選取了四個人工數(shù)據(jù)集Wine、Iris、Seed_dataset、Vehicle作為實驗數(shù)據(jù)集，如表1所示。將本文算法與王海燕等人提出的Canopy+_K-means算法[4]和陳勝發(fā)等人提出的基于密度權重的Canopy的改進K-medoids算法[3]就聚類正確率、誤差平方和[8]以及聚類數(shù)k值三個方面進行比較，保證所有算法均在同一環(huán)境下運行10次，并取相應算法的最優(yōu)值和平均值作為分析數(shù)據(jù)，數(shù)據(jù)集屬性與實驗結果如表2、圖1、圖2所示。

對降維后的人工數(shù)據(jù)集Wine、Iris、Seeds_dataset、Vehicle使用本文算法并進行可視化處理，結果如圖3至圖6所示，由圖可知，聚類結果基本符合算法的測試數(shù)值。

由上述實驗結果可直觀看出，本文算法優(yōu)化了原始K-means算法中初始聚類中心以及聚類數(shù)k值的選取方法，獲取的k值準確度明顯高于Canopy+_K-means算法和DWC_K-medoids算法，并且對于實驗中的四個數(shù)據(jù)集，本文算法均能選取出正確的k值。在此基礎上，通過聚類正確率和誤差平方和兩個指標對算法進行進一步的評價，可以發(fā)現(xiàn)，本算法較其他能正確分類的算法而言，聚類正確率最高且誤差平方和最小。因此，可以認為本文算法的改進是有成效的，優(yōu)化效果較好，對于不同屬性的數(shù)據(jù)集有較強的兼容性，具有推廣意義。

4? 算法應用

4.1? 應用背景

伴隨著互聯(lián)網(wǎng)技術的不斷提升，數(shù)據(jù)的應用也越來越多元化，客戶細分也成為銷售行業(yè)了解目標受眾的重要一環(huán)?？蛻艏毞帜軌驇椭鲩L客戶數(shù)量、提升客戶生命周期價值，是識別客戶需求的有力手段。通過客戶細分的技術，針對顧客需求的異質性，營銷團隊可以規(guī)劃相應的策略，從而更經濟地為細分客戶群提供服務，同時企業(yè)可以開發(fā)具有獨特吸引力的產品和服務來實現(xiàn)盈利能力最大化。

4.2? 數(shù)據(jù)解釋

此真實數(shù)據(jù)集為2 000名來自某一特定區(qū)域的“快速消費品”購買者的行為信息，所有數(shù)據(jù)均通過購買者的個人購物卡收集。數(shù)據(jù)集已經過預處理，沒有缺失值，數(shù)據(jù)集屬性如表3所示。

4.3? 聚類結果及分析

由于男女消費者購買心理和行為具有明顯差異，為了使客戶細分的分析更準確且有成效，先對真實數(shù)據(jù)集按照性別進行分類后，再利用本文算法分別對數(shù)據(jù)集中的男性與女性數(shù)據(jù)進行聚類分析。效果如圖7、圖8所示。

由圖7、圖8可以直觀地看出聚類結果為男性顧客4類、女性顧客3類，并且各類之間“距離”差異顯著，同類之間“距離”相對緊密，聚類效果可觀。為了進一步分析各個類別的特征，分別對男性顧客和女性顧客各個屬性的平均值進行統(tǒng)計，結果如表4至7所示。

針對快速消費品市場的特點，我們認為已婚男性相較于單身男性的購買頻率更高，并且生活城市越大型，經濟收入越高者，越具有購買潛力。因此將男性顧客概括為以下四種顧客類型。

第一類為邊緣型顧客，這類顧客對于“快速消費品”的需求和購買力較低，但也具有一定的消費貢獻值，因此精確地把這類客戶區(qū)分出來，有利于更好地調配資源。

第二類為忠誠型顧客，這類顧客的消費金額和頻率較高，是最重要的客戶來源。針對這類顧客，為其提供個性化服務，保持其對企業(yè)的信任度，是長期維持顧客對企業(yè)高忠誠度的關鍵。

第三類為潛在型顧客，這類顧客在客戶資源中的整體占比較大，消費金額較低于忠誠型顧客，但消費需求高。針對這類顧客，企業(yè)需要保證專業(yè)性、時效性以及多樣性，提高顧客對企業(yè)的認可程度。

第四類為不定型顧客，這類顧客的消費頻率較低，其購物喜好具有不確定性。針對這類顧客，企業(yè)可以主動了解顧客的需求以及購買動機，運用適當?shù)耐其N策略提高客戶的購買欲。

同樣地，根據(jù)女性顧客的年齡、婚姻狀況、居住城市規(guī)模以及收入等因素，我們可以將女性顧客概括為三種顧客類型，分別為潛在型顧客、忠誠型顧客以及邊緣型顧客。針對這三類顧客采取精準的營銷策略，有利于提升顧客的購買欲以及企業(yè)核心競爭力。

5? 結? 論

本文在傳統(tǒng)K-means算法和Canopy算法的基礎上提出了一種新的聚類算法Canopy-Kmeans-pro算法，該算法不僅解決了傳統(tǒng)K-means算法聚類數(shù)k值需要人工確定和初始聚類中心需要隨機選取的問題，還解決了Canopy算法對閾值T1、T2的確定問題，在很大程度上體現(xiàn)了算法的智能性。經過檢驗，本文算法的聚類效果相比于Canopy+_K-means算法和DWC_K-medoids算法在準確率和誤差上均有明顯的優(yōu)勢。將算法應用于快速消費品市場的顧客細分，對顧客進行快速聚類，可使企業(yè)人員直觀地判斷每種顧客類型的特點，進而采取精準的營銷策略，提升企業(yè)的核心競爭力。

參考文獻：

[1] 楊爽爽，石鴻雁.基于改進果蠅優(yōu)化的密度峰值聚類算法 [J].微電子學與計算機，2022，39（9）：26-34.

[2] 邱榮太.基于Canopy的高效K-means算法 [J].現(xiàn)代營銷：學苑版，2012（3）：244-246.

[3] 陳勝發(fā)，賈瑞玉.基于密度權重Canopy的改進K-medoids算法 [J].計算機工程與科學，2019，41（10）：1823-1828.

[4] 王海燕，崔文超，許佩迪，等.Canopy在劃分聚類算法中對K選取的優(yōu)化 [J].吉林大學學報：理學版，2020，58（3）：634-638.

[5] 魯茜，蒙祖強.Canopy算法中T值選取的優(yōu)化及聚類效果的改進 [J].信息與電腦：理論版，2021，33（6）：61-65.

[6] 袁逸銘，劉宏志，李海生.基于密度峰值的改進K-Means文本聚類算法及其并行化 [J].武漢大學學報：理學版，2019，65（5）：457-464.

[7] 薛京花，劉震宇，崔適時.對K-means算法初始聚類中心選取的優(yōu)化 [J].電子世界，2012（5）：11-14+18.

[8] 沈郭鑫，蔣中云.基于密度和中心指標的Canopy二分K-均值算法優(yōu)化 [J].計算機工程與科學，2022，44（2）：372-380.

作者簡介：方詩喬（2000—），女，漢族，廣東深圳人，本科在讀，研究方向：數(shù)學與應用數(shù)學；胡佩玲（2001—），女，漢族，廣東廣州人，本科在讀，研究方向：數(shù)學與應用數(shù)學；黃瑩瑩（2001—），女，漢族，廣東河源人，本科在讀，研究方向：信息與計算科學。

收稿日期：2022-11-06