海量流數(shù)據(jù)挖掘相關(guān)問(wèn)題研究.pdf

1、隨著移動(dòng)終端、傳感器、互聯(lián)網(wǎng)等技術(shù)的飛速發(fā)展，流數(shù)據(jù)作為一種典型的大數(shù)據(jù)已經(jīng)在許多領(lǐng)域廣泛出現(xiàn)。當(dāng)前，流數(shù)據(jù)包含時(shí)空數(shù)據(jù)、傳感數(shù)據(jù)、社交網(wǎng)絡(luò)數(shù)據(jù)等多種類型數(shù)據(jù)，數(shù)據(jù)本身蘊(yùn)含巨大的價(jià)值，這使得流數(shù)據(jù)挖掘具有重要的學(xué)術(shù)價(jià)值和應(yīng)用價(jià)值。與靜態(tài)數(shù)據(jù)相比，流數(shù)據(jù)有其自身特點(diǎn):原始數(shù)據(jù)量巨大、數(shù)據(jù)到達(dá)速度快、數(shù)據(jù)處理對(duì)時(shí)效性要求高、數(shù)據(jù)難以重復(fù)獲取。由于流數(shù)據(jù)自身的特點(diǎn)，一些已有的數(shù)據(jù)挖掘技術(shù)很難直接用來(lái)解決流數(shù)據(jù)挖掘問(wèn)題，因此研究流數(shù)據(jù)挖掘相關(guān)問(wèn)

2、題具有重要意義。
　　本文針對(duì)海量流數(shù)據(jù)挖掘領(lǐng)域的相關(guān)問(wèn)題進(jìn)行了研究。第一個(gè)問(wèn)題是多數(shù)據(jù)流的頻繁伴隨模式發(fā)現(xiàn)問(wèn)題。頻繁伴隨模式（Frequent Co-occurrence Pattern）是指一組對(duì)象較短時(shí)間內(nèi)在同一個(gè)數(shù)據(jù)流里伴隨出現(xiàn)，并且在之后指定的一段時(shí)間內(nèi)以同樣的方式出現(xiàn)在多個(gè)數(shù)據(jù)流上。本文的目標(biāo)是實(shí)時(shí)發(fā)現(xiàn)多個(gè)數(shù)據(jù)流里出現(xiàn)的所有頻繁伴隨模式。在實(shí)際應(yīng)用中，城市交通管控系統(tǒng)的伴隨車輛發(fā)現(xiàn)、電子商務(wù)中的熱銷商品組合挖掘、基于簽

3、到數(shù)據(jù)的伴隨人群發(fā)現(xiàn)以及社交網(wǎng)絡(luò)數(shù)據(jù)中基于高頻伴隨詞組的熱點(diǎn)事件發(fā)現(xiàn)等應(yīng)用都可以抽象為多數(shù)據(jù)流的頻繁伴隨模式發(fā)現(xiàn)問(wèn)題。為解決這一問(wèn)題，本文提出了基于segment片段的流數(shù)據(jù)劃分策略，并設(shè)計(jì)了DIMine和CooMine兩種挖掘方法。這兩種算法首先對(duì)有效的segment片段建立索引，然后基于segment索引結(jié)構(gòu)設(shè)計(jì)剪枝策略，通過(guò)不斷削減挖掘范圍以達(dá)到快速發(fā)現(xiàn)頻繁伴隨模式的目的。
　　DIMine和CooMine挖掘算法在挖掘效率

4、、內(nèi)存消耗和索引維護(hù)代價(jià)取得了很好的效果。但它們是適合單機(jī)運(yùn)行的集中式算法，難以直接部署到分布式環(huán)境中應(yīng)對(duì)規(guī)模巨大的流數(shù)據(jù)。為了能夠在大規(guī)模流數(shù)據(jù)中發(fā)現(xiàn)頻繁伴隨模式，本文設(shè)計(jì)了多數(shù)據(jù)流頻繁伴隨模式的分布式挖掘方法。該方法首先產(chǎn)生所有數(shù)據(jù)流中可能形成頻繁伴隨模式的候選模式，然后通過(guò)哈希方法將不同數(shù)據(jù)流的相同候選模式發(fā)送至至同一個(gè)計(jì)算單元，繼而判定該候選模式是否為頻繁伴隨模式。由于每個(gè)候選模式是獨(dú)立的，不同的候選模式可以由多個(gè)計(jì)算單元同時(shí)處

5、理，因此該方法能夠利用分布式服務(wù)器集群進(jìn)行并行計(jì)算，從而具備良好的可擴(kuò)展性。
　　本文研究的第三個(gè)問(wèn)題是分布式時(shí)空數(shù)據(jù)的k近鄰搜索問(wèn)題。時(shí)空數(shù)據(jù)是一種典型的流數(shù)據(jù)，k近鄰搜索是許多數(shù)據(jù)挖掘問(wèn)題的基本操作。給定一個(gè)時(shí)空數(shù)據(jù)集和任意一個(gè)查詢點(diǎn)，k近鄰搜索要求實(shí)時(shí)地得到該時(shí)空數(shù)據(jù)集中與該查詢點(diǎn)距離最近的k個(gè)對(duì)象。已有的時(shí)空數(shù)據(jù)k近鄰搜索算法通常假設(shè)時(shí)空數(shù)據(jù)集規(guī)模有限且查詢數(shù)量較少，其研究重點(diǎn)是面向單個(gè)計(jì)算節(jié)點(diǎn)的k近鄰集中式查詢算法，很難

6、將它們應(yīng)用到分布式環(huán)境下以處理大規(guī)模時(shí)空數(shù)據(jù)和高并發(fā)k近鄰搜索。為此，本文提出了面向海量時(shí)空數(shù)據(jù)的分布式k近鄰搜索算法。該算法首先設(shè)計(jì)了分布式動(dòng)態(tài)條狀索引結(jié)構(gòu)(DynamicStrip Index，DSI)，與已有的網(wǎng)格索引相比，DSI索引結(jié)構(gòu)能夠適應(yīng)不同的數(shù)據(jù)分布。此外，DSI索引結(jié)構(gòu)更容易分布式部署到多個(gè)計(jì)算節(jié)點(diǎn)之上?；谠撍饕?，我們?cè)O(shè)計(jì)了DKNN查詢算法。該算法能夠?qū)NN查詢的迭代次數(shù)減少至兩次，與已有的算法相比，DKNN算法的

7、性能更加高效且可以預(yù)測(cè)。隨后，我們將DSI索引結(jié)構(gòu)和DKNN查詢算法在開源的流數(shù)據(jù)處理平臺(tái)S4上進(jìn)行了實(shí)現(xiàn)，通過(guò)大量實(shí)驗(yàn)證明了算法良好的可擴(kuò)展性和優(yōu)異性能。
　　本文對(duì)流數(shù)據(jù)挖掘相關(guān)問(wèn)題進(jìn)行了深入研究，針對(duì)特定問(wèn)題，給出了針對(duì)性的解決方案。本文的創(chuàng)新點(diǎn)和貢獻(xiàn)如下:
　　(1)本文首次提出多數(shù)據(jù)流頻繁伴隨模式發(fā)現(xiàn)這一問(wèn)題，并給出了DIMine算法和CooMine算法兩種解決方案。
　　(2)本文提出了分布式的多數(shù)據(jù)流頻繁