空間數(shù)據(jù)挖掘中PVI算法的研究與應(yīng)用.pdf

1、近些年來，空間信息技術(shù)領(lǐng)域的高速發(fā)展使我們進(jìn)入信息變革的時(shí)代。空間數(shù)據(jù)通過傳感器或者其他數(shù)據(jù)收集設(shè)備源源不斷地收集起來，并呈指數(shù)級(jí)增長(zhǎng)。為了能夠有效管理數(shù)據(jù)，人們發(fā)展了數(shù)據(jù)庫技術(shù)，并在此基礎(chǔ)上建立了空間信息系統(tǒng)。然而，空間信息系統(tǒng)目前仍然只能提供給我們數(shù)據(jù)，卻給不了我們數(shù)據(jù)以外的信息。人們已經(jīng)不再滿足于數(shù)據(jù)表層的檢索與查詢，而是希望更深一步的認(rèn)識(shí)數(shù)據(jù)，得到知識(shí)與發(fā)現(xiàn)。關(guān)聯(lián)規(guī)則挖掘可以從龐大的數(shù)據(jù)庫中發(fā)現(xiàn)人們感興趣的知識(shí)，但是需要花費(fèi)大量

2、的時(shí)間與資源。在空間關(guān)聯(lián)規(guī)則中引入并行計(jì)算，不但可以滿足人們對(duì)空間數(shù)據(jù)不斷增長(zhǎng)的認(rèn)知要求，還可以降低數(shù)據(jù)挖掘時(shí)的時(shí)間與資源的消耗，以多臺(tái)微型計(jì)算機(jī)來完成大型機(jī)才能完成的工作。經(jīng)典的關(guān)聯(lián)規(guī)則有Apriori 算法、DHP 算法、Partition 算法等等。它們主要應(yīng)用于顧客消費(fèi)分析、目錄設(shè)計(jì)、廣告郵件分析、銷售優(yōu)化、倉(cāng)儲(chǔ)規(guī)劃、網(wǎng)絡(luò)故障分析等。
　　 通過對(duì)劉永彬于2008年提出的TP-PB 算法的研究，本文提出了一種類似計(jì)算向量

3、內(nèi)積的并行關(guān)聯(lián)規(guī)則算法（Parallel Vectors Inner-product，PVI 算法）用于遙感數(shù)據(jù)挖掘系統(tǒng)。算法通過改進(jìn)計(jì)算頻繁項(xiàng)目集方法和優(yōu)化數(shù)據(jù)讀取，使算法尋找頻繁項(xiàng)目集的效率大幅度提高。同時(shí)利用“廉價(jià)”的微型計(jì)算機(jī)資源，按照數(shù)據(jù)特點(diǎn)采用并行計(jì)算使得整個(gè)空間關(guān)聯(lián)規(guī)則的挖掘效率進(jìn)一步提高。經(jīng)過對(duì)并行空間關(guān)聯(lián)規(guī)則的研究，取得了如下研究成果：
　　 1）簡(jiǎn)化計(jì)算頻繁項(xiàng)集的方法。使用布爾型數(shù)據(jù)可以有效降低了PVI 算法

4、的復(fù)雜度，并且PVI 算法使用類似計(jì)算向量?jī)?nèi)積的方法來計(jì)算候選頻繁項(xiàng)集，并利用k-1 階頻繁項(xiàng)集計(jì)算k 階頻繁項(xiàng)集，大大簡(jiǎn)化了計(jì)算步驟，提高了算法的并行性。
　　 2）減少掃描數(shù)據(jù)庫次數(shù)。TP-PB 算法發(fā)現(xiàn)知識(shí)時(shí)需要掃描數(shù)據(jù)庫2次，而PVI 算法通過計(jì)算時(shí)記錄有效信息，只需掃描數(shù)據(jù)庫一次，相比于TP-PB 算法減少了I/O 操作。數(shù)據(jù)的I/O 操作會(huì)占算法開銷的很大一部分，PVI 算法減少了對(duì)數(shù)據(jù)庫的掃描，大大提高了算法效率。

5、
　　 3）空間關(guān)聯(lián)規(guī)則引入并行計(jì)算。PVI 算法采取冗余存儲(chǔ)與減少I/O 操作來降低任務(wù)完成時(shí)間?？刂茩C(jī)將挖掘任務(wù)分配后，并行機(jī)自行根據(jù)任務(wù)在本地讀取數(shù)據(jù)，進(jìn)行知識(shí)發(fā)現(xiàn)。其次，為了使并行機(jī)盡量不處于空閑狀態(tài)，應(yīng)將子任務(wù)數(shù)量劃分為并行機(jī)個(gè)數(shù)的整數(shù)倍并兼顧粒度。
　　 4）將并行的空間關(guān)聯(lián)規(guī)則算法嵌入到遙感數(shù)據(jù)挖掘系統(tǒng)中，實(shí)現(xiàn)對(duì)海量遙感數(shù)據(jù)的展示與知識(shí)發(fā)現(xiàn)。采用B/S模式，使用戶可以通過網(wǎng)絡(luò)在網(wǎng)頁瀏覽器上隨時(shí)隨地查看遙感數(shù)