煙草零售數據挖掘與聚類噪聲消除方法研究

趙海建 向俊宇 楊迎鐳

摘? 要： 煙草零售環節積累了大量交易數據，但其中隱藏的有價值的信息還未被有效挖掘。本文針對某省煙草零售戶卷煙進銷存流水數據進行數據挖掘研究。在原始數據清洗和預處理之后，對于零售戶分類中遇到的噪聲數據，運用K-means算法進行聚類。對聚類中的噪聲干擾，提出了離群點消除方法，將離群點劃分到另外的Voronoi單元中，增強正常數據點的聚類有效性。該系統在營銷實踐過程中得以應用，證明了方法的有效性。

關鍵詞： 零售數據； 數據挖掘； K-means； 離群點檢測； Voronoi單元

中圖分類號：TP391? ? ? ? ? 文獻標識碼：A? ? ?文章編號：1006-8228（2023）09-120-05

Research on retail data mining and clustering noise elimination method

Zhao Haijian， Xiang Junyu， Yang Yinglei

（Chongqing China Tobacco Industry Co.， Ltd.， Chongqing 400060， China）

Abstract： A large amount of transaction data has been collected in the tobacco retail segment， but the hidden valuable information has not been effectively mined. In this paper， a series of data mining research is carried out for the transaction data of tobacco retailers in a province. After the original data cleaning and preprocessing， the K-means algorithm is applied to cluster the noisy data encountered in the classification of retailers. For the noise interference in clustering， an outlier elimination method is proposed to divide the outliers into other Voronoi units to enhance the clustering effectiveness of normal data points. The system is applied in the process of marketing practice， which proves its effectiveness.

Key words： retail data; data mining; K-means; outlier detection; Voronoi Unit

0 引言

煙草零售是煙草銷售的重要組成部分，其零售網絡經過多年建設，已經取得較大成效，大量交易數據被記錄下來。但這些數據處于分散割裂狀態，往往不能有效傳遞到供應鏈上其他環節，由于數據的零散、異構、數據缺失、噪聲多等原因，也難以開展有針對性的分析挖掘，成為煙草供應鏈決策的薄弱環節。

反觀我國電商平臺之所以能成功，不僅僅因為其將交易的場所從線下轉到了線上，更在于其借助互聯網巨大的優勢，融合大數據等技術實現“智慧零售”[1]。如果能合理運用數據挖掘技術，深入挖掘其中蘊藏的潛在價值信息，將為企業貨源投放、市場調控、品牌營銷、風險評估和預警等方面提供數據支持，為企業提供有針對性的決策意見或建議，有助于零售環節的創新發展。

1 研究現狀

1.1 煙草零售的發展現狀和創新思路

經過多年的煙草零售網絡建設，煙草零售環節已積累了大量的經營數據，目前缺乏有效、合適的手段發揮其作用，其中潛在的商業價值未能充分挖掘，現有的一些研究，如：按照客戶價值進行分類聚類，實現客戶細分，從而可以為不同類別的零售戶提供有針對性的個性化服務。閆磊等[2]從客戶價值評價指標的維度對零售客戶進行了聚類，將大量指標按照分成貢獻度、影響度、支持度、成長度和規范度幾類，從客戶當前價值以及潛在價值的角度進行量化分析和聚類。劉坤達等[3]突出了品牌特征，選用少量指標進行K-means聚類分析。張鍵等[4]基于客戶畫像構建了一套監管模型，有效提升了市場監管成效。

1.2 K-means聚類方法的研究

K-means是常用的數據分析技術，它簡單直觀，速度較快，并可調整它的許多參數以適配實際問題。Moodleya等[5]為了更好地開展零售業務營銷，提出了一種有針對性的促銷算法，利用模糊C-means聚類和Apriori關聯規則挖掘算法等，有效識別商品的最佳目標客戶。劉瀟、王路遙、Hossain等也分別利用K-means方法對零售戶開展分類的特征提取[6-8]。

K-means算法有一個重要的缺陷，它無法處理數據中的噪音。許多技術如DBSCAN已經被提出并被廣泛研究。然而，這些方法只是將K-means作為初始的一個步驟，而較少考慮如何進行改進以使其適應噪聲數據集。其中，Chawla等[9]提出了一種改進K-means方法，但要求將離群點的數量作為參數進行設置。Gan等[10]提出了KMOR算法，它要求輸入兩個額外的參數，其中一個是最大的離群值。ODC算法[11]將離群點和真實數據點之間的“差異”作為一個參數，而Neo-K-means[12]則要求輸入兩個參數α和β，它們與數據點在聚類中的分配有關，也就是離群點的數量。

2 K-means聚類離群點消除方法

本文提出了一種改進的K-means聚類方法，將K-means方法擴展到噪聲數據集，以去除聚類結果中的離群點，而無需額外的參數。

2.1 K-means聚類方法

K-means聚類是一種劃分式的聚類算法，其原理簡單，算法效率高。但是，由于無法預先確定聚類的數量即k值，使用上也存在一定的局限性。

進行K-means聚類前需要進行數據預處理的準備工作，包括數據的準備、清洗、特征構建、特征標準化、確定k值等。最優k值的確定常采用手肘法和輪廓系數法。以手肘法為例，它采用SSE（誤差平方和）作為評估聚類好壞的標準，如公式⑴所示，其中Ci是第i個簇，mi是Ci的聚類中心：

[SSE=i=1kp∈Cip-mi2]? ⑴

SSE隨著k值的增大而減小，且剛開始會迅速下降，隨著k的增大，SSE下降的速度逐步減慢，從k-SSE的圖像上可以找到曲率較大一點，對應的k值可以作為最優的k值。因圖像上這一點的形狀向手肘，故稱手肘法。

對標準化后的數據集應用K-means算法，持續將樣本劃分到k個樣本集合（即簇）中，直到聚類中心的變化小于一定的閾值或達到設定的迭代次數，最終得到k個簇，每個簇包含一定的樣本量，簇的中心也就是樣本集合的特征均值，反映了這個簇的整體特征。

2.2 離群點消除

上述過程得到了k個聚類簇，但在簇中各數據點與聚類中心的距離相差較大，某些點與兩個乃至多個聚類中心距離接近，只是因為微小的差距而劃入其中某個簇，這樣的點顯然更應作為離群點被分離出去。本文提出一種方法，從上一節的聚類結果開始，探索離群點所在的區域。

由于聚類中心是由所有簇中數據點取平均得來的，因此，數據點越近中心，它被正確分類的可能性越大；反之，數據點與中心相距越遠，它被錯誤分類或成為離群點的可能性就越大。為此，對離群點的搜索應該從離聚類中心最遠的位置開始。K-means聚類簇將空間剖分為Voronoi單元，相鄰Voronoi單元之間是超平面。如圖1所示，在超平面的交匯處，可以找到離聚類中心最遠的點，該點可記為m。

在一個[d]維的數據空間中，[d+1]個Voronoi單元能夠確定這樣一個交點[m]，它是數據空間中的一個點，滿足[vj-m=r，j∈1，2，…，d+1]。其中[vj]是Voronoi單元的中心，即K-means方法發現的聚類中心，[r]是m與Voronoi單元中心的距離。如果其中一個Voronoi單元中心與[m]的距離不等于[r]，[m]將被分配到距離最小的Voronoi單元。

當找到這些交點時，假設這些交點的區域應被視為包含離群點。我們保留聚類的形態，在交點處新建一個Voronoi單元，但該單元中的所有數據點都被視為離群點（見圖1（b））。在原有的聚類簇之外，創建這樣的離群Voronoi單元有時可能是錯誤的，因為這樣的離群Voronoi單元可能也把一些正常的數據點包含進來。為此，必須設置一個標準來決定是否需要創建這樣的離群Voronoi單元。本文使用了最小描述長度（MDL）策略，它假設聚類的編碼成本取決于聚類的好壞，而編碼成本與聚類編碼所需的內存直接相關。應用該準則，可推算新建的Voronoi單元是否保留，然后開始下一次迭代。在圖1（b）中，找到了新的Voronoi單元交點，可以采取與之前相同的步驟。在此之前會更新聚類中心。這一過程迭代進行，直到找不到其他交點用于改善聚類。

2.2.1 尋找Voronoi單元交點

有幾種方法可以用于搜尋Voronoi單元的交點。最直觀的方法是用幾何計算法找到m。但如果在d維數據空間中有k個K-means中心，在不知道這些中心的相鄰關系的情況下，需要遍歷所有組合以找到Voronoi單元的組合，這種方法效率較低。

本文使用Avis-Fukuda算法，它專門用于尋找Voronoi交點。Avis-Fukuda算法將每個Voronoi單元的中心作為輸入，并計算這些Voronoi單元的交點，即從一個Voronoi單元的中心和約束它的其他中心開始，形成一個圍繞中心的凸多面體，該凸多面體的角就是要找的交點。它用線性優化方法計算出最近的頂點，然后沿著凸多面體的邊找到其他頂點。通過這種方式，可以找到凸多面體的所有角點，即所有Voronoi交點。

2.2.2 MDL準則

找到Voronoi單元的所有交點后，下一步要決定是否新建Voronoi離群單元。MDL假設，較低的編碼成本意味著更好的聚類。因此，如果新的Voronoi噪聲單元降低了總的編碼成本，算法就會保留新的Voronoi噪聲單元。編碼成本由兩部分組成。模型[LM]的編碼成本和數據[LD|M]的編碼成本。因此，總的編碼成本可通過公式⑵計算：

[LM，D=LM+L（D|M）]

[=i=1Kj=1Cilog2NCi+i=1Kpi2log2（Ci）-i=1Kx∈Cilog2（pdf（x））] ⑵

其中，[K]是聚類[Ci]的數量；[N]是數據點[x]的數量；[pi]是參數的數量。

編碼成本推導如下：只要知道聚類的大小，便可以計算模型編碼成本[LM]，它跟數據點的分布有關。一般K-means假設基于正態分布，該分布在所有方向上的方差都一樣。因此，基于這一假設，數據點與中心的距離就足以確定其概率。聚類的正態分布取決于兩個參數，即均值和聚類方差。聚類均值就是聚類中心，基于聚類可計算方差。假設[x]是正態群中的一個隨機點，聚類在每個維度都是[N0，α]的正態分布，即方差為[α]的正態分布，因此找到[α]就是方差。計算[x]到中心的距離[distx，0=i=1dαXi2]，其中[Xi]服從[N0，α]分布，因此[αXi]也是[N0，α]分布的，從而更新[distx，0]的計算方法，如公式⑶：

[distx，0=i=1d（αXi）2]

[=α2i=1d（Xi）2=αi=1dXi2] ⑶

[Y=i=1dXi2]被稱為卡方分布，把它標為[pdfx]。不同的是，這里有系數[α]。如果[i=1dXi2～pdfx]，則[αi=1dXi2～1αpdfxα]，由此得到了概率分布。利用方差公式，可得概率密度函數，如公式⑷：

[pdfx=xd-1e-xd2α2xd2-1αdΓ（d2）] ⑷

其中，[Γ]是標準的伽馬函數。

至于應該用哪種[pdf]來模擬噪聲，一般采用均勻分布的噪聲，但它可能會被異常值扭曲。為了降低異常值的影響，本方法假設噪聲也服從正態分布。噪聲分布的參數計算同前，即平均值是所有數據點的平均值，噪聲的方差是所有數據點的方差。

3 數據分析與數據挖掘的設計與實現

煙草零售環節海量原始數據存在不完整、含噪音、不一致等問題，需要通過數據清洗、轉換、歸納等手段進行預處理，從而解決數據的不規范問題。本文所使用的原始數據為2020年8月至2021年3月某省級煙草公司零售戶卷煙零售的進銷存流水數據，共計3357萬余條。初步分析數據，存在大量重復值、缺失值和少量異常值，以及不一致的情況。為此，對于重復記錄，經過謹慎清洗，共刪除3.01%的數據；對于占大量的結存、銷售價格缺失情形，基于前后數據進行填補；對于異常值，通過數據校驗，依次消除。

隨后作了多維聚合分析，以時間、產品、銷售三個維度來進行：時間維度劃分為日、周、月；產品維度劃分為規格、品牌、制造企業；銷售維度劃分為零售戶、縣、地市、省等。將經過清洗后的流水數據作為事實表，構建星型模型，開展了OLAP數據分析國，主要的分析指標包括基礎指標（購進量、銷售量、售價等）、零售戶指標（活躍客戶數、經銷客戶數、凈增長率等）、品牌銷售指標（覆蓋率、鋪貨率等）等類別。

本文構建了帶品牌特征的聚類模型，使用客戶與品牌連接的數據作為聚類樣本，有效擴大了聚類特征值的多樣性，增大了樣本集合。選擇聚類特征時，通過構建五個二級特征指標，反映樣本的品牌傾向性、當前價值、潛在價值三個方面。數據集首先按照月份進行分組，分別對每月的數據進行聚類分析。針對數據的量綱不同，因此通過Z-score標準化方法進行標準化和無量綱化處理。然后采用手肘法確定聚類最優k值，通過比較每個月的k-SSE圖像，并多次試驗，最終確定k取5。圖2以2月份為例展示k-SSE圖像。

經過K-means算法多輪迭代后，得到了各月的聚類結果。各簇的聚類中心如表1所示。

使用雷達圖進行繪制，如圖3所示，可以觀察到各個簇的特征。

為每個簇確定類別的過程，如果僅參考特征排名，則存在不穩定性（如圖3 SHCZ指標中G1為次高、G0為最差，但他們的值幾乎接近），因此還參考了指標的相對大小的等級（簡稱指標等級）。指標等級指一組簇類的某一指標經min-max歸一化后的值所處的范圍等級，0～0.2之間表示E，0.2～0.4之間表示D，以此類推。從而將簇的特征數據轉化為等級與排名的形式，以便賦予類別標簽。從品牌傾向度、商戶當前價值、商戶潛在價值三個角度，用H、X、L分別表示高、中、低，分別根據指標等級、排名進行評估、綜合與擬合后確定類別。各類的大致特征為：HHX（A類）、LHX（B類）、HLH（C類）、LLH（D類）、XLL（E類）。所刻畫的五類分別為：重點客戶的主銷品牌、重點客戶的非主銷品牌、成長型客戶的主銷品牌、成長型客戶的非主銷品牌、低價值和低潛力客戶。

該分類方法已在企業十余個基層銷售組織中進行推廣應用，在三個多月的試用過程中收集銷售人員的意見與反饋，并進行統計分析。分析結果表明，本方法所分類的85%以上的產品符合銷售人員的原有判斷，并有所細化。其余分類有差異的主要涉及中等偏下的產品。按照本方法的分類開展相應營銷工作后，銷量有10%以上幅度增長，說明本方法將數據中的一些隱含信息挖掘了出來，并有效指導了營銷工業的開展。

4 總結

本文針對省級煙草公司所轄零售戶卷煙的進銷流水數據開展了一系列數據挖掘工作。在調研銷售分析相關方法的基礎上，選擇K-means聚類算法作為零售戶分類的基礎方法，在聚類成果之上進行離群點消除。在此基礎上開展數據分析和數據挖掘，完成了數據清洗與預處理、多維分析處理和數據展示。本文所開發的系統已在該煙草公司應用實施，取得了良好的應用效果。

參考文獻（References）：

[1] 李衛華.大數據背景下傳統零售企業精準營銷探析[J].商業

經濟研究，2019（15）：71-74.

[2] 閆磊，劉旭，徐斌.基于客戶價值的卷煙零售客戶分類研究與

應用[J].價值工程，2019，38（25）：89-90.

[3] 劉坤達，宋紅文，張衛東，等.品牌優先的零售客戶細分研究[J].

現代商貿工業，2021，42（32）：45-46.

[4] 張健，魏生強，張瀛.精準畫像提高煙草專賣監管效能——

基于粗糙集的大數據分類監管體系研究[J].海峽科學，2021（8）：69-73.

[5] Raymond Moodleya， Francisco Chiclanacb， Fabio Caraf-

finia， et al. A product-centric data mining algorithm for targeted promotions[J]. Journal of Retailing and Consumer Services，2020，54（5）：1-13.

[6] 劉瀟，王效俐.基于K-means和鄰域粗糙集的航空客戶價值

分類研究[J].運籌與管理，2021，30（3）：104-111.

[7] 王路遙，高山，李俊，等.基于K-means聚類與空間相關性的

零售戶銷售行為分析[J].測繪通報，2019（9）：51-54.

[8] Hossain， M. Z.， Akhtar， M. N.， Ahmad， R. B.， et al. A

dynamic K-means clustering for data mining[J]. Indonesian Journal of Electrical Engineering and Computer Science，2019，13（2）：521-526.

[9] Sanjay Chawla， Aristides Gionis. K-means--： a unified

approach to clustering and outlier detection[C].Proceedings of the 2013 SIAM International Conference on Data Mining，2013：190-197.

[10] Guojun Gan， Michael Kwok-Po Ng.K-means clustering

with outlier removal[J]. Pattern Recognition Letters，2017，90（4）：8-14.

[11] Mohiuddin Ahmed， Abdun Naser Mahmood. A novel

approach for outlier detection and clustering improvement[A]. 2013 IEEE 8th Conference on Industrial Electronics and Applications （ICIEA）[C]. Melbourne， VIC， Australia：IEEE，2013：577-582.

[12] Joyce Jiyoung Whang， Yangyang Hou， David F. Gleich，

etc. Non-exhaustive， Overlapping Clustering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2019，41（11）：2644-2659.