• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      時空同現(xiàn)挖掘算法及應(yīng)用研究

      2016-12-19 09:24:39張奕張永梅郭莎降愛蓮鄔小燕
      計算機時代 2016年11期
      關(guān)鍵詞:數(shù)據(jù)挖掘

      張奕 張永梅 郭莎 降愛蓮 鄔小燕

      摘 要: 在隱藏于歷史軌跡數(shù)據(jù)集的眾多模式中,同現(xiàn)模式的挖掘尤其引人關(guān)注。文章將時空同現(xiàn)的數(shù)據(jù)挖掘算法與Hadoop平臺相結(jié)合,實現(xiàn)了并行處理,對軌跡數(shù)據(jù)進行預(yù)處理,并設(shè)計了時空同現(xiàn)模式挖掘算法。實驗結(jié)果表明,該算法能夠挖掘乘客集中地,為出租車司機提供合理有效的載客路徑。

      關(guān)鍵詞: 時空同現(xiàn); 并行處理; 出租車軌跡數(shù)據(jù); 數(shù)據(jù)挖掘

      中圖分類號:TP311 文獻標(biāo)志碼:A 文章編號:1006-8228(2016)11-05-02

      Spatiotemporal co-occurrence mining algorithm and the application

      Zhang Yi1, Zhang Yongmei2, Guo Sha2, Jiang Ailian3, Wu Xiaoyan2

      (1. College of Software, Taiyuan University of Technology, Shanxi, Taiyuan 030600, China; 2. College of Computer, North China University of Technology; 3. College of Computer Science and Technology, Taiyuan University of Technology)

      Abstract: Among the many modes hidden in the historical trajectory data set, mining the co-occurrence modes is particularly concerned. In this paper, combining the spatiotemporal co-occurrence data mining algorithm with Hadoop platform, the parallel processing is realized to pre-process the trajectory data, and the spatiotemporal co-occurrence mining algorithm is designed. The experiment results show that the algorithm can mining concentrated areas of passengers, and provide reasonable and effective paths for taxi drivers.

      Key words: spatiotemporal co-occurrence; parallel processing; taxi trajectory data; data mining

      0 引言

      時空同現(xiàn)模式就是在時空維度下,不同對象類型子集的實例在一些時間段內(nèi),在空間上是相互鄰近的,或符合某種空間關(guān)系的對象集合。在許多應(yīng)用領(lǐng)域如:環(huán)境監(jiān)測、搶險救災(zāi)、基于位置的服務(wù)等,數(shù)據(jù)都隨著時間變化而變化。然而,大多數(shù)數(shù)據(jù)庫都不能有效地處理數(shù)據(jù)的時間維度。當(dāng)數(shù)據(jù)發(fā)生變化時,無法對數(shù)據(jù)變化的趨勢進行分析,更無法預(yù)測未來的趨勢。因此,從這些大量的數(shù)據(jù)中挖掘出有價值的信息變得更加重要,時空同現(xiàn)模式挖掘成為研究熱點。

      隨著移動電話、GPS(Global Positioning System,全球定位系統(tǒng))等具備定位功能的設(shè)備普及,產(chǎn)生了大量基于時間和空間的移動對象歷史軌跡數(shù)據(jù)。在地理信息系統(tǒng)中,移動對象的歷史位置信息日益重要,在這一背景下,針對移動對象歷史軌跡的數(shù)據(jù)挖掘研究成為當(dāng)前研究熱點之一[1-2]。與傳統(tǒng)事務(wù)性數(shù)據(jù)集相比,從空間數(shù)據(jù)集中識別感興趣的模式更為困難和復(fù)雜,因為空間數(shù)據(jù)集具有復(fù)雜的數(shù)據(jù)類型和關(guān)系,而且數(shù)據(jù)總量龐大。在隱藏于歷史軌跡數(shù)據(jù)集的眾多模式中,同現(xiàn)模式的挖掘尤其引人關(guān)注??臻g數(shù)據(jù)集的同現(xiàn)模式直觀地反映了移動過程中移動對象之間相互接觸的情況,所以快速準(zhǔn)確地挖掘時空數(shù)據(jù)中的同現(xiàn)模式有利于推動眾多領(lǐng)域的研究,如生態(tài)、電力系統(tǒng)故障分析、軍事等。

      雖然時空同現(xiàn)模式挖掘已經(jīng)取得了一些令人欣慰的研究成果,但總體來說還處于起步階段。隨著空間數(shù)據(jù)采集效率的提高,空間數(shù)據(jù)逐漸增大。在時空同現(xiàn)模式挖掘研究領(lǐng)域中,MeteCelik等人提出的混合驅(qū)動的時空同現(xiàn)模式挖掘最具有代表性。為了挖掘時空同現(xiàn)模式,他們提出了混合時空同現(xiàn)模式挖掘算法。該挖掘算法是基于連接操作的,會消耗大量時間生成候選模式集,隨著對象類型的增多,需要生成的候選模式集數(shù)量呈指數(shù)級增長,這意味著需要消耗的計算時間迅速增長,計算效率無法隨著對象類型的增加而迅速增長,不能處理龐大的時空數(shù)據(jù);同時該算法是基于內(nèi)存的,無法處理大量時空數(shù)據(jù)[3-5]。本文對出租車軌跡數(shù)據(jù)進行分析與挖掘,將時空同現(xiàn)的數(shù)據(jù)挖掘算法與Hadoop平臺相結(jié)合,可以有效解決數(shù)據(jù)存儲和運行慢的問題,同時又能高效獲取潛在信息。

      1 時空同現(xiàn)挖掘算法的設(shè)計及實現(xiàn)

      1.1 并行處理方法的實現(xiàn)

      本文采用云計算理念,促進資源管理和高效利用,提升系統(tǒng)構(gòu)建的速度和靈活性。構(gòu)建基于云計算的數(shù)據(jù)環(huán)境,改善傳統(tǒng)的應(yīng)用與硬件綁定、不易維護、難以擴展等問題。大數(shù)據(jù)批處理需求主要針對復(fù)雜分布式編程,通過先存儲后計算的模式,允許對存儲單元的內(nèi)容進行多次操作,從而為復(fù)雜計算提供支撐。當(dāng)前,大數(shù)據(jù)批處理計算技術(shù)主要包括MapReduce、Dryad和spark等。

      MapReduce是Google開發(fā)的一種簡潔抽象的分布式計算模型,在處理T級別以上巨量數(shù)據(jù)的業(yè)務(wù)上具有明顯優(yōu)勢。在MapReduce中,應(yīng)用的原始數(shù)據(jù)被劃分為多個用于并行計算的數(shù)據(jù)分片split,以顯式地挖掘應(yīng)用中的并行性。為了更好地描述問題的并行求解,split 被定義為數(shù)據(jù)域、屬性域和狀態(tài)描述域三部分。MapReduce 運行時系統(tǒng)是無狀態(tài)的,各個split保存自身狀態(tài)信息,便于將來checkpoint等功能的實現(xiàn)。MapReduce還提供了對數(shù)據(jù)分片的map和reduce計算。MapReduce已有多種實現(xiàn),最著名的是Hadoop,Hadoop靈活易用、可靠高效,已成為目前分布式海量數(shù)據(jù)處理的首選工具。

      本文選擇Apache的Hadoop作為整個系統(tǒng)的底層計算平臺,主要使用Hadoop的分布式文件存儲系統(tǒng)HDFS和并行計算系統(tǒng)MapReduce。Hadoop環(huán)境搭建在vmware安裝好ubuntu的條件下。本文采用HDFS分布架構(gòu)系統(tǒng),把需處理的任務(wù)分布到多個計算機上,把一臺計算機作為NameNode結(jié)點,再選另外幾臺計算機作為DataNode,提高運算效率,同時也采用了MapReduce,利用它的并行處理功能,提高運算速度。

      1.2 數(shù)據(jù)的預(yù)處理方法

      本文采用的數(shù)據(jù)是網(wǎng)上下載的軌跡數(shù)據(jù),該數(shù)據(jù)是微軟亞洲研究院在Geolife 項目中收集的北京市出租車軌跡數(shù)據(jù),收集時間段:2008年2月2日-2月8日。數(shù)據(jù)平均采樣間隔約177秒,距離約623米。本文的數(shù)據(jù)預(yù)處理主要包括:計算速度、出租車??奎c的分析。計算速度是根據(jù)數(shù)據(jù)文件里所給的同一車輛在不同時間點上處于不同的經(jīng)緯度,經(jīng)過轉(zhuǎn)換和計算獲得兩點間的歐氏距離,利用距離除以相隔時間,得到在每個時間間隔內(nèi)的出租車速度。出租車??奎c的分析是結(jié)合出租車速度和時間空間,進行出租車??奎c的分析,即篩選出出租車載客的地點,過濾掉造成干擾的點。

      1.3 時空同現(xiàn)模式挖掘算法具體步驟及實現(xiàn)

      本文根據(jù)空間鄰近距離R計算出所有時間槽內(nèi)的空間鄰近模式,對于所有時間槽內(nèi)的空間鄰近模式計算各模式的實例支持度,與空間頻繁閾值進行比較,挖掘出滿足閾值的空間同位模式集,再縱向考慮所有時間槽,統(tǒng)計各個空間同位模式的時間頻繁度,找出滿足時間頻繁閾值的時空同現(xiàn)模式,進行時空同現(xiàn)模式的挖掘計算。時空同現(xiàn)模式挖掘算法具體步驟如下。

      ⑴ 初始化各個時間槽實例之間的空間關(guān)系,對時空數(shù)據(jù)集建立時空網(wǎng)絡(luò)模型STCOPG;

      ⑵ 設(shè)置k=1;

      ⑶ 根據(jù)STCOPG圖,生成k+1元候選時空同現(xiàn)模式;

      ⑷ 通過查詢STCOPG獲得候選時空同現(xiàn)模式的實例集,計算時空頻繁度,生成k+l元時空同現(xiàn)模式;

      ⑸ 重復(fù)生成候選同現(xiàn)模式操作,直到無新的候選同現(xiàn)模式或新的時空同現(xiàn)模式生成,算法結(jié)束;

      ⑹ 合并得到所有符合時空閾值的時空同現(xiàn)模式集。

      根據(jù)大量實驗結(jié)果,本文的時空鄰近距離、空間頻繁閾值、時間頻繁閾值分別為4km、0.5和0.4。圖1給出了2008年2月4日下午2點出租車位于北京交通大學(xué),相對于出租車所處位置來說,在空間上鄰近的時空同現(xiàn)挖掘結(jié)果。

      在圖1中,出租車位于北京交通大學(xué),也就是標(biāo)識為TAXI的位置,相對于出租車所處位置來說,在空間上鄰近的一些熱點的分布圖,也就是出租車司機在下午2點時,開車去如圖1所示的熱點分布的地方最容易載到乘客。

      2 結(jié)束語

      時空同現(xiàn)模式挖掘從其產(chǎn)生至今,就一直受到各界研究人員的關(guān)注。挖掘時空模式是非常有意義的,并且具有挑戰(zhàn)性,它可以應(yīng)用于軍事、道路的交通管制、災(zāi)情分析、案件偵破、國防、生態(tài)等領(lǐng)域。本文研究了時空同現(xiàn)挖掘算法及應(yīng)用,可以有效挖掘乘客集中地,為出租車司機提供合理有效的載客路徑。進一步需要研究時空鄰近距離、空間頻繁閾值、時間頻繁閾值的自適應(yīng)選取。

      參考文獻(References):

      [1] 齊林.基于GPS數(shù)據(jù)的出租車交通運行特性研究及應(yīng)用[D].

      哈爾濱工業(yè)大學(xué)碩士學(xué)位論文,2013.

      [2] 叢湘香.大數(shù)據(jù)下時空同現(xiàn)模式挖掘算法研究[D].華東理工

      大學(xué)碩士學(xué)位論文,2012.

      [3] 陳延平.基于局部時空共現(xiàn)特征的人體行為識別方法研究[D].

      廈門大學(xué)碩士學(xué)位論文,2012.

      [4] 黃照鶴,戴健.基于時空同現(xiàn)挖掘技術(shù)的FNRB-Tree[J].小型

      微型計算機系統(tǒng),2012.33(12):2636-2641

      [5] 許強,羅澤,魏穎,閻保平.一種檢測時空數(shù)據(jù)中重要同現(xiàn)模式的

      快速算法[J].科研信息化技術(shù)與應(yīng)用,2013.4(3):23-31

      猜你喜歡
      數(shù)據(jù)挖掘
      基于數(shù)據(jù)挖掘的船舶通信網(wǎng)絡(luò)流量異常識別方法
      探討人工智能與數(shù)據(jù)挖掘發(fā)展趨勢
      數(shù)據(jù)挖掘技術(shù)在打擊倒賣OBU逃費中的應(yīng)用淺析
      基于并行計算的大數(shù)據(jù)挖掘在電網(wǎng)中的應(yīng)用
      電力與能源(2017年6期)2017-05-14 06:19:37
      數(shù)據(jù)挖掘技術(shù)在中醫(yī)診療數(shù)據(jù)分析中的應(yīng)用
      一種基于Hadoop的大數(shù)據(jù)挖掘云服務(wù)及應(yīng)用
      數(shù)據(jù)挖掘在高校圖書館中的應(yīng)用
      數(shù)據(jù)挖掘的分析與探索
      河南科技(2014年23期)2014-02-27 14:18:43
      基于GPGPU的離散數(shù)據(jù)挖掘研究
      利用數(shù)據(jù)挖掘技術(shù)實現(xiàn)LIS數(shù)據(jù)共享的開發(fā)實踐
      修武县| 扬州市| 云阳县| 文化| 裕民县| 石嘴山市| 堆龙德庆县| 灵寿县| 凌海市| 民县| 惠东县| 平昌县| 黄陵县| 石泉县| 阿坝| 日喀则市| 永胜县| 南溪县| 海口市| 西华县| 胶南市| 年辖:市辖区| 武隆县| 杭锦旗| 六盘水市| 远安县| 长海县| 共和县| 博罗县| 巴彦淖尔市| 武安市| 石阡县| 安达市| 麟游县| 通城县| 阜康市| 龙门县| 鲁甸县| 屏南县| 惠来县| 大城县|