基于K-m eans算法的案件預測應用*

王健豪 蘇 勇

（江蘇科技大學計算機學院 鎮(zhèn)江 212003）

1 引言

現(xiàn)在大數(shù)據(jù)與云計算是計算機發(fā)展的主流，那么在新時期背景下，公安信息化成為了公安工作的重要內容［1］。面對大量案件物證信息的堆積，那么如何充分挖掘這些數(shù)據(jù)中隱含的規(guī)律，提高公安部門辦案效率，有效降低犯罪率，為公安部門提供決策依據(jù)，而不是僅僅進行一些基礎的查詢和統(tǒng)計。聚類分析是數(shù)據(jù)挖掘的一項重要技術［2］，目的在于分析事物的內在聯(lián)系和本質。所以是一種不錯的選擇。聚類算法分為基于劃分的、密度的、分層的、網(wǎng)絡的、模型的等類型［3］。K-means算法是一種基于劃分的的聚類算法，其算法易于實現(xiàn)、效率高、可以高效處理大數(shù)據(jù)集合［4］。經(jīng)典K-means算法由于其選擇初始簇中心具有隨機性，會導致以下一些缺點：1）隨著數(shù)據(jù)集合的改變，聚類可能會失去穩(wěn)定性［5］；2）聚類結果很多情況下是局部最優(yōu)，而不是我們要求得全局最優(yōu)［6］；3）聚類分析的總耗時會隨著迭代次數(shù)的增加而增加［7］。很多K-means的優(yōu)化算法為了削弱這些缺點而相繼產生，如文獻［8］提出的K-means算法，是基于最優(yōu)劃分的。其核心思想：在數(shù)據(jù)集中取出樣本，然后根據(jù)樣本的特性把它分為不同的類型，最后根據(jù)樣本類型的不同來確定初始的聚類中心。該改進算法優(yōu)化了算法的效率，提高的聚類的準確率，但其缺陷也很明顯，比如如果數(shù)據(jù)集需要超高維度，那么算法的復雜度會呈幾何度增加。文獻［9～11］提出對不確定性數(shù)據(jù)集的挖掘方法。文獻［12］提出的高效聚類算法，使得K-means具有局部最優(yōu)性。該算法主要是利用了數(shù)學上的圖的優(yōu)點，通過構建加權連通圖，然后利用這種由子簇交集產生的連通圖的特性去合并，進而優(yōu)化聚類效果，但其著重點在于局部，而不是全局，所以其聚類精度還是有所欠缺。文獻［13］提出的改進方法在于利用樣本的局部密度去初始聚類中心從而提高聚類效果；文獻［14～20］也是在K-means算法的初始化上做了優(yōu)化；那么考慮到在某市嘗試案件物證信息分類的作用是為相關部門提供決策，準確性是第一位的，通過對多方面改進算法的學習和思考，本文采用在聚合度較高的樣本中，選擇聚類中心，然后求方差可以使聚類中心緊湊，實現(xiàn)分類的自動化、定時化，保證結果的客觀性。

2 K-m eans算法

K-means算法［21］是一種基于劃分方法的聚類算法。不同樣本的相似性一般通過樣本間的歐氏距離作為評價依據(jù)。其核心思想：1）在給定的數(shù)據(jù)集中隨機的去選取一定數(shù)量的的初始聚類中心（數(shù)量假設為k），然后計算數(shù)據(jù)集中樣本到初始聚類中心的歐式距離d，根據(jù)歐式距離d與初始聚類中心的遠近來確定當前樣本屬于哪個聚類中心的范圍，繼而初始的分為k個類；2）在每個類中重新計算（通常為各個類中樣本的平均值）得到新的聚類中心，循環(huán)步驟1），知道聚類中心趨于穩(wěn)定。

一般情況下，我們可以通過誤差平方和來作為標準，其定義為

其中：k為簇的數(shù)量；Xi為簇Ci的聚類中心，即平均值。K-means算法步驟如下：

輸入：簇的數(shù)量k、樣本集中樣本個數(shù)N，遞歸終止條件ε，最大遞歸次數(shù)tatal。

輸出：算法終止后的聚類中心的個數(shù)k、遞歸次數(shù)s。

1）隨機初始化k個簇中心。

2）對數(shù)據(jù)集中的每個對象，計算其與各個聚類中心的距離，并選擇距離最?。ㄏ嗨贫茸畲螅┑木垲愔行?，將該對象歸入該聚類中心所處的簇。

3）通過平局值重新計算每個簇的聚類中心，并使用式（1）得出測度函數(shù)值E。

4）如果達到最大遞歸次數(shù)或滿足：

則算法結束；否則返回2），繼續(xù)循環(huán)執(zhí)行。

其中：E1和 E2分別代表前后兩次遞歸的測度函數(shù)值，ε值極小，上式表示簇內誤差平方總和已經(jīng)收斂，即聚類中心基本上不發(fā)生變化。

3 本文核心算法原理

數(shù)學領域中，通常使用方差和標準差來測算樣本離散趨勢。樣本方差或樣本標準差越大，數(shù)據(jù)的浮動就越大。方差用來度量隨機變量與其數(shù)學期望（即均值）之間的偏離程度，是測算數(shù)值型數(shù)據(jù)離散程度的最重要方法。因此通過方差可以降低孤立點對聚類中心的一些影響。

本文算法與經(jīng)典K-means算法隨機確定聚類中心不同，在于確定的聚類中心位于比較密集區(qū)域中。

算法步驟：設D為數(shù)據(jù)集

1）確定K個聚類中心

（1）求出樣本集中不同樣本間的平均距離ave-Distance：

其中dis(xi，xj)為樣本 xi與樣本 xi之間的歐式距離，n為樣本總個數(shù)。

（2）在數(shù)據(jù)集中找出一個樣本 x1，使得dis（x1，xi）＜ aveDistance，其中1＜i＜n；并且令：

（3）重復（2）直到找到K個聚類中心。

2）按照經(jīng)典K-means算法步驟即可。

4 實驗結果

在某段時間階段內的某個地域上的人工模擬數(shù)據(jù)集上的聚類準確率如圖1～2（圖1和圖2分為為數(shù)據(jù)集為1000，2000時的實驗數(shù)據(jù)）。

經(jīng)過對比，可以看到本文改進的K-means算法相對于經(jīng)典的K-means算法具有較為準確的分類效果。

5 案件預測

根據(jù)上述方法，并結合以往時間段、地域等因素，我們可以得出不同時間不同地域不同案件的發(fā)生數(shù)量、發(fā)生比例，相關部門便可以根據(jù)曲線圖的趨勢做出對應的決策，維護社會治安。

圖1 數(shù)據(jù)集為1000時的實驗數(shù)據(jù)

圖2 數(shù)據(jù)集為2000時的實驗數(shù)據(jù)

6 結語

本文著重通過算法上初始聚類中心的自動化選擇上去改進K-means算法，提高算法聚類的準確率，盡量降低傳統(tǒng)K-means算法中孤立點對聚類的影響。由于主要目標是為了相關部門人員分配的參考，故這里聚類中心只需要幾個。下一步的研究方向是針對本算法中的不足，研究如何自動確認適合的聚類中心，并優(yōu)化算法分類的準確率，以便為相關部門提供以為有力的參考依據(jù)。