城市計算中的顯露模式分析方法研究*

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

（長春工業大學計算機科學與工程學院 長春 130012）

1 引言

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

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

1）對POI數據，GPS數據，公交數據針對于不同應用目的給出幾點處理方法，采用相關處理過程后使其多源異構數據可以轉化成一維數據表。

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

3）對結果進行分析，結合實際場景得到對應結果。

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

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

2.1 ep-樹定義

1）ep-樹含有一個根節點標記為None和一組節點作為該跟的子樹。

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

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

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

2.2 構建ep-樹

構建ep-樹具體步驟如下。

1）掃描數據集，刪除不滿足最小支持度的單項集。

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

3）從空樹出發，掃描數據集，按照heartable中逆序插入ep-樹中。

步驟3）可采用creteTree實現，其中data是數據集，C是所屬類別。

以表1中的數據為例，構建ep-樹。假定最小支持度計數為2。

表1 測試數據

表構造的ep-樹，結果如圖1。

圖1 測試ep-樹

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

3 多源城市數據處理

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

但城市數據這種的多源的結構很難給出統一的處理辦法，只有針對具體數據類型和對數據的具體需求給出相應的處理方法。為此，本文針對興趣點數據，GPS數據，公交數據給出幾種處理方法。

3.1 興趣點（point of interest，POI）數據

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

1）計算區域范圍內的POI個數

POI數據中主要包含經緯度，POI類別，POI名稱等。根據經緯度劃和所要劃分的半徑，可以準確統計該區域的POI數據，如果不滿足聚類條件，可以擴大半徑繼續聚類。

2）根據POI名稱進行聚類

對POI數據中每個POI的名稱進行聚類，但名稱這種文字類型的數據無法直接利用半徑并且離散度很高，所以利用層次聚類樹結構先進行聚類，第一層是以名稱進行中心點的選取，根據設定的類比閾值，滿足則繼續擴大聚類半徑，每擴大一次半徑的值就是一個聚類結果，直到當前層類比閾值小于上一層的類比閾值，或者聚類個數達到行政區域個數停止向上聚類。同時層次樹可以保存每一次聚類結果，可以進行回溯。

具體構建過程如下：

（1）根據POI的種類，將數據項分為C類和非C類。遍歷數據集中的每一個POI點，假設遍歷到P點，以該點為中心點。

（2）選定中心點后，設定半徑起始值，當類比閾值即當前范圍內C類個數與非C類個數比值大于預先計算好的值，將當前結果存進層次樹中，同樣以該點為中心點，擴大半徑，進行下一次迭代，將結果存入樹的上一層。

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

算法偽代碼：

迭代數據構建層次樹通過調用build_city_tree（data，，min_count，）build_city_tree偽代碼如下：

其中，geodesic函數是用經緯度值計算兩點之間直線距離的。通過調用build_city_tree之后會得到一個對數據集C類和非C類的聚類結果。同時可以對數據用聚類結果res_class表示，其值代表該POI點屬于那個范圍，同時通過層次樹，可以得到該聚類中心，半徑及屬于該聚類的POI數據。

3.2 GPS數據

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

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

表2 路段交通運行等級劃分

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

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

3.3 公交數據

1）計算某一區域內的公交繁榮度

根據該區域公交站點個數和經過該區域的公交線路加權線性求和。對比城市公交交通繁榮指數，進行等級歸類。

2）計算某一區域公交站點密度

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

計算出的每個區域的公交站點密度，將所得數據統一劃分為幾個等級，將每個數據用對應的等級進行表示。

4 實驗

實驗在3.20GHz、Intel（R）Core（TM）i5-3470 CPU，8G內存，Windows 10系統的計算機上進行。

4.1 數據集

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

1）POI數據

構建層次聚類樹進行POI聚類，原始POI數據格式如表3所示，通過層次聚類樹轉換成用類別表示的一維數據。

表3 原始POI數據格式

數據處理結果，如圖2所示：每一行代表一個POI數據節點，其中第一列為所劃分區域半徑；第二列為該區域C類和非C類所占比例；第三列為區域表示；第四列為區域中心點經緯度坐標。

圖2 POI結果

2）人口數據

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

其中p(i)是第i個小區的戶數，r(i)是第i個小區的入戶率。計算出的結果在乘以每個房屋包含人數，本文設定num=3，最后sum即為總人口數。

4.2 實驗模型

將以上幾步的結果匯聚在一張表，其表結構為

表4 結果表結構

其中res_class，是POI對應結果類別，res_rate是類別中C類和非C類的比例，people_rate是區域人口占總人口的比例，stop_rate是區域公交站占總公交站比例。

4.3 結果分析

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

表5 不同參數結果

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

表6 實驗結果

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

圖3 驗證實驗結果

5 結語

本文提出了城市計算中的顯露模式分析方法。該分析方法給出了城市中部分數據轉換方法，通過采用相應的數據轉換方法，可以將多表中的數據轉換為一張表中，同時設計了一種適合于挖掘城市數據中的顯露模式的樹形結構。通過實驗對比驗證，該方法可以有效挖掘城市中的顯露模式。

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