肖凡智 張雨竹 尹耀寬 許建潮 劉 鋼

（長春工業(yè)大學(xué)計算機(jī)科學(xué)與工程學(xué)院 長春 130012）

1 引言

隨著大數(shù)據(jù)技術(shù)的成熟，分析城市數(shù)據(jù)，如交通數(shù)據(jù)、氣象數(shù)據(jù)、興趣點(diǎn)數(shù)據(jù)、社交媒數(shù)據(jù)體等成為了解決城市問題所面臨的首要挑戰(zhàn)［1～2］。挖掘城市數(shù)據(jù)中的相關(guān)性和差異性也是城市計算的熱點(diǎn)。使用顯露模式（Emerging Pattern，EP）［3］分析方法挖掘數(shù)據(jù)差異性是一個有效的處理方法。顯露模式是支持度從一個數(shù)據(jù)集到另一個數(shù)據(jù)集項(xiàng)集顯著變化的模式［4～5］。顯露模式能夠很好捕捉兩類數(shù)據(jù)集上屬性之間的差異。但城市計算中涉及的數(shù)據(jù)具有多維、異構(gòu)的星型結(jié)構(gòu)特點(diǎn)，難于直接進(jìn)行顯露模式分析。本文提出一種顯露模式分析算法，對POI（Point of Interest）數(shù) 據(jù)［6～7］，GPS（Global Positioning System）數(shù)據(jù)［8］，交通數(shù)據(jù)等，按應(yīng)用需求設(shè)計合理的轉(zhuǎn)換方法，將多源異構(gòu)數(shù)據(jù)［9］融合在一張表中，通過顯露模式分析方法挖掘數(shù)據(jù)之間的差異性獲取新知識。同時為了滿足POI數(shù)據(jù)可以利用POI名稱直接進(jìn)行聚類，本文利用層次聚類樹算法，將POI轉(zhuǎn)換為區(qū)域地址名稱進(jìn)行聚類。

基于顯露模式的城市數(shù)據(jù)分析方法過程如下：

1）對POI數(shù)據(jù)，GPS數(shù)據(jù)，公交數(shù)據(jù)針對于不同應(yīng)用目的給出幾點(diǎn)處理方法，采用相關(guān)處理過程后使其多源異構(gòu)數(shù)據(jù)可以轉(zhuǎn)化成一維數(shù)據(jù)表。

2）通過步驟1）得到的一維數(shù)據(jù)表可直接通過顯露模式進(jìn)行數(shù)據(jù)挖掘，得到數(shù)據(jù)中的差異性。

3）對結(jié)果進(jìn)行分析，結(jié)合實(shí)際場景得到對應(yīng)結(jié)果。

2 基于城市計算的顯露模式分析方法

顯露模式分析方法是發(fā)現(xiàn)兩類數(shù)據(jù)中項(xiàng)集支持度顯著變化的方法，本文用C類和非C類表示這兩個類別。由于C類上的顯露模式也是C類上的頻繁模式［10～11］，所以提出了ep-樹結(jié)構(gòu)用來挖掘顯露模式，ep-樹結(jié)構(gòu)類似于頻繁模式樹，但它記錄了C類和非C類的各自信息。

2.1 ep-樹定義

1）ep-樹含有一個根節(jié)點(diǎn)標(biāo)記為None和一組節(jié)點(diǎn)作為該跟的子樹。

2）子樹的每個節(jié)點(diǎn)中包含一個列表，每個列表里有6個字段［name，c1，c2，nodeLink，parent，children］。

其中，name節(jié)點(diǎn)代表該項(xiàng)名稱；c1和c2是計算C類和非C類個數(shù)，{j1......jk}（jk=name）依次是根節(jié)點(diǎn)到該節(jié)點(diǎn)上的路徑，則c1等于以{j1......jk}為前綴C類個數(shù)，同理c2是非C類個數(shù)；nodeLink是指向與當(dāng)前節(jié)點(diǎn)值相同的下一個節(jié)點(diǎn)，可以為空；parent指向當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)；children指向當(dāng)前節(jié)點(diǎn)最左子節(jié)點(diǎn)。

3）相同值通過nodeLink指針鏈接在一起，形成節(jié)點(diǎn)鏈。字典heartable，key是當(dāng)前項(xiàng)名稱，value是一個列表，列表里包含3個元素，分別是totalc1，totalc2，node-link，其中heartable［i］中totalc1和totalc2代表i在C類和非C類樣本的計數(shù)和。node-link指向其他樹節(jié)點(diǎn)，該樹節(jié)點(diǎn)item值等于heartable［i］值。

2.2 構(gòu)建ep-樹

構(gòu)建ep-樹具體步驟如下。

1）掃描數(shù)據(jù)集，刪除不滿足最小支持度的單項(xiàng)集。

2）滿足支持度單項(xiàng)集按照從大到小順序存入heartable字典中。

3）從空樹出發(fā)，掃描數(shù)據(jù)集，按照heartable中逆序插入ep-樹中。

步驟3）可采用creteTree實(shí)現(xiàn)，其中data是數(shù)據(jù)集，C是所屬類別。

以表1中的數(shù)據(jù)為例，構(gòu)建ep-樹。假定最小支持度計數(shù)為2。

表1 測試數(shù)據(jù)

表構(gòu)造的ep-樹，結(jié)果如圖1。

圖1 測試ep-樹

在構(gòu)建完的ep-樹，可直接在ep-樹上挖掘顯露模式，同時得到對應(yīng)的增長率和支持度計數(shù)。開始prefix為空，從具有最小支持度計算的項(xiàng)開始挖掘。將該項(xiàng)加入prefix，繼續(xù)增長prefix，既從加入節(jié)點(diǎn)的項(xiàng)向上走。同時創(chuàng)建min_up（prefix，first），直到當(dāng)前項(xiàng)是根節(jié)點(diǎn)或者是當(dāng)前prefix不滿足最小增長率時停止，并繼續(xù)遍歷其nodeLink所指向的同值節(jié)點(diǎn)。算法偽代碼：

3 多源城市數(shù)據(jù)處理

如前兩節(jié)所述，城市數(shù)據(jù)往往具有非常多的類型與來源，即城市數(shù)據(jù)的多元性。這些不同來源的數(shù)據(jù)從結(jié)構(gòu)上，組織形式上，維度等存在巨大的差異，即數(shù)據(jù)異構(gòu)性。同時對于城市數(shù)據(jù)中，如興趣點(diǎn)，天氣等數(shù)據(jù)離散度過高，無法滿足顯露模式分析方法中支持度要求，所以需要對城市數(shù)據(jù)進(jìn)行聚類。

但城市數(shù)據(jù)這種的多源的結(jié)構(gòu)很難給出統(tǒng)一的處理辦法，只有針對具體數(shù)據(jù)類型和對數(shù)據(jù)的具體需求給出相應(yīng)的處理方法。為此，本文針對興趣點(diǎn)數(shù)據(jù)，GPS數(shù)據(jù)，公交數(shù)據(jù)給出幾種處理方法。

3.1 興趣點(diǎn)（point of interest，POI）數(shù)據(jù)

POI數(shù)據(jù)是城市各功能單元的基本信息。因此對POI數(shù)據(jù)處理也是城市計算中較為重要的一點(diǎn)。

1）計算區(qū)域范圍內(nèi)的POI個數(shù)

POI數(shù)據(jù)中主要包含經(jīng)緯度，POI類別，POI名稱等。根據(jù)經(jīng)緯度劃和所要劃分的半徑，可以準(zhǔn)確統(tǒng)計該區(qū)域的POI數(shù)據(jù)，如果不滿足聚類條件，可以擴(kuò)大半徑繼續(xù)聚類。

2）根據(jù)POI名稱進(jìn)行聚類

對POI數(shù)據(jù)中每個POI的名稱進(jìn)行聚類，但名稱這種文字類型的數(shù)據(jù)無法直接利用半徑并且離散度很高，所以利用層次聚類樹結(jié)構(gòu)先進(jìn)行聚類，第一層是以名稱進(jìn)行中心點(diǎn)的選取，根據(jù)設(shè)定的類比閾值，滿足則繼續(xù)擴(kuò)大聚類半徑，每擴(kuò)大一次半徑的值就是一個聚類結(jié)果，直到當(dāng)前層類比閾值小于上一層的類比閾值，或者聚類個數(shù)達(dá)到行政區(qū)域個數(shù)停止向上聚類。同時層次樹可以保存每一次聚類結(jié)果，可以進(jìn)行回溯。

具體構(gòu)建過程如下：

（1）根據(jù)POI的種類，將數(shù)據(jù)項(xiàng)分為C類和非C類。遍歷數(shù)據(jù)集中的每一個POI點(diǎn)，假設(shè)遍歷到P點(diǎn)，以該點(diǎn)為中心點(diǎn)。

（2）選定中心點(diǎn)后，設(shè)定半徑起始值，當(dāng)類比閾值即當(dāng)前范圍內(nèi)C類個數(shù)與非C類個數(shù)比值大于預(yù)先計算好的值，將當(dāng)前結(jié)果存進(jìn)層次樹中，同樣以該點(diǎn)為中心點(diǎn)，擴(kuò)大半徑，進(jìn)行下一次迭代，將結(jié)果存入樹的上一層。

（3）直到下一次迭代的閾值小于上一次的結(jié)果。結(jié)束該點(diǎn)迭代，以下一個未劃分聚類的點(diǎn)進(jìn)行迭代，直到所有點(diǎn)遍歷完成。

算法偽代碼：

迭代數(shù)據(jù)構(gòu)建層次樹通過調(diào)用build_city_tree（data，，min_count，）build_city_tree偽代碼如下：

其中，geodesic函數(shù)是用經(jīng)緯度值計算兩點(diǎn)之間直線距離的。通過調(diào)用build_city_tree之后會得到一個對數(shù)據(jù)集C類和非C類的聚類結(jié)果。同時可以對數(shù)據(jù)用聚類結(jié)果res_class表示，其值代表該P(yáng)OI點(diǎn)屬于那個范圍，同時通過層次樹，可以得到該聚類中心，半徑及屬于該聚類的POI數(shù)據(jù)。

3.2 GPS數(shù)據(jù)

1）計算城市中某條道路的交通擁堵狀況

對該路段所有通行車輛計算行車速度，行駛某一段距離d和行駛該距離所花費(fèi)的時間t，計算得出該路段典型代表性的速度平均值。距離d可以通過數(shù)據(jù)中經(jīng)緯度進(jìn)行計算。如果d長度過大，可以采用分段計算每段的平均車速，最后加權(quán)求得該路段平均車速。對于交通擁堵范圍的界定，參照北京城市道路交通運(yùn)行評價指標(biāo)體系［12］將道路交通擁堵狀況劃分為5個級別，如表2。將計算得到的平均速度，轉(zhuǎn)換成有意義的5個類別。將離散值聚類。

表2 路段交通運(yùn)行等級劃分

2）計算某一車輛的行駛車速

由于某一車輛可能行駛距離較長，行駛路段較復(fù)雜，無法直接進(jìn)行經(jīng)緯度的距離計算。可以采用對路段進(jìn)行劃分，通過求得每段平均車速和當(dāng)前路段長度所占總長度比例和道路運(yùn)行等級進(jìn)行線性加權(quán)求平均車速。對照表2，轉(zhuǎn)換成5個類別。

3.3 公交數(shù)據(jù)

1）計算某一區(qū)域內(nèi)的公交繁榮度

根據(jù)該區(qū)域公交站點(diǎn)個數(shù)和經(jīng)過該區(qū)域的公交線路加權(quán)線性求和。對比城市公交交通繁榮指數(shù)，進(jìn)行等級歸類。

2）計算某一區(qū)域公交站點(diǎn)密度

根據(jù)核密度聚類方法，具體如式（1），其中f（x）為空間位置為x的密度計算函數(shù)，r為搜索半徑，n為距離額小于r的所有站點(diǎn)，k(·)表示權(quán)重函數(shù)。

計算出的每個區(qū)域的公交站點(diǎn)密度，將所得數(shù)據(jù)統(tǒng)一劃分為幾個等級，將每個數(shù)據(jù)用對應(yīng)的等級進(jìn)行表示。

4 實(shí)驗(yàn)

實(shí)驗(yàn)在3.20GHz、Intel（R）Core（TM）i5-3470 CPU，8G內(nèi)存，Windows 10系統(tǒng)的計算機(jī)上進(jìn)行。

4.1 數(shù)據(jù)集

本文采用長春市本地真實(shí)數(shù)據(jù)，包括長春市POI數(shù)據(jù)，長春市房屋數(shù)據(jù)及長春市公交數(shù)據(jù)等。其中POI數(shù)據(jù)集包括32768條數(shù)據(jù)。同時根據(jù)數(shù)據(jù)特性，將顯露模式中兩類數(shù)據(jù)選為汽車和非汽車類。其中汽車類有10749個。對每種數(shù)據(jù)的處理方法如下。

1）POI數(shù)據(jù)

構(gòu)建層次聚類樹進(jìn)行POI聚類，原始POI數(shù)據(jù)格式如表3所示，通過層次聚類樹轉(zhuǎn)換成用類別表示的一維數(shù)據(jù)。

表3 原始POI數(shù)據(jù)格式

數(shù)據(jù)處理結(jié)果，如圖2所示：每一行代表一個POI數(shù)據(jù)節(jié)點(diǎn)，其中第一列為所劃分區(qū)域半徑；第二列為該區(qū)域C類和非C類所占比例；第三列為區(qū)域表示；第四列為區(qū)域中心點(diǎn)經(jīng)緯度坐標(biāo)。

圖2 POI結(jié)果

2）人口數(shù)據(jù)

根據(jù)POI數(shù)據(jù)劃分出的區(qū)域，計算出每個區(qū)域包含小區(qū)個數(shù)［13］，同時根據(jù)每個小區(qū)的房屋總數(shù)及入戶率計算出該區(qū)域人口數(shù)，具體公式為

其中p(i)是第i個小區(qū)的戶數(shù)，r(i)是第i個小區(qū)的入戶率。計算出的結(jié)果在乘以每個房屋包含人數(shù)，本文設(shè)定num=3，最后sum即為總?cè)丝跀?shù)。

4.2 實(shí)驗(yàn)?zāi)Ｐ?/h3>

將以上幾步的結(jié)果匯聚在一張表，其表結(jié)構(gòu)為

表4 結(jié)果表結(jié)構(gòu)

其中res_class，是POI對應(yīng)結(jié)果類別，res_rate是類別中C類和非C類的比例，people_rate是區(qū)域人口占總?cè)丝诘谋壤?，stop_rate是區(qū)域公交站占總公交站比例。

4.3 結(jié)果分析

實(shí)驗(yàn)進(jìn)行了不同支持度和增長率下的顯露模式挖掘，支持度范圍從100到800，每次增加100，每一次增加支持度時增長率范圍從0.7到0.9增長，每一次的顯露模式個數(shù)如表5所示。

表5 不同參數(shù)結(jié)果

從表中可以看出支持度為100，增長率為0.7時，顯露模式數(shù)量最多，但支持度過低無法有效統(tǒng)計數(shù)據(jù)特性，所以最終選定支持度為300，增長率為0.8，實(shí)驗(yàn)結(jié)果包括3條顯露模式，其中包含2個強(qiáng)跳躍顯露模式［14～16］。實(shí)驗(yàn)結(jié)果如表6所示。

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

取其中的res_class=A45，汽車相關(guān)的第45個分類，經(jīng)緯度坐標(biāo)為（125.27789，43.88147）。百度地圖展示為圖3，其中與汽車相關(guān)的POI有七家，占圖中總POI個數(shù)60%以上，所以定義為汽車相關(guān)分類正確。

圖3 驗(yàn)證實(shí)驗(yàn)結(jié)果

5 結(jié)語

本文提出了城市計算中的顯露模式分析方法。該分析方法給出了城市中部分?jǐn)?shù)據(jù)轉(zhuǎn)換方法，通過采用相應(yīng)的數(shù)據(jù)轉(zhuǎn)換方法，可以將多表中的數(shù)據(jù)轉(zhuǎn)換為一張表中，同時設(shè)計了一種適合于挖掘城市數(shù)據(jù)中的顯露模式的樹形結(jié)構(gòu)。通過實(shí)驗(yàn)對比驗(yàn)證，該方法可以有效挖掘城市中的顯露模式。

本文介紹的分析方法只關(guān)注了城市中部分?jǐn)?shù)據(jù)，并沒有給出較為全面處理城市數(shù)據(jù)的分析方法。將來的工作方向是完善城市數(shù)據(jù)的分析方法，如如何處理文本、處理圖像等。