基于K-m eans算法的案件預(yù)測(cè)應(yīng)用*

王健豪 蘇 勇

（江蘇科技大學(xué)計(jì)算機(jī)學(xué)院 鎮(zhèn)江 212003）

1 引言

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

2 K-m eans算法

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

一般情況下，我們可以通過(guò)誤差平方和來(lái)作為標(biāo)準(zhǔn)，其定義為

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

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

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

1）隨機(jī)初始化k個(gè)簇中心。

2）對(duì)數(shù)據(jù)集中的每個(gè)對(duì)象，計(jì)算其與各個(gè)聚類中心的距離，并選擇距離最小（相似度最大）的聚類中心，將該對(duì)象歸入該聚類中心所處的簇。

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

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

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

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

3 本文核心算法原理

數(shù)學(xué)領(lǐng)域中，通常使用方差和標(biāo)準(zhǔn)差來(lái)測(cè)算樣本離散趨勢(shì)。樣本方差或樣本標(biāo)準(zhǔn)差越大，數(shù)據(jù)的浮動(dòng)就越大。方差用來(lái)度量隨機(jī)變量與其數(shù)學(xué)期望（即均值）之間的偏離程度，是測(cè)算數(shù)值型數(shù)據(jù)離散程度的最重要方法。因此通過(guò)方差可以降低孤立點(diǎn)對(duì)聚類中心的一些影響。

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

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

1）確定K個(gè)聚類中心

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

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

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

（3）重復(fù)（2）直到找到K個(gè)聚類中心。

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

4 實(shí)驗(yàn)結(jié)果

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

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

5 案件預(yù)測(cè)

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

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

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

6 結(jié)語(yǔ)

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