基于企業應用的K-means算法的實現與改進

羅俊

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

關鍵詞：電子商務;聚類;算法改進;K-means算法

中圖分類號：TP311? ? ? 文獻標識碼：A

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

開放科學（資源服務）標識碼（OSID）：

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

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

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

1.1 K-means算法概述

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

1.2算法偽代碼描述

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

輸入：類的數目k和包含n個對象的數據集。

輸出：k個類，使平方誤差準則最小。

（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? ? ? ? ? ? ? ? ? ? ? ? ? ? //計算準則函數

（6）Until E不再變化;

1.3 算法優化思路

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

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

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

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

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

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

K-means改進算法的偽代碼描述如下：

（1）設定K=3;

//結合實際應用情況設定分類數

（2）對數據進行排序，取上四分位數、中位數、上四分位數為簇中心初始值;

（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? ? ? ? ? ? ? ? ? ? ? ? ? ? //計算準則函數

（7）Until E不再變化;

K-means算法改進后的流程圖描述如下：

2? 模型實驗與結果分析

2.1 數據準備

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

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

穩定型：消費活動不規律，有一定的購買欲望，營銷需要關注對象;

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

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

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

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;

查詢結果數據截圖如下：

2）將以上查詢結果導出為xls表格數據，分布對如下兩種情況進行數據清洗：

（1）季度積分值不全的數據進行清洗（即連續三個月未發生任何交易），這部分數據具有不穩定性，對無交易積分值進行補0處理，以免流失重要數據;

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

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

2.2 聚類模型建立

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

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

2.3 改進算法對比

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

3 結束語

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

k-means算法的改進有很多方面，例如中心點調整及重復的距離計算、確定收斂性的規則等，結合企業實際應用，從某個方面著手能夠有效提高算法的實用性。后續可能還會開展網絡安全、電子商務、CRM等方面的深入研究，以期建立更多具有實際指導意義的應用模型及相關算法的改進思路。

參考文獻：

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

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

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

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

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

【通聯編輯：李雅琪】