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

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

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

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

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

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