羅俊

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

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

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

文章編號：1009-3044（2021）18-0029-03

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

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

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

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

1.1 K-means算法概述

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

1.2算法偽代碼描述

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

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

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

（1） Assign initial value for means;

//任意分配到K個對象作為簇的平均值

（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? ? ? ? ? ? ? ? ? ? ? ? ? ? //計算準(zhǔn)則函數(shù)

（6）Until E不再變化;

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

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

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

其二是初始隨機點的選擇，算法的開銷和性能直接取決于隨機點，不同的初始隨機點的選擇帶來的算法運行結(jié)果也不盡相同。

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

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

式中n表示資料的項數(shù)，以減少t的值來縮短算法運行時間。

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

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

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

（2）對數(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? ? ? ? ? ? ? ? ? ? ? ? ? ? //計算準(zhǔn)則函數(shù)

（7）Until E不再變化;

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

2? 模型實驗與結(jié)果分析

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

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

活躍型：消費活動頻繁，購買欲強，積分值高;

穩(wěn)定型：消費活動不規(guī)律，有一定的購買欲望，營銷需要關(guān)注對象;

停滯型：消費活動少，購買欲望弱。

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

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

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ù)，分布對如下兩種情況進(jìn)行數(shù)據(jù)清洗：

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

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

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

2.2 聚類模型建立

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

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

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

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

3 結(jié)束語

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

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

參考文獻(xiàn)：

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

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

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

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

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

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