基于企業(yè)應(yīng)用的K-means算法的實(shí)現(xiàn)與改進(jìn)

羅俊

摘要：K-Means算法，也稱為K-均值，是數(shù)據(jù)挖掘研究中是一種最基本的算法，也是應(yīng)用最廣泛的聚類算法。在電子商務(wù)、入侵檢測(cè)、CRM等領(lǐng)域有較多的應(yīng)用實(shí)例。它是一種cluster analysis的算法，其實(shí)現(xiàn)主要通過(guò)不斷循環(huán)迭代地選取離種子點(diǎn)最近均值的過(guò)程。本文結(jié)合企業(yè)實(shí)際應(yīng)用闡述k-means的實(shí)現(xiàn)過(guò)程、具體的改進(jìn)思路以及應(yīng)用價(jià)值，聚類模型的建立對(duì)企業(yè)具有較強(qiáng)的實(shí)際意義。

關(guān)鍵詞：電子商務(wù);聚類;算法改進(jìn);K-means算法

中圖分類號(hào)：TP311? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2021）18-0029-03

開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

當(dāng)今關(guān)于大數(shù)據(jù)、云的研究愈發(fā)深入，可是如何用好這些數(shù)據(jù)，發(fā)現(xiàn)這些數(shù)據(jù)背后隱藏的信息卻成為更具實(shí)際價(jià)值的工作，這也就是數(shù)據(jù)挖掘的概念。數(shù)據(jù)挖掘就是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中，提取隱藏其中人們事先不知道的、但又是潛在有用的信息和知識(shí)的過(guò)程。其與數(shù)據(jù)分析最大的區(qū)別在于未知性，當(dāng)前數(shù)據(jù)挖掘的實(shí)際價(jià)值已經(jīng)應(yīng)用社會(huì)的各行各業(yè)，例如：百貨連鎖、電子商務(wù)、生產(chǎn)制造、金融等。

本文從企業(yè)實(shí)際應(yīng)用出發(fā)，結(jié)合企業(yè)日常經(jīng)營(yíng)過(guò)程產(chǎn)生的業(yè)務(wù)數(shù)據(jù)，并結(jié)合k-means算法挖掘海量數(shù)據(jù)中可能潛在的分類規(guī)則與分布情況，并結(jié)合企業(yè)實(shí)際應(yīng)用情況提出K-means算法的改進(jìn)思路，通過(guò)大量的業(yè)務(wù)數(shù)據(jù)進(jìn)行對(duì)比實(shí)驗(yàn)。從而更加快速有效地幫助企業(yè)分析顧客的消費(fèi)情況，建立聚類模型，從而優(yōu)化企業(yè)營(yíng)銷策略和顧客關(guān)系維護(hù)方案，一定程度上提高營(yíng)銷的針對(duì)性、有效性。

1 基于k-means算法的聚類模型

1.1 K-means算法概述

K-means作為經(jīng)典的聚類算法， 它將各個(gè)聚類子集中的所有數(shù)據(jù)樣本的均值作為該聚類的代表點(diǎn)，使用誤差平方和準(zhǔn)則函數(shù)來(lái)評(píng)價(jià)聚類性能，給定數(shù)據(jù)集X，假設(shè)X中包含K個(gè)聚類子集C1、C2、…、Ck，各聚類子集的樣本數(shù)為N1、N2、…、Nk，各聚類子集的中心點(diǎn)（均值）分別為M1、M2、…、Mk（Xi），則誤差平方和準(zhǔn)則函數(shù)公式如下：

1.2算法偽代碼描述

K-means的偽代碼描述如下：

輸入：類的數(shù)目k和包含n個(gè)對(duì)象的數(shù)據(jù)集。

輸出：k個(gè)類，使平方誤差準(zhǔn)則最小。

（1） Assign initial value for means;

//任意分配到K個(gè)對(duì)象作為簇的平均值

（2）Repeat;

（3）For j=1 to n DO assign each Xj to the closest clusters;

（4）For i=1 to K DO? ? ? ? ? ? ? ? ? ? ?//更新簇平均值

（5）Compare? ? ? ? ? ? ? ? ? ? ? ? ? ? //計(jì)算準(zhǔn)則函數(shù)

（6）Until E不再變化;

1.3 算法優(yōu)化思路

K-means算法有兩個(gè)明顯的缺點(diǎn)，這兩點(diǎn)均與初始值相關(guān)：

其一是聚類的數(shù)量K需要事先設(shè)定，而通常情況下，我們是無(wú)法預(yù)知數(shù)據(jù)集應(yīng)該被分為多少類別;

其二是初始隨機(jī)點(diǎn)的選擇，算法的開(kāi)銷和性能直接取決于隨機(jī)點(diǎn)，不同的初始隨機(jī)點(diǎn)的選擇帶來(lái)的算法運(yùn)行結(jié)果也不盡相同。

此外，從算法的執(zhí)行過(guò)程可以看出，需要不斷調(diào)整樣本分類，重復(fù)計(jì)算樣本數(shù)據(jù)與類中心的距離，在數(shù)據(jù)樣本集較大的情況下，算法的時(shí)間開(kāi)銷是需要引起注意的。

K-means算法的時(shí)間復(fù)雜性：O（nkt），其中n=|S|，k為聚類的數(shù)量，t為迭代的次數(shù)。每次迭代均要計(jì)算S中的每個(gè)樣本同每個(gè)中心點(diǎn)的距離，然后將其歸類為最小距離的中心點(diǎn)。結(jié)合實(shí)際應(yīng)用情況設(shè)定合適的K值，此外，對(duì)于簇中心初始值的設(shè)定，我們選擇首先將數(shù)據(jù)集進(jìn)行排序操作，然后取四分位數(shù)進(jìn)行賦值，四分位數(shù)是將數(shù)列等分成四個(gè)部分的數(shù)，一個(gè)數(shù)列有三個(gè)四分位數(shù)，設(shè)下四分位數(shù)、中位數(shù)和上四分位數(shù)分別為Q1、Q2、Q3，則：Q1、Q2、Q3的位置可由下述公式確定：

式中n表示資料的項(xiàng)數(shù)，以減少t的值來(lái)縮短算法運(yùn)行時(shí)間。

K-means改進(jìn)算法的偽代碼描述如下：

（1）設(shè)定K=3;

//結(jié)合實(shí)際應(yīng)用情況設(shè)定分類數(shù)

（2）對(duì)數(shù)據(jù)進(jìn)行排序，取上四分位數(shù)、中位數(shù)、上四分位數(shù)為簇中心初始值;

（3）Repeat;

（4）For j=1 to n DO assign each Xj to the closest clusters;

（5）For i=1 to K DO? ? ? ? ? ? ? ? ? ? ?//更新簇平均值

（6）Compare? ? ? ? ? ? ? ? ? ? ? ? ? ? //計(jì)算準(zhǔn)則函數(shù)

（7）Until E不再變化;

K-means算法改進(jìn)后的流程圖描述如下：

2? 模型實(shí)驗(yàn)與結(jié)果分析

2.1 數(shù)據(jù)準(zhǔn)備

實(shí)驗(yàn)數(shù)據(jù)為某大型百貨商場(chǎng)2011、2012、2013三年內(nèi)的交易數(shù)據(jù)，使用k-means算法對(duì)顧客會(huì)員證交易積分進(jìn)行分類，通過(guò)季度累計(jì)積分值的合理分類確定合適的營(yíng)銷手段。積分匯總值的實(shí)際情況分布復(fù)雜，對(duì)于商場(chǎng)的營(yíng)銷可定義以下三種類型：

活躍型：消費(fèi)活動(dòng)頻繁，購(gòu)買欲強(qiáng)，積分值高;

穩(wěn)定型：消費(fèi)活動(dòng)不規(guī)律，有一定的購(gòu)買欲望，營(yíng)銷需要關(guān)注對(duì)象;

停滯型：消費(fèi)活動(dòng)少，購(gòu)買欲望弱。

由此可設(shè)置分類數(shù)K=3，季度積分累計(jì)匯總數(shù)據(jù)集的獲取主要經(jīng)過(guò)以下三個(gè)步驟：

1）通過(guò)sql語(yǔ)句查詢數(shù)據(jù)庫(kù)獲取初始數(shù)據(jù)集，每張會(huì)員證的積分依據(jù)季度進(jìn)行匯總，卡號(hào)進(jìn)行分組。查詢語(yǔ)句如下：

Select mbrid，

（select sum（itg） from mbrsaldtl where mbrid=a.mbrid and trddtm between '201201000000' and '201204000000'） as first，

（select sum（itg） from mbrsaldtl where mbrid=a.mbrid and trddtm between '201204000000' and '201207000000'） as second，

（select sum（itg） from mbrsaldtl where mbrid=a.mbrid and trddtm between '201207000000' and '201210000000'） as third，

（select sum（itg） from mbrsaldtl where mbrid=a.mbrid and trddtm between '201210000000' and '201301000000'） as last

from mbrsaldtl a

where trddtm like '2012%'

group by mbrid

order by mbrid;

查詢結(jié)果數(shù)據(jù)截圖如下：

2）將以上查詢結(jié)果導(dǎo)出為xls表格數(shù)據(jù)，分布對(duì)如下兩種情況進(jìn)行數(shù)據(jù)清洗：

（1）季度積分值不全的數(shù)據(jù)進(jìn)行清洗（即連續(xù)三個(gè)月未發(fā)生任何交易），這部分?jǐn)?shù)據(jù)具有不穩(wěn)定性，對(duì)無(wú)交易積分值進(jìn)行補(bǔ)0處理，以免流失重要數(shù)據(jù);

（2）積分?jǐn)?shù)值為負(fù)值的數(shù)據(jù)（即只進(jìn)行退貨，或者退貨返還積分值大于本季度交易獲得積分值），因?yàn)橥素浢總€(gè)月都可能發(fā)生，季度匯總最終的積分值可能是消費(fèi)交易產(chǎn)生的，也可能是沖抵部分退貨后凈得的，所以對(duì)于負(fù)值積分也進(jìn)行補(bǔ)0處理，如果要再進(jìn)行退貨原因等情況的分析則需要重新規(guī)劃數(shù)據(jù)組成;

3）每張會(huì)員卡取一年四個(gè)季度積分匯總值作為一行數(shù)據(jù)，最終保存為txt文本文件數(shù)據(jù)集，數(shù)據(jù)項(xiàng)之間以“，”進(jìn)行分割，供算法程序運(yùn)行時(shí)讀取。這樣可以避免數(shù)據(jù)庫(kù)網(wǎng)絡(luò)連接及sql語(yǔ)句執(zhí)行等因素對(duì)算法執(zhí)行時(shí)間的影響。以下為最終數(shù)據(jù)集前20行的截圖：

2.2 聚類模型建立

通過(guò)在Eclipse中進(jìn)行txt文件數(shù)據(jù)集的讀取，然后運(yùn)行k-means算法的java實(shí)現(xiàn)程序，并將最終分類結(jié)果寫入cluster_result.txt文件中。輸出結(jié)果顯示算法運(yùn)行耗時(shí)為47ms。程序控制臺(tái)輸出結(jié)果截圖如下：

此外，還可以通過(guò)程序進(jìn)行算法運(yùn)行結(jié)果的圖像輸出顯示，從而更加直觀地顯示數(shù)據(jù)聚類的分布情況，程序圖形輸出結(jié)果截圖如下：

2.3 改進(jìn)算法對(duì)比

通過(guò)對(duì)初始種子點(diǎn)值的設(shè)置，有效地減少了迭代的次數(shù)，算法運(yùn)行耗時(shí)為16ms，由此可見(jiàn)初始種子點(diǎn)的值對(duì)算法的影響是至關(guān)重要的，后輸出截圖如下：

3 結(jié)束語(yǔ)

本文結(jié)合企業(yè)實(shí)際應(yīng)用對(duì)k-means算法應(yīng)用提出一種改進(jìn)思路，并用企業(yè)實(shí)際銷售產(chǎn)生的交易數(shù)據(jù)進(jìn)行對(duì)比實(shí)驗(yàn)，證明優(yōu)化是切實(shí)有效的。并通過(guò)建立聚類模型，劃分會(huì)員證類型，從而開(kāi)展有針對(duì)性的營(yíng)銷，一定程度上增強(qiáng)了企業(yè)的營(yíng)銷的針對(duì)性，如果再進(jìn)行深層次的挖掘，則可以依據(jù)商場(chǎng)的商品大類對(duì)會(huì)員證的消費(fèi)習(xí)慣進(jìn)行細(xì)分，例如：百貨、服裝、鞋帽、家電、超市等，而對(duì)于某一具體的商品大類又可細(xì)分為幾個(gè)小類，例如服裝，可劃分為男裝、女裝、運(yùn)動(dòng)裝等，這樣在季節(jié)新品的宣城方面就可以進(jìn)行更加有針對(duì)性的宣傳與推廣，這樣對(duì)于提高商場(chǎng)的銷售業(yè)績(jī)無(wú)疑是有重大意義的。

k-means算法的改進(jìn)有很多方面，例如中心點(diǎn)調(diào)整及重復(fù)的距離計(jì)算、確定收斂性的規(guī)則等，結(jié)合企業(yè)實(shí)際應(yīng)用，從某個(gè)方面著手能夠有效提高算法的實(shí)用性。后續(xù)可能還會(huì)開(kāi)展網(wǎng)絡(luò)安全、電子商務(wù)、CRM等方面的深入研究，以期建立更多具有實(shí)際指導(dǎo)意義的應(yīng)用模型及相關(guān)算法的改進(jìn)思路。

參考文獻(xiàn)：

[1] Jiawei Han，Micheline Kamber，Jian Pei.范明，孟小峰譯.數(shù)據(jù)挖掘：概念與技術(shù) concepts and techniques[M].北京：機(jī)械工業(yè)出版社，2012.

[2] 韓家煒，孟小峰，王靜，等.Web挖掘研究[J].計(jì)算機(jī)研究與發(fā)展，2001，38（4）：405-414.

[3] Bing Liu.俞勇，薛貴榮，韓定一譯.Web數(shù)據(jù)挖掘[M].北京：清華大學(xué)出版社，2009.

[4] 周煒奔，石躍祥.基于密度的K-means聚類中心選取的優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究，2012，29（5）：1726-1728.

[5] 賴玉霞，劉建平.K-means算法的初始聚類中心的優(yōu)化[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（10）：147-149.

【通聯(lián)編輯：李雅琪】