張小川++嚴(yán)杰++朱常鵬

摘要摘要：針對Kmeans聚類算法，結(jié)合市政績效評估的需要進(jìn)行改進(jìn)。以穩(wěn)定Kmeans聚類算法中心和選取最優(yōu)聚類個數(shù)為目的，提出基于Kruskal算法和輪廓系數(shù)法的Kmeans聚類算法。針對區(qū)縣不同結(jié)構(gòu)實際市政績效評估數(shù)據(jù)，按照商業(yè)智能和IQR規(guī)則進(jìn)行預(yù)處理，然后利用改進(jìn)的Kmeans聚類算法對預(yù)處理后的數(shù)據(jù)進(jìn)行聚類分析。實驗結(jié)果表明，該算法能夠有效地確立各市政事件、部件的發(fā)生頻數(shù)等級，幫助市政管理者發(fā)現(xiàn)各市政事件、部件之間關(guān)聯(lián)關(guān)系，提高其科學(xué)決策能力。

關(guān)鍵詞關(guān)鍵詞：Kmeans聚類算法；Kruskal算法；輪廓系數(shù)法；IQR；商業(yè)智能

DOIDOI：10.11907/rjdk.1511214

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A文章編號文章編號：16727800（2015）011004803

基金項目基金項目：

作者簡介作者簡介：張小川（1965-）， 男，重慶人，重慶理工大學(xué)計算機(jī)科學(xué)與工程學(xué)院教授，研究方向為人工智能、人工生命、計算機(jī)軟件；嚴(yán)杰（1991-），男，重慶人，重慶理工大學(xué)計算機(jī)科學(xué)與工程學(xué)院碩士研究生，研究方向為數(shù)據(jù)庫管理、數(shù)據(jù)挖掘、數(shù)據(jù)分析。

0引言

智慧城市是信息化社會中一種以網(wǎng)絡(luò)為依托，智能融合，全民參與城市塑造的數(shù)字城市的高級形態(tài)。智慧城市要落地，數(shù)字城管是基礎(chǔ)[1]。而數(shù)字城管是一種能夠?qū)Τ鞘袑崿F(xiàn)敏捷、高效、全方位、全時段覆蓋，并且與傳統(tǒng)城市管理不同的全新的城市管理模式[2]。實際上，在十二五期間，數(shù)字城管的數(shù)據(jù)體系、軟件體系、應(yīng)用體系和保障體系已基本建成，為智慧城市建設(shè)奠定了堅實的基礎(chǔ)。由于信息互聯(lián)互通與數(shù)據(jù)共享程度低、建設(shè)實效和作用不明顯、標(biāo)準(zhǔn)體系與政策法規(guī)滯后等問題，造成了數(shù)字城管的人力、物力、財力和信息資源浪費(fèi)。因此，為了提高數(shù)字城管管理效率，建立一個科學(xué)、合理的績效評估體系尤為必要。市政績效評估體系是指在合理制度安排和新的公共行政理念的指導(dǎo)下，運(yùn)用科學(xué)的政府管理方法，提高市政行政管理效率，降低管理成本為目的的綜合行政評價體制[3-4]。數(shù)字城管每天都在產(chǎn)生大量雜亂無章、價值密度相對較低的數(shù)據(jù)，如何在指定時間內(nèi)對這些數(shù)據(jù)進(jìn)行提取、管理、處理、整理、分析，并建立一個科學(xué)的市政績效評估體系是一個亟待解決的問題。基于此，文章首先利用商業(yè)智能和IQR對已有的市政績效評估數(shù)據(jù)進(jìn)行數(shù)據(jù)預(yù)處理；其次，對改進(jìn)的Kmeans聚類算法與傳統(tǒng)Kmeans聚類算法進(jìn)行比較，證明改進(jìn)的Kmeans聚類算法的可靠性；最后，對改進(jìn)的Kmeans聚類算法的結(jié)果進(jìn)行分析，證明其有效性。

1研究綜述

自Kmeans聚類算法由MacQueen于1967年提出以來，Kmeans聚類算法以其簡單和易于實現(xiàn)的特點使其成為經(jīng)典的劃分型聚類算法，被廣泛使用[5]。由于傳統(tǒng)的Kmeans聚類算法存在對初始聚類中心選擇敏感，并且需要人工指定聚類個數(shù)的問題，因此，很多學(xué)者提出了改進(jìn)的Kmeans聚類算法。

文獻(xiàn)[6]基于最小生成樹的思想，文獻(xiàn)[7]基于密度和歐氏距離積的思想，文獻(xiàn)[8]基于粒子群和密度的最大最小距離法的思想，文獻(xiàn)[9]基于層次聚類的思想，文獻(xiàn)[10]基于距離矩陣的思想，文獻(xiàn)[11]基于最小方差的思想，文獻(xiàn)[13]基于距離和權(quán)值的思想，提出了穩(wěn)定初始聚類中心的Kmeans聚類算法。

針對最優(yōu)聚類個數(shù)選擇問題，大多數(shù)聚類算法都是通過聚類有效性評估函數(shù)的計算來確定。文獻(xiàn)[14]綜述了各種聚類有效性評估函數(shù)。文獻(xiàn)[15]基于DS證據(jù)理論，把各種聚類有效性評估函數(shù)結(jié)合起來，提高了聚類評估的有效性和可靠性。

本文提出基于Kruskal算法和輪廓系數(shù)法的Kmeans聚類算法，并將其應(yīng)用于經(jīng)過數(shù)據(jù)預(yù)處理的市政績效評估。實驗結(jié)果表明，文章提出的算法能夠?qū)κ姓录?、部件有效地進(jìn)行聚類。使市政管理者更容易發(fā)現(xiàn)市政事件、部件的關(guān)聯(lián)關(guān)系，確立市政事件、部件的頻數(shù)等級，從而有利于科學(xué)決策。

3實驗

3.1數(shù)據(jù)預(yù)處理

商業(yè)智能就是利用數(shù)據(jù)管理功能，將從多個數(shù)據(jù)源中抽取的數(shù)據(jù)進(jìn)行整理、轉(zhuǎn)換和清理，并利用OLTP、OLAP對數(shù)據(jù)進(jìn)行分析，最終形成報表。本文利用SQL Server 2008 R2 BI提取原始的某區(qū)的市政績效評估數(shù)據(jù)，并對數(shù)據(jù)進(jìn)行整理，最終形成相關(guān)維度表、事實表。利用SQL進(jìn)行查詢，得到的結(jié)果如表1所示。表1中，第一列表示市政事件、部件的名稱和編號，第一行表示統(tǒng)計周期，表中數(shù)據(jù)表示的是某一市政事件、部件在某一統(tǒng)計周期內(nèi)總共發(fā)生的次數(shù)。

由于表中數(shù)據(jù)存在孤立點，因此為避免改進(jìn)的Kmeans聚類算法產(chǎn)生局部最優(yōu)，需要利用IQR規(guī)則進(jìn)行數(shù)據(jù)清洗。結(jié)果排除了無照經(jīng)營游商（54）、亂堆物堆料（57）、暴露垃圾（79）、非法小廣告（105）。分析排除的這4個市政事件、部件，可以得出這4個市政事件、部件均屬于市政事件。其中， 54、57屬于街面秩序事件，79屬于市容環(huán)境事件，105屬于宣傳廣告事件。在日常生活中，這些事件屬于高發(fā)類事件，市政管理員需要對這些事件加強(qiáng)管理，將它們控制在一個有效范圍內(nèi)。

3.2算法比較

對改進(jìn)Kmeans聚類算法進(jìn)行拆分，并利用經(jīng)過數(shù)據(jù)預(yù)處理后的數(shù)據(jù)進(jìn)行運(yùn)算，最終，繪制聚類個數(shù)——輪廓系數(shù)圖，如圖1所示。

從圖1可以看出，聚類個數(shù)為3時，算法效果最優(yōu)。因此利用這個聚類個數(shù)，對本文提出的算法與傳統(tǒng)的Kmeans聚類算法在相同條件下運(yùn)行79次，記錄在運(yùn)行次數(shù)為13、23、37、47、57、67、79時各自聚類中心的變化次數(shù)，如表2所示。

在表2中，第一行表示所用聚類算法，第一列表示實驗的次數(shù)，表中數(shù)據(jù)表示聚類中心的變化次數(shù)。分析表2可得，針對同一數(shù)據(jù)集，改進(jìn)的Kmeans聚類算法的運(yùn)行結(jié)果比傳統(tǒng)的Kmeans聚類算法更具有可靠性。

3.3結(jié)果分析

在最優(yōu)聚類個數(shù)下改進(jìn)的Kmeans聚類算法得到的最優(yōu)聚類結(jié)果，如表3所示。

表3最優(yōu)聚類結(jié)果

簇類[]聚類結(jié)果

簇1[]8、91、101、18、31、40、51、58、80、88

簇2[]64、84、102

簇3[]76、60、74、106、83、98

可以看出8、91、101、18、31、40、51、58、80、88為一類（簇1），64、84、102為一類（簇2），76、60、74、106、83、98為一類（簇3）。結(jié)合表1可以看出，簇1在所選的周期上發(fā)生次數(shù)比簇2和簇3少，簇2發(fā)生次數(shù)比簇3多，針對以上問題，市政管理者對簇3包含的市政事件、部件應(yīng)該重點關(guān)注。分析簇1，結(jié)合表1可得，如果在行道樹旁邊圈養(yǎng)家禽家畜，或者在行道樹邊晾曬拖把，就影響了行道樹美觀，那么可以將擅自飼養(yǎng)家禽家畜和非裝飾性樹掛與行道樹關(guān)聯(lián)起來形成一類。分析簇2，結(jié)合表1可得，如果在街邊拉一根繩子晾曬衣服，或者在人行橫道上放一塊廣告牌招攬生意，這樣影響了行人通行，并且影響了市容環(huán)境，由于市容環(huán)境問題主要是指城市的清潔衛(wèi)生問題，因此可以將沿街晾掛和占道廣告牌與其他市容環(huán)境問題關(guān)聯(lián)起來形成一類。分析簇3，結(jié)合表1可得，用餐時段，道路邊的店面一般會在店外多加幾張桌子、凳子，由于位置太偏，因此老板會在顯眼的墻上懸掛廣告牌，這樣會吸引更多就餐的客人。由于有些客人隨地亂丟垃圾，導(dǎo)致道路不潔。所以違章張貼懸掛廣告牌匾和道路不潔可以與店外經(jīng)營關(guān)聯(lián)起來形成一類。由以上分析可得，改進(jìn)的Kmeans聚類算法的運(yùn)行結(jié)果具有有效性。

4結(jié)語

針對市政事件、部件的關(guān)聯(lián)性分析問題，本文提出了基于Kruskal算法和輪廓系數(shù)法的Kmeans聚類算法，并將其運(yùn)用于經(jīng)過數(shù)據(jù)預(yù)處理的市政績效評估數(shù)據(jù)中。與傳統(tǒng)Kmeans聚類算法相比，改進(jìn)的Kmeans聚類算法的運(yùn)行結(jié)果具有可靠性。通過聚類分析，得到改進(jìn)的Kmeans聚類算法的運(yùn)行結(jié)果具有有效性。

參考文獻(xiàn)：

[1]郭嘉凱.智慧城市落地：數(shù)字城管先行[J].軟件和信息服務(wù)，2013，（7）：5051.

[2]曾廣暉.淺談數(shù)字城管系統(tǒng)[J].江西通信科技，2015，（1）：3437.

[3]王謙.政府績效評估方法及應(yīng)用研究[D].成都：西南交通大學(xué)，2006.

[4]盛明科.服務(wù)型政府績效評估體系構(gòu)建與制度安排[D].湘潭：湘潭大學(xué)，2008.

[5]金建國.聚類算法綜述[J].計算機(jī)科學(xué)，2014，41（11A）：288293.

[6]馮波.Kmeans算法初始聚類中心選擇的優(yōu)化[J].計算機(jī)工程與應(yīng)用，2013，49（14）：182186.

[7]樊曉光.基于密度和距離積的聚類中心選取方法[J].測控技術(shù)，2013，32（10）：152154.

[8]楊志，羅可.一種改進(jìn)的基于粒子群的聚類算法[J].計算機(jī)應(yīng)用研究，2014，31（9）：25972599.

[9]李文超，周勇，夏士雄.一種新的基于層次和Kmeans方法的聚類算法[R].張家界，2007.

[10]張靖，段富.優(yōu)化初始聚類中心的改進(jìn)Kmeans算法[J].計算機(jī)工程與設(shè)計，2013，34（5）：16911694.

[11]謝娟英，王艷娥.最小方差優(yōu)化初始聚類中心的Kmeans算法[J].計算機(jī)工程，2014，40（8）：205211.

[12]周世兵，徐振源，唐旭清.新的K均值算法最佳聚類數(shù)確定方法[J].計算機(jī)工程與應(yīng)用，2010，46（10）：2731.

[13]王越，王泉，呂奇峰，曾晶.基于初始聚類中心優(yōu)化和維間加權(quán)的改進(jìn)Kmeans算法[J].重慶理工大學(xué)學(xué)報：自然科學(xué)版，2013，27（4）：7780.

[14]周開樂，楊善林，丁帥，羅賀.聚類有效性研究綜述[J].系統(tǒng)工程理論與實踐，2014，34（9）：24172431.

[15]劉燕馳，高學(xué)東，國宏偉，武森.聚類有效性的組合評價方法[J].計算機(jī)工程與應(yīng)用，2011，47（19）：1517.

責(zé)任編輯（責(zé)任編輯：陳福時）