聚類算法在市政績效評估中的應(yīng)用

張小川++嚴杰++朱常鵬

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

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

DOIDOI：10.11907/rjdk.1511214

中圖分類號：TP312

文獻標識碼：A文章編號文章編號：16727800（2015）011004803

基金項目基金項目：

作者簡介作者簡介：張小川（1965-）， 男，重慶人，重慶理工大學計算機科學與工程學院教授，研究方向為人工智能、人工生命、計算機軟件；嚴杰（1991-），男，重慶人，重慶理工大學計算機科學與工程學院碩士研究生，研究方向為數(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è)實效和作用不明顯、標準體系與政策法規(guī)滯后等問題，造成了數(shù)字城管的人力、物力、財力和信息資源浪費。因此，為了提高數(shù)字城管管理效率，建立一個科學、合理的績效評估體系尤為必要。市政績效評估體系是指在合理制度安排和新的公共行政理念的指導下，運用科學的政府管理方法，提高市政行政管理效率，降低管理成本為目的的綜合行政評價體制[3-4]。數(shù)字城管每天都在產(chǎn)生大量雜亂無章、價值密度相對較低的數(shù)據(jù)，如何在指定時間內(nèi)對這些數(shù)據(jù)進行提取、管理、處理、整理、分析，并建立一個科學的市政績效評估體系是一個亟待解決的問題?；诖?，文章首先利用商業(yè)智能和IQR對已有的市政績效評估數(shù)據(jù)進行數(shù)據(jù)預處理；其次，對改進的Kmeans聚類算法與傳統(tǒng)Kmeans聚類算法進行比較，證明改進的Kmeans聚類算法的可靠性；最后，對改進的Kmeans聚類算法的結(jié)果進行分析，證明其有效性。

1研究綜述

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

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

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

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

3實驗

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

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

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

3.2算法比較

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

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

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

3.3結(jié)果分析

在最優(yōu)聚類個數(shù)下改進的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可得，用餐時段，道路邊的店面一般會在店外多加幾張桌子、凳子，由于位置太偏，因此老板會在顯眼的墻上懸掛廣告牌，這樣會吸引更多就餐的客人。由于有些客人隨地亂丟垃圾，導致道路不潔。所以違章張貼懸掛廣告牌匾和道路不潔可以與店外經(jīng)營關(guān)聯(lián)起來形成一類。由以上分析可得，改進的Kmeans聚類算法的運行結(jié)果具有有效性。

4結(jié)語

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

參考文獻：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

責任編輯（責任編輯：陳福時）