基于位表的關(guān)聯(lián)規(guī)則挖掘及關(guān)聯(lián)分類研究.pdf

1、隨著人們利用信息技術(shù)生產(chǎn)和搜集數(shù)據(jù)的能力大幅度提高，數(shù)據(jù)資料的規(guī)模急速膨脹。如何快速有效的從海量數(shù)據(jù)中發(fā)現(xiàn)隱藏的、預(yù)先未知的信息和知識顯得尤為重要，數(shù)據(jù)挖掘是解決這一問題的有力工具。關(guān)聯(lián)規(guī)則(Association Rules)獲取是數(shù)據(jù)挖掘研究的一個(gè)重要領(lǐng)域，從某種意義上來講，關(guān)聯(lián)規(guī)則挖掘就是數(shù)據(jù)挖掘的本質(zhì)。近年來相關(guān)的研究與應(yīng)用一直占有重要的比例并得到了迅速發(fā)展。研究如何快速有效的從海量數(shù)據(jù)庫中挖掘蘊(yùn)含其中的關(guān)聯(lián)規(guī)則，并將挖掘得到的

2、關(guān)聯(lián)規(guī)則合理利用，具有十分重要的理論和實(shí)際意義。本文在分析現(xiàn)有挖掘算法中存在問題的基礎(chǔ)上，提出基于位表的完全頻繁項(xiàng)集和事務(wù)間頻繁閉項(xiàng)集的挖掘算法，并進(jìn)一步研究關(guān)聯(lián)規(guī)則在分類問題中的應(yīng)用，利用其解決遙感影像分類問題。本文的研究工作可概括為如下三個(gè)方面的內(nèi)容： 1、研究事務(wù)內(nèi)完全頻繁項(xiàng)集的快速挖掘算法?，F(xiàn)有的完全頻繁項(xiàng)集挖掘算法多基于Apriori算法，稱為Apriori類算法。其在生成候選集須逐個(gè)比較兩個(gè)項(xiàng)集的前n-1項(xiàng)，并且在計(jì)

3、算支持度需對全部或部分?jǐn)?shù)據(jù)庫進(jìn)行逐條掃描，占用大量的計(jì)算時(shí)間和I/O操作，成為此類算法的主要瓶頸。針對以上問題，本文首先提出了位表(BitTable)數(shù)據(jù)結(jié)構(gòu)及其相應(yīng)的二進(jìn)制操作。利用其對事務(wù)數(shù)據(jù)庫進(jìn)行壓縮，同時(shí)通過二進(jìn)制“與”、“或”操作快速計(jì)算候選項(xiàng)集的支持度，改善了低效率的數(shù)據(jù)庫掃描操作；利用其對候選項(xiàng)集和頻繁項(xiàng)集進(jìn)行橫向壓縮，可直接生成候選項(xiàng)集，避免了逐項(xiàng)比較的復(fù)雜操作。該數(shù)據(jù)結(jié)構(gòu)及其操作可以直接應(yīng)用于現(xiàn)有的Apriori類算法

4、中，有效地改善此類算法的效率問題。在位表數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上，本文進(jìn)一步提出了基于位表的關(guān)聯(lián)規(guī)則挖掘算法BitTableFI。對常用數(shù)據(jù)集的仿真試驗(yàn)表明了該算法的有效性。 2、研究事務(wù)間頻繁閉項(xiàng)集及其快速挖掘算法。相對于事務(wù)內(nèi)頻繁項(xiàng)集，事務(wù)間頻繁項(xiàng)集能夠有效的揭示各屬性在不同時(shí)刻的關(guān)聯(lián)性，是事務(wù)內(nèi)頻繁項(xiàng)集的擴(kuò)展。然而事務(wù)間頻繁項(xiàng)集的數(shù)量隨滑動時(shí)間窗口的增大而迅速增加，造成挖掘效率降低，利用閉項(xiàng)集來表示事物間頻繁項(xiàng)集能夠在不丟失信息的

5、情況下有效的減少項(xiàng)集的數(shù)量。本文通過分析事務(wù)內(nèi)頻繁閉項(xiàng)集和事務(wù)間頻繁閉項(xiàng)的內(nèi)在關(guān)系，提出了一種利用事務(wù)內(nèi)頻繁閉項(xiàng)集生成事務(wù)間頻繁閉項(xiàng)集的算法。算法采用分割和條件數(shù)據(jù)庫技術(shù)，有效的避免了生成龐大的擴(kuò)展事務(wù)數(shù)據(jù)庫，利用擴(kuò)展的位表結(jié)構(gòu)壓縮事務(wù)從而提高支持度的計(jì)算效率。此外，采用動態(tài)排序和哈希技術(shù)極大地減少了頻繁閉項(xiàng)集的測試次數(shù)。該算法為挖掘事物間頻繁閉項(xiàng)集提供了一種有效而快速的算法。 3、研究模糊關(guān)聯(lián)分類算法，并利用其解決遙感影像分

6、類問題。關(guān)聯(lián)分類將挖掘獲取的頻繁項(xiàng)集應(yīng)用于解決分類問題，將關(guān)聯(lián)規(guī)則的挖掘和應(yīng)用問題緊密結(jié)合。將模糊方法引入到關(guān)聯(lián)分類問題中，能夠較好的解決規(guī)則的“尖銳邊界“問題。然而，現(xiàn)有的模糊關(guān)聯(lián)分類算法多采用固定模糊隸屬度函數(shù)對連續(xù)型屬性進(jìn)行模糊劃分，沒有考慮數(shù)據(jù)本身的特性。基于此，本章提出一種基于自適應(yīng)區(qū)間劃分的模糊關(guān)聯(lián)分類算法—FARC(Fuzzy association rules classification)，利用模糊c均值聚類算法根據(jù)數(shù)

7、據(jù)本身的特點(diǎn)自適應(yīng)地建立模糊區(qū)間，并在挖掘模糊關(guān)聯(lián)規(guī)則時(shí)采用了新的剪枝策略，極大地減少了候選集的數(shù)量。新的規(guī)則權(quán)重度量方法能夠更好的利用多模糊關(guān)聯(lián)規(guī)則進(jìn)行分類。對UC Irvine Machine Learning Repository測試數(shù)據(jù)的實(shí)驗(yàn)表明，F(xiàn)ARC不僅是具有高精度的分類精度，同時(shí)具有對訓(xùn)練樣本數(shù)量的不敏感性，在訓(xùn)練樣本減少的情況下仍能保持較好的分類精度，是一種有效的分類方法。同時(shí)，本文將模糊關(guān)聯(lián)分類算法引入遙感圖像分類問