基于Hadoop 的車位空閑模式挖掘方法

張藝瓊，王海青，王鎖柱，高琳琦

（1.首都師范大學(xué)信息工程學(xué)院，北京100048；2.首都師范大學(xué)管理學(xué)院，北京100048；3.天津師范大學(xué)管理學(xué)院，天津300387）

近些年，停車市場日益突出的供需矛盾為城市交通發(fā)展帶來了極大的困擾，靜態(tài)交通服務(wù)設(shè)施供給不足導(dǎo)致的停車難、交通擁堵和環(huán)境污染等一系列問題逐漸顯現(xiàn).隨著相關(guān)技術(shù)的成熟，智慧社區(qū)共享停車服務(wù)的興起，為緩解社區(qū)及其周邊的停車壓力，解決城市交通停車問題提供了更大的發(fā)展空間.實(shí)現(xiàn)智慧社區(qū)共享停車服務(wù)的首要問題是有效刻畫社區(qū)業(yè)主的車位空閑模式，其核心是對(duì)車位空閑時(shí)刻頻繁項(xiàng)集的挖掘.

Apriori 算法[1]作為一種經(jīng)典的數(shù)據(jù)挖掘算法，在對(duì)頻繁項(xiàng)集挖掘的問題中展現(xiàn)出很強(qiáng)的優(yōu)勢，它不僅可以在雜亂無章的數(shù)據(jù)中挖掘出數(shù)據(jù)之間實(shí)際存在的關(guān)系，而且還可以給予每種關(guān)系準(zhǔn)確的支持度.但是，隨著數(shù)據(jù)量的增加，Apriori 算法需要多次反復(fù)掃描事務(wù)集并記錄大量的候選集，容易導(dǎo)致I/O 負(fù)載過重，不能及時(shí)完成計(jì)算任務(wù).為了解決這個(gè)問題，相關(guān)學(xué)者利用其擴(kuò)展性較好的特點(diǎn)，嘗試?yán)貌⑿泻头植际狡脚_(tái)來進(jìn)行頻繁模式的挖掘[2].

本文借助Hadoop[3-4]的MapReduce 并行計(jì)算框架[5-7]，基于Apriori 算法設(shè)計(jì)一種車位空閑模式的挖掘方法，并設(shè)計(jì)實(shí)驗(yàn)完成了對(duì)社區(qū)業(yè)主車位空閑模式的挖掘.實(shí)驗(yàn)表明，該方法不僅可以有效解決內(nèi)存溢出的問題，而且，隨著數(shù)據(jù)集的不斷擴(kuò)大，該方法的執(zhí)行效率明顯優(yōu)于傳統(tǒng)方法.

1 問題描述

1.1 車位空閑模式描述

通常，社區(qū)停車需求時(shí)間一般與附近的商業(yè)、辦公、醫(yī)療等其他類型場所具有明顯的互補(bǔ)性.社區(qū)大多數(shù)業(yè)主“朝出夕歸”的日常出行行為使得社區(qū)停車位在部分時(shí)段出現(xiàn)明顯閑置，因此具備良好的對(duì)外共享?xiàng)l件.本文對(duì)停車場管理中心的業(yè)主車輛出行行為數(shù)據(jù)進(jìn)行分析，從海量業(yè)主出行數(shù)據(jù)中發(fā)現(xiàn)閑置車位資源，為實(shí)現(xiàn)車位資源對(duì)外共享提供基礎(chǔ)數(shù)據(jù)支持.

利用Apriori 算法的思想根據(jù)業(yè)主的歷史出行數(shù)據(jù)挖掘每個(gè)業(yè)主相應(yīng)的閑置車位資源，需要將一天24 h 等間隔 ΔT（可以為10 min，15 min 等）離散化為T 個(gè)時(shí)段，T=（24×60）/ΔT.設(shè)ti表示第（ii=1，2，…，T）個(gè)時(shí)段Ii=[0：00+（i-1）ΔT，0：00+iΔT]的車位空閑狀況，車位閑置時(shí)，ti=1，車位占用時(shí)，ti=0.由此，使用離散化后的數(shù)據(jù)構(gòu)造一個(gè)社區(qū)業(yè)主出行事務(wù)集，ti是事務(wù)集中的最小計(jì)算單元，在挖掘車位空閑模式時(shí)，只需利用頻繁項(xiàng)集挖掘方法對(duì)事務(wù)集中的ti進(jìn)行計(jì)算處理.

頻繁項(xiàng)集主要通過項(xiàng)的連接和剪枝得到[8-10].連接步驟利用項(xiàng)與項(xiàng)之間遍歷組合的方式生成項(xiàng)集；剪枝步驟通過預(yù)定義的支持度閾值裁剪掉不滿足條件的項(xiàng)集，從而得到滿足條件的頻繁項(xiàng)集.

利用頻繁項(xiàng)集挖掘車位空閑模式時(shí)，ti是每條事務(wù)中需要進(jìn)行連接的項(xiàng)，項(xiàng)與項(xiàng)進(jìn)行連接、剪枝后得到的頻繁項(xiàng)集則為業(yè)主提供了共享服務(wù)的車位空閑模式，每個(gè)模式表示對(duì)應(yīng)業(yè)主私人車位可以提供共享服務(wù)的開始時(shí)段Istart和結(jié)束時(shí)段Iend.

1.2 Hadoop 平臺(tái)

Hadoop 是一種大數(shù)據(jù)計(jì)算平臺(tái)，由分布式文件系統(tǒng)HDFS、并行計(jì)算框架MapReduce 和資源管理器Yarn構(gòu)成.Hadoop 具有高可靠、高擴(kuò)展和高容錯(cuò)等特性，以及對(duì)海量數(shù)據(jù)的高容存儲(chǔ)和高速計(jì)算等優(yōu)勢[11-13].Spark 是在Hadoop MapReduce 基礎(chǔ)上發(fā)展形成的一種大數(shù)據(jù)計(jì)算框架，其核心是基于內(nèi)存的計(jì)算.在執(zhí)行任務(wù)時(shí)，Spark 將中間數(shù)據(jù)緩存到內(nèi)存中，而Hadoop 將中間數(shù)據(jù)存儲(chǔ)在磁盤中.因此，Spark 相對(duì)于Hadoop 具有速度優(yōu)勢[14].但是，當(dāng)數(shù)據(jù)量超過T 級(jí)時(shí)，Spark 會(huì)出現(xiàn)OOM 內(nèi)存溢出，導(dǎo)致程序無法運(yùn)行.Hadoop 集群易于搭建維護(hù)，在執(zhí)行任務(wù)時(shí)需要更多的磁盤，而Spark 則需要更專業(yè)的專家團(tuán)隊(duì)維護(hù)，在執(zhí)行任務(wù)時(shí)需要更多的RAM.所以，Hadoop 的運(yùn)行成本和開銷更低[15-16].

針對(duì)本文的問題，在利用頻繁項(xiàng)集算法挖掘車位空閑模式時(shí)，業(yè)主出行數(shù)據(jù)越多，挖掘到的模式就越準(zhǔn)確，所以，需要長期不斷采集業(yè)主出行數(shù)據(jù)，根據(jù)歷史數(shù)據(jù)挖掘得到具有準(zhǔn)確支持度的車位空閑模式，從而為后續(xù)車位分配和管理等提供數(shù)據(jù)支持，這個(gè)過程是相對(duì)獨(dú)立的，適合離線計(jì)算，而且對(duì)實(shí)時(shí)性要求不高.因此，從數(shù)據(jù)量計(jì)算需求、平臺(tái)開發(fā)成本以及實(shí)時(shí)性需求等方面考慮，Hadoop 平臺(tái)更適用于本文問題.

2 車位空閑模式挖掘方法

2.1 頻繁項(xiàng)集挖掘方法的改進(jìn)

在Hadoop 上直接利用Apriori 的方法（HApriori方法）雖然相較于單機(jī)方式可以提高計(jì)算效率，但在進(jìn)行項(xiàng)之間的連接時(shí)會(huì)產(chǎn)生大量冗余的候選集，以致消耗更多的時(shí)空資源.為減少冗余候選集的生成，進(jìn)一步提高運(yùn)行效率，本文通過引入0-1 矩陣改進(jìn)HApriori 方法，記為HMApriori 方法. 該方法基于Apriori 算法的思想，將日常車位占用行為數(shù)據(jù)轉(zhuǎn)換成一個(gè)0-1 二維矩陣，矩陣的列向量表示事務(wù)集中參與運(yùn)算的項(xiàng)，行向量表示事務(wù)集中的一條數(shù)據(jù). 與HApriori 方法不同，HMApriori 方法不需要存儲(chǔ)實(shí)際項(xiàng)元素，只需用0 和1 表示該項(xiàng)的存在情況. 同時(shí)，在矩陣的每行每列最后增加1 位標(biāo)記位，用于標(biāo)記不滿足下次掃描條件的數(shù)據(jù).

2.2 HMApriori 方法

業(yè)主出行數(shù)據(jù)事務(wù)集記為S={S1，S2，…，SN}，Si為S 中的第i 個(gè)事務(wù)，項(xiàng)目集為I={I1，I2，…，IT}.將日常車位占用行為數(shù)據(jù)事務(wù)集轉(zhuǎn)換成0-1 矩陣MN×T，

mi，j表示事務(wù)Si中Ij項(xiàng)的對(duì)應(yīng)值，若Ij?[Tuplea，Tuparr]，則mi，j=1，否則mi，j=0，其中：Tuplea為業(yè)主u 離開車位p的時(shí)刻，Tuparr為業(yè)主u 到達(dá)車位p 的時(shí)刻.

1 項(xiàng)集定義為C1={Ix；x=1，2，…，T}；k 項(xiàng)集定義為Ck={Ix，Iy，…，Iz；x，y，…，z=1，2，…，T，x，y，…，z 互不相等，|{x，y，…，z}| = k}. k 項(xiàng)集的支持度為SupCk=定的最小支持度，則此k 項(xiàng)集稱為頻繁k 項(xiàng)集.

若事務(wù)Si包含的項(xiàng)目總數(shù)為L（L≤k），則該事務(wù)中的項(xiàng)在進(jìn)行連接時(shí)，最大可生成k 項(xiàng)集，所以，在生成k 項(xiàng)集之前可以先刪除項(xiàng)目總數(shù)小于k 的事務(wù).此外，因?yàn)轭l繁集的子集一定是頻繁集，所以在進(jìn)行項(xiàng)連接之前，可以先刪除非頻繁項(xiàng)所對(duì)應(yīng)的列.基于上述考慮，在原矩陣MN×T中增加行標(biāo)記和列標(biāo)記，形成矩陣M（N+1）×（T+1），

其中：mi，T+1記錄每行事務(wù)包含項(xiàng)目的總數(shù)，即第i 行中元素為1 的數(shù)量；mN+1，j的值是0 或1，0 表示該列對(duì)應(yīng)的項(xiàng)是非頻繁項(xiàng)，1 表示該列對(duì)應(yīng)的項(xiàng)是頻繁項(xiàng).

若行標(biāo)記mi，T+1＜k，則該行事務(wù)進(jìn)行項(xiàng)連接后不可能生成k 項(xiàng)集，所以直接刪去該行的事務(wù)數(shù)據(jù).列標(biāo)記值mN+1，j=0 對(duì)應(yīng)的項(xiàng)不需要參與到下一步項(xiàng)集的連接，為此，依次統(tǒng)計(jì)2 個(gè)值為0 的標(biāo)記位區(qū)間的項(xiàng)目總數(shù)Q.若Q≥k，則可以生成k 項(xiàng)集；否則不可能生成k 項(xiàng)集，所以直接略過該區(qū)間，跳入下一區(qū)間進(jìn)行判斷連接.上述項(xiàng)集連接過程偽碼見表1.

表1 HMApriori 的項(xiàng)集連接偽碼Tab.1 Pseudo code of itemset connects by HMApriori

HMApriori 的算法流程見圖1.

圖1 HMApriori 方法流程Fig.1 Flowchart of HMApriori

3 車位空閑模式的MapReduce 設(shè)計(jì)

MapReduce 是Hadoop 的一個(gè)編程模型，主要應(yīng)用于大規(guī)模數(shù)據(jù)并行計(jì)算，由Map 和Reduce 函數(shù)組成[17-18].

3.1 頻繁1 項(xiàng)集的MapReduce

第1 階段的MapReduce 用來生成頻繁1 項(xiàng)集，同時(shí)將結(jié)果保存至HDFS 中.首先，根據(jù)本地?cái)?shù)據(jù)建立矩陣，執(zhí)行Map 函數(shù)OneFrequentMapper（Key，Value0）計(jì)算頻繁1 項(xiàng)集，將每行數(shù)據(jù)轉(zhuǎn)換成鍵值對(duì)的形式，此時(shí)默認(rèn)輸入的鍵值對(duì)為[Key，Value]，Key 為輸入文件的編號(hào)，Value 為該文件記錄的矩陣；經(jīng)過中間處理后，得到Map 函數(shù)的中間鍵值對(duì)[item，IntWritable]，item 為1 項(xiàng)集，IntWritable 為初始計(jì)數(shù)，默認(rèn)值為1；接下來執(zhí)行Reduce 函數(shù)，Reduce 的輸入為每個(gè)Map函數(shù)輸出的中間鍵值對(duì)[item，IntWritable]，其中item和IntWritable 分別對(duì)應(yīng)Reduce 的Key*和Value*；然后利用OneFrequentReducer（Key*，Value*）整合相同的鍵，得到每個(gè)1 項(xiàng)集的支持度；最后，利用最小支持度minSup 的約束，得到頻繁1 項(xiàng)集Key*及其支持度Sup.頻繁1 項(xiàng)集的MapReduce 偽碼見表2.

表2 頻繁1 項(xiàng)集的MapReduce 偽碼Tab.2 Pseudo code of MapReduce for frequent 1 itemsets

3.2 頻繁k 項(xiàng)集的MapReduce

第2 階段的MapReduce 用來生成頻繁k 項(xiàng)集，同時(shí)將結(jié)果保存至HDFS 中.在第1 階段的MapReduce處理后，判斷矩陣M 中是否存有數(shù)據(jù)，若沒有數(shù)據(jù)，則任務(wù)停止，否則，執(zhí)行生成頻繁k 項(xiàng)集的MapReduce.首先，執(zhí)行Map 函數(shù)KFrequentMapper（Key，Value），Key 為數(shù)據(jù)文件的編號(hào)，Value 為文件的數(shù)據(jù)內(nèi)容；經(jīng)過中間處理后，得到Map 函數(shù)的中間鍵值對(duì)[kitem，IntWritable]，kitem 為k 項(xiàng)集；最后，執(zhí)行KFrequent-Reducer（Key*，Value*）對(duì)中間鍵值對(duì)進(jìn)行歸約處理，得到頻繁k 項(xiàng)集Key*及其支持度Sup.頻繁k 項(xiàng)集的MapReduce 偽碼見表3.

表3 頻繁k 項(xiàng)集的MapReduce 偽碼Tab.3 Pseudo code of MapReduce for frequent k itemsets

4 車位空閑模式挖掘方法的實(shí)現(xiàn)

4.1 實(shí)驗(yàn)環(huán)境

Hadoop 集群由4 臺(tái)PC 構(gòu)成，分別為Master、Slave1、Slave2 和Slave3. Master（172.19.205.158）為NameNode，負(fù)責(zé)整個(gè)任務(wù)的分工和數(shù)據(jù)存儲(chǔ)空間的分配，Slave1（172.19.205.159）、Slave2（172.19.205.160）和Slave3（172.19.205.161）為DataNode，負(fù)責(zé)存儲(chǔ)數(shù)據(jù)，執(zhí)行任務(wù)響應(yīng)客戶端，以及執(zhí)行NameNode 的讀寫請(qǐng)求等操作命令.集群架構(gòu)如圖2 所示.

圖2 Hadoop 集群架構(gòu)Fig.2 Hadoop cluster architecture

在Hadoop 集群中，各節(jié)點(diǎn)始終通過心跳機(jī)制Heart-Beats 保持通信，確保每個(gè)節(jié)點(diǎn)的基本生命情況和數(shù)據(jù)的正常讀寫.此外，采用Hadoop 的Yarn[19-20]框架實(shí)現(xiàn)全局資源管理和作業(yè)調(diào)度.

4.2 實(shí)驗(yàn)數(shù)據(jù)預(yù)處理

基于業(yè)主的出行行為，社區(qū)停車位空閑情況呈現(xiàn)一定的規(guī)律性.在業(yè)主授權(quán)的情況下，可直接從社區(qū)物業(yè)停車場管理部門獲取業(yè)主出行數(shù)據(jù)，這些數(shù)據(jù)記錄了業(yè)主基本身份信息和每天出入停車場的時(shí)間.為了在這些數(shù)據(jù)中挖掘到每個(gè)業(yè)主相應(yīng)車位的空閑時(shí)段，需要對(duì)原始數(shù)據(jù)進(jìn)行預(yù)處理.首先隱去身份信息，統(tǒng)一編碼；其次，將原始數(shù)據(jù)按等間隔ΔT 劃分并取值，生成業(yè)主出行事務(wù)集，事務(wù)集包含業(yè)主車位ID、日期以及每個(gè)時(shí)段車位空閑狀態(tài)取值.

4.3 實(shí)驗(yàn)結(jié)果分析

采用某社區(qū)2014 年到2019 年的停車場出入數(shù)據(jù)，使用HMApriori 方法對(duì)預(yù)處理后的數(shù)據(jù)進(jìn)行計(jì)算，得到每個(gè)業(yè)主的車位空閑模式. 以集群節(jié)點(diǎn)數(shù)為4、ΔT=15 min、支持度為80%為例，計(jì)算得到車位空閑模式的部分結(jié)果見表4.

表4 車位空閑模式部分結(jié)果Tab.4 Part of result of parking space idle pattern

實(shí)驗(yàn)1 考察不同T 值下，3 種方法Apriori、HApriori 和HMApriori 的執(zhí)行時(shí)間.T=（24×60）/ΔT，時(shí)間間隔ΔT 對(duì)程序的執(zhí)行效率有很大影響.選用3×105條業(yè)主出行數(shù)據(jù)，固定支持度為10%，集群節(jié)點(diǎn)數(shù)為4，圖3 給出了不同T 值下3 種方法的執(zhí)行時(shí)間.

由圖3 可見，隨著T 值增加，3 種方法的執(zhí)行時(shí)間均逐漸變長.當(dāng)T≤10 時(shí)，HApriori 和HMApriori 方法的執(zhí)行時(shí)間高于單機(jī)方式的Apriori 方法，這是因?yàn)楫?dāng)T 值較小時(shí)，傳統(tǒng)單機(jī)方式進(jìn)行的項(xiàng)連接步數(shù)較少，所以可以在較短時(shí)間內(nèi)得出結(jié)果，而HApriori 和HMApriori 除進(jìn)行項(xiàng)集的連接外，還要多次涉及Hadoop 文件的讀寫及任務(wù)的分配，導(dǎo)致執(zhí)行時(shí)間較長.當(dāng)10 ＜T≤15 時(shí)，Apriori 的執(zhí)行時(shí)間明顯高于另2種方法，這是因?yàn)閱螜C(jī)下Apriori 會(huì)生成大量候選集（2T個(gè)），造成內(nèi)存消耗嚴(yán)重，當(dāng)T ＞15 時(shí)，Apriori 方法出現(xiàn)內(nèi)存溢出，程序無法繼續(xù)進(jìn)行.由圖3 還可發(fā)現(xiàn)，對(duì)于不同的T 值，HMApriori 始終比HApriori 耗時(shí)少，這是因?yàn)镠MApriori 利用矩陣壓縮了事務(wù)集和項(xiàng)集，減少了事務(wù)集的掃描次數(shù)和項(xiàng)集的連接次數(shù)，避免了冗余候選集生成，進(jìn)而縮短整個(gè)程序的執(zhí)行時(shí)間.

圖3 不同T 值下3 種方法的執(zhí)行時(shí)間Fig.3 Execution time of 3 methods for different T

實(shí)驗(yàn)2 考察HApriori 和HMApriori 在不同支持度下的的執(zhí)行時(shí)間.選用3×105條業(yè)主出行數(shù)據(jù)，固定T = 96，集群節(jié)點(diǎn)數(shù)為4，圖4 給出了支持度為70%、80%和90%，2 種方法的執(zhí)行時(shí)間.由圖4 可見，2 種方法的執(zhí)行時(shí)間均隨支持度的提高而減少，這是因?yàn)橹С侄壬仙l繁項(xiàng)集的規(guī)模下降，產(chǎn)生的候選項(xiàng)集數(shù)量下降.另外，由圖4 還可見，在相同的支持度下，HMApriori 比HApriori 的執(zhí)行效率更高.

圖4 不同支持度下2 種方法的執(zhí)行時(shí)間Fig.4 Execution time of 2 methods for different supports

實(shí)驗(yàn)3 考察不同節(jié)點(diǎn)數(shù)對(duì)HMApriori 執(zhí)行時(shí)間的影響.固定T=96，支持度為60%，選用3 個(gè)數(shù)據(jù)集，圖5 給出了節(jié)點(diǎn)數(shù)為1、2、3 和4 的HMApriori 的執(zhí)行時(shí)間，其中：數(shù)據(jù)集Data1=207 110 kB，Data2=1 191 952 kB，Data3= 7 912 754 kB. 由圖5 可見，對(duì)于Data1，程序執(zhí)行時(shí)間隨節(jié)點(diǎn)數(shù)的變化不大，這是因?yàn)閿?shù)據(jù)量較小時(shí)，單個(gè)節(jié)點(diǎn)的MapReduce 任務(wù)就可以完成數(shù)據(jù)處理，不需要等待其他節(jié)點(diǎn)MapReduce任務(wù)結(jié)束再啟動(dòng)下一個(gè)任務(wù).所以，對(duì)于數(shù)據(jù)量較小的數(shù)據(jù)集，增加節(jié)點(diǎn)不會(huì)減少執(zhí)行時(shí)間，節(jié)點(diǎn)數(shù)越多，反而會(huì)增加數(shù)據(jù)存儲(chǔ)、任務(wù)分配和節(jié)點(diǎn)通信等額外開銷.對(duì)于Data2 和Data3，隨著節(jié)點(diǎn)數(shù)增加，程序執(zhí)行時(shí)間逐漸減少，這是因?yàn)楣?jié)點(diǎn)數(shù)的增加可以增加MapReduce 任務(wù)的數(shù)量，多個(gè)任務(wù)并行進(jìn)行顯著提高了集群處理數(shù)據(jù)的效率.

圖5 不同節(jié)點(diǎn)數(shù)HMApriori 的執(zhí)行時(shí)間Fig.5 Execution time of HMApriori for different node numbers

5 結(jié)語

采用Hadoop 平臺(tái)，基于Apriori 算法設(shè)計(jì)完成了車位空閑模式挖掘方法，解決了傳統(tǒng)模式下頻繁項(xiàng)集挖掘方法的內(nèi)存溢出問題，提高了程序的計(jì)算效率.實(shí)驗(yàn)結(jié)果表明，隨著業(yè)主數(shù)據(jù)集的增大，該方法的執(zhí)行效率明顯優(yōu)于傳統(tǒng)方式，為后續(xù)共享車位的分配提供了可靠的數(shù)據(jù)支持.