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

方詩(shī)喬 胡佩玲 黃瑩瑩 張昕

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

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

中圖分類(lèi)號(hào)：TP301.6? ? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：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? 引? 言

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

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

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

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

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

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

首先對(duì)Xn×m作歸一化處理：

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

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

2? 優(yōu)化算法

2.1? 相關(guān)概念

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

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

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

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

其中函數(shù) 。

平均密度為 ：

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

平均距離為 ：

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

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

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

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

其中 。

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

取閾值 ，

滿(mǎn)足T1＞T2。

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

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

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

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

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

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

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

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

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

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

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

輸出：k個(gè)聚簇

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

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

步驟3：重復(fù)步驟2，直到所有的聚類(lèi)中心相鄰兩次迭代結(jié)果的改變量不超過(guò)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ù)集中選取了四個(gè)人工數(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]就聚類(lèi)正確率、誤差平方和[8]以及聚類(lèi)數(shù)k值三個(gè)方面進(jìn)行比較，保證所有算法均在同一環(huán)境下運(yùn)行10次，并取相應(yīng)算法的最優(yōu)值和平均值作為分析數(shù)據(jù)，數(shù)據(jù)集屬性與實(shí)驗(yàn)結(jié)果如表2、圖1、圖2所示。

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

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

4? 算法應(yīng)用

4.1? 應(yīng)用背景

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

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

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

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

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

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

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

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

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

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

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

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

5? 結(jié)? 論

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

參考文獻(xiàn)：

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

[2] 邱榮太.基于Canopy的高效K-means算法 [J].現(xiàn)代營(yíng)銷(xiāo)：學(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在劃分聚類(lèi)算法中對(duì)K選取的優(yōu)化 [J].吉林大學(xué)學(xué)報(bào)：理學(xué)版，2020，58（3）：634-638.

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

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

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

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

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

收稿日期：2022-11-06