基于改進K-Means聚類算法的互聯網涉煙違法犯罪區(qū)域劃分研究

呂飛

[摘 要]近年來，利用物流和快遞從事卷煙非法交易的違法犯罪活動日益猖獗，隨著煙草行業(yè)打假打私力度不斷增大，各級煙草專賣管理部門在物流寄遞渠道均查獲了大量的涉煙案件數據。由于目前行業(yè)內外鮮有對該類案件進行大數據分析研究，因此，本文以理論結合實際，首先介紹了數據挖掘技術中聚類算法相關理論，重點對經典K-Means算法及其相關改進算法進行了研究，然后以W市煙草專賣局的真實涉煙案件數據進行實驗仿真，通過分析歷史各類案發(fā)地址等信息，幫助煙草專賣執(zhí)法人員在涉煙案件經營偵辦、卷煙消費市場監(jiān)管等方面開展精準打擊、重點治理。

[關鍵詞]煙草專賣;市場監(jiān)管;數據挖掘;聚類分析;K-Means算法

doi：10.3969/j.issn.1673 - 0194.2019.22.077

[中圖分類號]TP391.3[文獻標識碼]A[文章編號]1673-0194（2019）22-0-05

0? ? ?引 言

近年來，不法分子利用物流寄遞渠道，將非法卷煙銷往全國各地，嚴重干擾了正常卷煙市場秩序，使國家稅收流失，消費者利益受到侵害。為進一步加強對物流寄遞領域涉煙違法行為的監(jiān)管，自2016年起，煙草行業(yè)逐漸加大了對利用互聯網制售假冒卷煙犯罪活動的打擊力度，積累了大量的物流寄遞渠道涉煙案件數據。但是，由于缺少大數據的整理整合以及內在價值的挖掘分析能力，在目前的煙草專賣市場監(jiān)管和案件偵辦工作中，“數據豐富、情報匱乏、手段單一”的現象仍然存在。如何有效利用這些歷史案件數據，全面、客觀、系統(tǒng)地挖掘互聯網涉煙案件線索，深入拓展卷煙市場監(jiān)管的新領域，以實現新時期煙草專賣管理的高質量發(fā)展，是目前迫切需要研究的課題。數據挖掘作為當前一種新穎高效的數據分析手段，如今被廣泛應用在各行各業(yè)，例如數據庫營銷、客戶關系管理、顧客行為預測及市場趨勢預測等，在公安部門情報偵察、案件偵辦領域也發(fā)揮著舉足輕重的作用。因此，利用數據挖掘方法對物流寄遞渠道的海量涉煙案件數據進行深入研究，充分挖掘犯罪數據中的犯罪規(guī)律、行為特征等情報價值，給煙草專賣市場監(jiān)管提供幫助，是讓沉淀的歷史案件數據發(fā)揮最大價值的有效途徑。對于如何運用大數據分析方法對煙草專賣管理領域的案件數據進行價值挖掘，行業(yè)內外鮮有相關研究，而采用類似方法的研究課題大多集中在卷煙營銷領域。本文基于數據挖掘中的聚類分析K-Means算法，圍繞互聯網涉煙案件中的大量案發(fā)地址數據，開展智能化自動分類和輔助預警，以幫助一線煙草專賣執(zhí)法人員迅速了解和掌握管轄市場的違法犯罪活動高發(fā)區(qū)域和活動中心，準確開展市場信息分析，全面推動卷煙市場監(jiān)管由“人工經驗”向“數字決策”轉變。

1? ? ?聚類算法概述

1.1? ?聚類算法

聚類算法是一種非監(jiān)督機器學習算法，實質是按照特定的標準把一組數據對象劃分成若干類子集或簇的過程，使同一個子集或簇的數據對象相似度盡可能大，不同子集或簇的數據對象差異性也盡可能大。即聚類后具有相似屬性的數據對象盡可能聚到一起，不同的數據對象盡量分離。聚類算法有很多種，分為劃分法、層次法、基于密度的方法、基于網格的方法、基于模型的方法等。每一類中都有目前廣泛應用的算法，例如，劃分方法中的K-Means聚類算法、層次方法中的凝聚型層次聚類算法、基于密度方法中的DBSCAN聚類算法等。

1.2? ?經典K-Means算法

經典K-Means算法由于簡單易實現且效率高，是聚類算法中最流行、使用最廣泛的算法。該算法主要采用距離作為相似性的評價指標，認為子集或簇是由距離靠近的對象組成，最終目標是獲得緊湊且獨立的子集或簇。即以k為參數，把n個對象分成k個子集或簇，使子集或簇內具有較高的相似度，而子集或簇間的相似度較低。經典K-Means算法主要分為4個步驟。

步驟1：從樣本數據集中隨機抽取k個值作為初始簇的質心。

步驟2：將每個剩余的樣本數據劃分到距離最近質心所在的簇。

步驟3：重新計算每個簇內樣本數據的質心。

步驟4：重復步驟2和3，直到每個簇內樣本數據的質心不再變化或達到設定的迭代次數后停止。

在計算過程中，距離的計算采用歐式距離，在二維空間的計算公式如下。

ρ為迭代次數，k為簇的數目，n為數據個數。經典K-Means算法的計算時間與n線性相關，所以該算法速度很快。

但是，經典K-Means算法在開始之前，需要人工指定兩個參數：初始質心和簇數目k。初始質心通過隨機選取，簇數目k也憑經驗設定。這樣做的缺點是，如果初始質心的位置選擇不當，例如都在一個簇里面，那么不僅會大大增加迭代次數，最終的聚類結果也比較糟糕，往往只能得到局部最優(yōu)解。同樣，簇數目k在聚類之前就設定也不符合工作實際，例如，專賣執(zhí)法人員在開展海量案件數據分析之前，不可能知道案發(fā)區(qū)域大致可以劃分為哪幾個塊。因此，需要對經典K-Means算法進行改進，科學選擇初始質心并初步確定最優(yōu)k值。

1.3? ?初始質心的選擇

初始質心的選擇方法有很多種，有經典的隨機選擇、層次聚類、基于最近鄰密度等。本文主要基于K-Means++算法進行初始質心選擇改進，具體步驟如下。

步驟1：從數據集中隨機選取一個樣本點作為初始質心C1。

步驟2：計算每個樣本與當前已有質心之間的最短距離（即最近質心的距離），即D（x）.

步驟3：計算每個樣本點被選為下一個質心的概率：。

步驟4：按照輪盤法選擇出下一個質心。

步驟5：重復步驟2、3、4，直到選擇出k個質心;

步驟6：基于選定的質心執(zhí)行經典K-Means算法。

由以上步驟可以得知，除第一個質心是隨機選擇以外，后繼是距離當前已有質心越遠的樣本點有更高概率被選擇，當然這也非常符合人們的直覺，即簇中心相互離得越遠越好。

綜上所述，K-Means++與經典K-Means的區(qū)別就在于初始質心的選擇上，確定好初始質心之后，其余步驟都同經典K-Means一樣。例如，對于有12個樣本點的數據集，坐標分布及序號如圖1所示。由圖1憑經驗可知，該數據集可以劃分為3個簇。假設第一個初始質心隨機選擇了6號樣本，若按照經典K-Means算法，則后續(xù)初始質心中除6號以外的其余樣本點被選中的概率均等。若后續(xù)初始質心仍然選中在B簇中的樣本點，則對合理聚類十分不利。在K-Means++算法中，從第二個初始質心選擇開始，需要進行以下概率計算。

從表1可以得知，下一個聚類中心點落在1～4點的概率區(qū)間為[0，0.391 304]（例如其分別落在點1、點2的概率為[0，0.086 957][0.086 957，0.228 261]），落在5～8點的概率區(qū)間為[0.402 174，0.434 783]，落在9～12點的概率區(qū)間為[0.521 739，1]。也就是說，選到前4個點和后4個點的概率總和非常接近1，而這也是人們希望看到的，體現了質心相互離得越遠越好。此時，只要隨機生成一個0～1之間的數（如matlab中的rand函數），就能確定好下一個質心（離當前已有質心較遠的點有更大的概率被選為下一個質心）。以此類推，當k個初始質心選好之后，繼續(xù)進行經典K-means算法。

1.4? ?最優(yōu)k值的確定

k值的設定直接決定了K-Means算法的聚類簇個數，如果設置不當將直接影響聚類結果。以圖1樣本數據集為例，將k值分別設置為2和4時，聚類結果如圖2和圖3所示。由圖2和圖3可以得知，若k值設置不當，聚類結果明顯不符常理。其實很多情況下，對數據集進行簇劃分本身并沒有絕對清晰和正確的結論，這取決于人們對數據集本身意義的個體認知。因此，研究能夠自動求解正確k值的算法是非常困難的，只能從多個角度對k取值進行評估。本文采用基于SSE指標的評價方法對k值進行評估，并給出最優(yōu)k值建議。

SSE（sum of the squared errors，誤差平方和）計算公式如下。

其中，Ci是第i個簇，p是Ci中的樣本點，mi是Ci的質心（k中所有樣本的均值）。

核心思想是采用肘部法則，即隨著聚類數k的增大，數據集的劃分會更加精細，每個簇的聚合程度會逐漸提高，隨之誤差平方和SSE自然會逐漸變小。首先，當k小于真實的聚類數時，由于k的增大會大幅增加每個簇的聚合程度，故SSE的下降幅度會很大。然后，當k到達真實聚類數時，再增加k所得到的聚合程度回報會迅速變小，此時SSE的下降幅度會驟減。最后，隨著k值的繼續(xù)增大而趨于平緩。也就是說SSE和k的關系圖是一個類似手臂肘部的形狀，而這個肘部對應的k值就是數據集的最優(yōu)聚類數。當然，肘部法則也存在一定缺陷，由于需要對每個k值進行聚類，考慮到計算復雜度，所以k取值上限一般不超過10。不過對于研究地理區(qū)域劃分這一課題，本身對聚類結果的簇數量沒有過多要求，一般也在10以內，故該缺陷對本次研究沒有多少影響。

仍然以圖1數據為例，利用肘部法選取最優(yōu)聚類數k。具體做法是讓k從1開始取值，直到上限8，對每一個k值進行聚類并且計算對應的SSE，然后畫出k和SSE的關系圖，最后選取肘部對應的k值作為最優(yōu)聚類數。由表2和圖4可以得知，肘部對應的k值為3，因此對于圖1數據集而言，最佳聚類數應該選3，這與觀測結果相吻合。

1.5? ?改進后算法步驟

通過上述對經典K-Means算法和相關改進算法的研究，在一定程度上解決了局部最優(yōu)等問題，減少了聚類迭代次數，提高了聚類效率，對聚類簇個數也進行了評估并給出最優(yōu)解。改進后計算步驟如下。

步驟1：對于給定樣本數據集，設置初始k值為1。

步驟2：若k=1，則隨機選擇1個質心;若k>2，則計算每個樣本與已選質心最短距離D（x）和被選中的概率P（x），用輪盤法選擇后續(xù)質心。

步驟3：用選好的質心和k值進行經典K-Means聚類，并計算SSE。

步驟4：k自增1，重復步驟2、4，直到k>8停止。

步驟5：比較k值與SSE關系，根據肘部法則確定最優(yōu)k值。

步驟6：根據最優(yōu)k值進行改進后的初始質心選擇，并進行經典K-Means聚類。

2? ? ?實驗仿真

為了進一步驗證上述算法理論在實際涉煙違法犯罪區(qū)域劃分中的應用，本節(jié)選取W市煙草專賣局部分物流寄遞涉煙案件數據樣本進行實驗。W市位于A省南部，屬于A省物流寄遞業(yè)核心樞紐城市之一，大量寄往A省的物流快件均通過W市進行中轉。2017年起，W市煙草專賣局全面貫徹行業(yè)相關工作要求，不斷加大對物流寄遞渠道涉煙違法犯罪活動的打擊力度，違法卷煙查獲總量和人均查獲量穩(wěn)居A省前列，積累了大量的互聯網涉煙案件數據。同時，W市通過自行研發(fā)相關信息管理系統(tǒng)，在案件數據電子化歸檔的同時，對數據格式進行了統(tǒng)一標準化處理，因此，數據有效性和規(guī)范化得到了保證。W市煙草專賣局關于物流寄遞涉煙案件數據管理系統(tǒng)中，數據庫的主體數據表結構如表3所示（由于涉密原因，已略去部分無關字段）。

由表3可以看到，對于每起物流寄遞渠道涉煙案件，系統(tǒng)均記錄了收發(fā)貨地址信息及對應的GIS經緯度數據。本次實驗采用Python編程實現，從數據庫中隨機選取了200起W市煙草專賣局2018年1-5月查獲的物流寄遞涉煙案件數據樣本，提取了每起案件的收貨地址GIS坐標信息，繪制了散點圖，如圖5所示（由于案件地址GIS數據涉密原因，故事先對其進行了統(tǒng)一標準換算）。

圖5中，每個圓點即為一起案件的收貨地點，下面對其進行聚類分析。將k值設定為1～8后，統(tǒng)計每個k值的SSE結果，繪制關系圖，如圖6所示。

從表4可以得出，當k取值為4時，前后折線斜率最大，即最優(yōu)聚類簇個數為4個。接著將k值設定為4，進行經典K-Means算法，并同時計算每個聚類簇的質心，繪制聚類結果圖如圖7所示。由圖7可以得知，該200起案件數據樣本的案發(fā)地址大致可以劃分為4個區(qū)域，也就是說，在W市的卷煙消費市場中，這4個區(qū)域的消費者或非法經營者從互聯網購買非法卷煙的頻次較高。因此，在市場監(jiān)管實際工作中，專賣市管員、稽查員要對這4個區(qū)域，特別是以“★”為代表的中心區(qū)域進行重點走訪和調查。

3? ? ?指導實踐

3.1? ?發(fā)揮大數據情報導偵優(yōu)勢，助力物流寄遞涉煙犯罪精準打擊

由于物流、快遞業(yè)的快速發(fā)展以及其方便快捷、隱蔽性強、偽裝手段多等特點，越來越多的不法分子選擇通過物流寄遞渠道進行制售假冒偽劣卷煙。目前，W市煙草專賣局采取“現場檢查、人工排查”的方式，選派若干名專賣執(zhí)法人員進駐各物流快遞企業(yè)城市分撥中心，與公安部門、郵政管理部門等工作人員一起，對每天運抵的各類包裹進行集中排查。由于通過物流寄遞渠道進行涉煙非法犯罪活動通常具有“螞蟻搬家”等少量、多頻次的特點，因此，每起查獲的物流寄遞案件的收發(fā)貨面單信息均應納入重點檢查名單，特別是查獲頻次較高和收件地址較為集中的面單信息。在實際工作中，由于目前缺少先進的數據分析方法，負責現場檢查的執(zhí)法人員只能根據自身經驗，對印象中經常查獲的收件人和收件地址進行重點檢查，這種方法受個人能力影響較大，容易遺漏關鍵人員地址等信息，且不利于執(zhí)法人員之間的情報溝通交流。2018年7月，W市煙草專賣局在自行研發(fā)的案件管理系統(tǒng)中采用了包括改進K-Means聚類算法在內的大數據分析方法，在幾分鐘之類即可對歷史案發(fā)地址進行歸類總結，并建立了情報溝通交流信息群，將近期的案發(fā)熱點區(qū)域和臨近的收件地址直接分發(fā)至每位現場執(zhí)法人員處，確保了情報信息的研判及時、內容完整、溝通有效。2018年，W市煙草專賣局在物流寄遞渠道共查獲各類涉煙非法包裹7 706件，假冒卷煙762.1萬支，查獲總量和人均查獲量實現了A省的“雙第一”。

3.2? ?深化大數據在APCD工作法中的運用，助力卷煙消費市場精準治理

卷煙市場監(jiān)管工作是煙草專賣管理工作基石，是維護卷煙市場經營秩序的基本措施。為了全面變革多年以來專賣市場監(jiān)管“地毯式檢查”的粗放管理模式，煙草行業(yè)從2014年起全面推行“APCD”工作法，為傳統(tǒng)的工作模式注入新鮮血液，是煙草市場檢查方法的創(chuàng)新之舉。“APCD”工作法指通過將零售市場檢查工作劃分為“A分析”“P計劃”“C檢查”和“D處理”4個環(huán)節(jié)，通過對卷煙經營數據分析、綜合監(jiān)管信息分析隨時掌握市場異常情況，找出市場檢查的重點對象，由此可見，該工作方法重在A分析階段。在實際工作中，煙草專賣市場管理員雖然能夠通過業(yè)務系統(tǒng)對卷煙零售戶的經營數據進行實時監(jiān)測并分析異常，但是對卷煙零售戶的銷售行為數據和消費者的實際需求了解十分有限，缺少必要的信息獲取渠道。實際上，物流寄遞渠道查獲的涉煙案件數據中包含了大量的行為信息，收件人、收件地址、卷煙品牌規(guī)格等數據能夠為卷煙市場監(jiān)管工作提供大量的情報來源。由于缺少高效的分析手段，采用人工的方式在數以萬計的物流寄遞涉煙案件中進行犯罪行為規(guī)律查找和統(tǒng)計分析難以實現，大量的案件數據被束之高閣，其中蘊含的有價情報線索白白流失。

2018年7月以來，W市煙草專賣局采用聚類算法對物流寄遞涉煙案件的收貨地址進行自動劃分，并對劃分后各區(qū)域內的零售戶基本資料和經營數據進行對比，特別是對以“★”為代表的中心區(qū)域零售戶進行經營數據和違法行為的關聯分析，迅速定位疑似進行假冒偽劣卷煙批發(fā)行為的零售戶或嫌疑人，為一線市場檢查執(zhí)法人員在“A分析”階段提供了高效的研判結論，也為專賣案件稽查人員提供精準的情報來源，為全面實現情報導偵和精準打擊奠定了堅實的基礎。2018年，W市煙草專賣局市場檢查環(huán)節(jié)查獲案件數量同比增長11.7%，查獲卷煙數量同比增長50.3%，成效十分顯著。

4? ? ?結 語

本文運用聚類算法中的經典K-Means算法及其相關改進算法分析了互聯網涉煙案件地址數據，對案件發(fā)生區(qū)域進行了聚類劃分，并指出了中心區(qū)域。與傳統(tǒng)方法相比，基于聚類的K-Means算法在檢測的精準度上可能略有不足，但應用便捷、簡潔高效，對訓練數據集的要求低，特別是對于給定一定數量的案件數據，可以在無須人工干預的前提下快速進行犯罪活動高發(fā)區(qū)域劃分，并尋找中心點，以此不斷挖掘出潛在情報線索。該方法可以幫助煙草專賣執(zhí)法人員在大量案件數據中快速了解案情，在卷煙消費市場監(jiān)管和涉煙案件分析研判領域有廣泛的應用前景。該方法適用的前提是涉煙案件地址GIS數據必須準確，否則運行結果將不具備指導意義。同時，該方法對“噪聲”樣本點和孤立樣本點較為敏感，少量該類數據可能對最終結果產生影響，加上尚未考慮每個樣本點的本身“大小”因素，即每起案件的案值不一，因此，如何“降噪”和對樣本點“大小”因素進行額外加權評估，將是下一步工作需要繼續(xù)研究的課題。

主要參考文獻

[1]朱明.數據挖掘[M].北京：中國科學技術大學出版社，2008.

[2]張素潔，趙懷慈.最優(yōu)聚類個數和初始聚類中心點選取算法研

究[J].計算機應用研究，2017（6）.

[3]孫吉貴，劉杰，趙連宇.聚類算法研究[J].軟件學報，2008（1）.

[4]賈瑞玉，宋建林.基于聚類中心優(yōu)化的K-means最佳聚類數確定方法[J].微電子學與計算機，2016（5）.

[5]翟東海，魚江，高飛，等.最大距離法選取初始簇中心的K-means文本聚類算法的研究[J].計算機應用研究，2014（3）.

[6]錢政.Android平臺下基于改進的K-means酒店信息聚類算法[J].淮海工學院學報：自然科學版，2014（4）.

[7]王旭仁，李娜，何發(fā)鎂，等.基于改進聚類算法的網絡輿情分析系統(tǒng)研究[J].情報學報，2014（5）.

[8]黎光譜.改進K-Means聚類算法在基于Hadoop平臺的圖像檢索系統(tǒng)中的研究與實現[D].廈門：廈門大學，2014.

[9]徐春光.基于語義分析和改進K-means算法的新聞熱點提取方法研究[D].北京：北京化工大學，2014.

[10]雷蓓麗.對打擊互聯網涉煙違法犯罪的思考[J].新西部，2012（12）.

[11]韋穎藝.淺析打擊互聯網涉煙違法犯罪中電子證據采信與運用[C].//廣西煙草學會2018年論文匯編，2018.

[12]劉澤林.淺析新形勢下“互聯網+物流寄遞”涉煙違法行為監(jiān)管難點及對策[J].經貿實踐，2018（13）.

[13]趙將.基于改進K-means聚類的推薦方法研究[D].武漢：華中科技大學，2016.