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

方詩喬 胡佩玲 黃瑩瑩 張昕

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

關(guān)鍵詞：Canopy算法；主成分分析法；局部密度；顧客細(xì)分

中圖分類號：TP301.6? ? 文獻(xiàn)標(biāo)識碼：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算法是最經(jīng)典的無監(jiān)督劃分算法，它具有算法思想簡單、收斂速度快、對大規(guī)模數(shù)據(jù)集處理效率高等特點(diǎn)，被廣泛運(yùn)用于商業(yè)、電子商務(wù)、大數(shù)據(jù)挖掘等領(lǐng)域。

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

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

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

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

設(shè)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運(yùn)用PCA主成分分析法，將原始的高維數(shù)據(jù)集降為簡單的二維數(shù)據(jù)集，得到數(shù)據(jù)矩陣Dn×2。

2? 優(yōu)化算法

2.1? 相關(guān)概念

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

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

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

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

其中函數(shù) 。

平均密度為 ：

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

平均距離為 ：

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

定義6：預(yù)備聚類中心集Hp×2的均值點(diǎn)為 ：

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

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

其中 。

2.2? 改進(jìn)Canopy算法

取閾值 ，

滿足T1＞T2。

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

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

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

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

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

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

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

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

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

2.3? 改進(jìn)K-means算法

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

輸出：k個聚簇

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

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

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

3? 仿真實(shí)驗(yàn)

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

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

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

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

4? 算法應(yīng)用

4.1? 應(yīng)用背景

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

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

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

4.3? 聚類結(jié)果及分析

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

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

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

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

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

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

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

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

5? 結(jié)? 論

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

收稿日期：2022-11-06