頻繁閉合項集挖掘算法及應(yīng)用研究.pdf

1、頻繁項集的挖掘是數(shù)據(jù)挖掘中的一個基礎(chǔ)和核心問題，具有廣泛的應(yīng)用領(lǐng)域。由于它是關(guān)聯(lián)性挖掘過程中最耗時的部分，挖掘算法的好壞直接影響數(shù)據(jù)挖掘的效率和應(yīng)用范圍。因此，頻繁項集挖掘算法的研究具有重要的理論和應(yīng)用價值。
　　 頻繁項集挖掘輸出的項集集合通常非常龐大。在生成的頻繁集中，有相當(dāng)大一部分是冗余的信息。這不僅帶來了時間和空間上效率低下的問題，而且會導(dǎo)致生成許多冗余的關(guān)聯(lián)規(guī)則。針對這個問題，存在兩種解決方案。一種稱為最大頻繁項集，即

2、挖掘頻繁項集晶格中的最小元素。另一種稱為閉合頻繁項集，即挖掘Galois算子定義的頻繁項集等價類內(nèi)部的最小元素。閉合頻繁項集保證沒有任何信息損失，而最大頻繁項集挖掘則無法保證。
　　 在廣泛查閱國內(nèi)外文獻的基礎(chǔ)上，圍繞“頻繁閉合項集”的概念，從傳統(tǒng)的批量式算法，在線的增量式算法，具備高容錯性的近似算法，以及頻繁閉合項集在推薦系統(tǒng)中的應(yīng)用這四個角度出發(fā)，展開系統(tǒng)的討論：
　　 1.批量式算法：
　　 提出一個簡單高

3、效的頻繁閉合項集的批量式算法FCII。FCII基于一種與目標(biāo)問題等價的新表達方式，并采用深度優(yōu)先的先序搜索策略以及高效的冗余信息檢測技術(shù)。理論分析得出，F(xiàn)CII可以在線性時間內(nèi)找到所有的頻繁閉合項集。實驗數(shù)據(jù)表明，F(xiàn)CII在標(biāo)準(zhǔn)數(shù)據(jù)集上的測試結(jié)果比業(yè)界領(lǐng)先的同類算法，如CLOSET+，F(xiàn)PCLOSE等有更好的性能。而且，F(xiàn)CII可以增量式的處理列維度的數(shù)據(jù)添加行為。最后，F(xiàn)CII可以同時得到項集維度與事務(wù)集維度的雙重信息，這是傳統(tǒng)的頻繁

4、閉合項集挖掘算法無法做到的。
　　 2.增量式算法：
　　 數(shù)據(jù)流環(huán)境具有海量數(shù)據(jù)，快速輸入，動態(tài)變化等特性。這些特性給傳統(tǒng)的數(shù)據(jù)挖掘算法提出了巨大的挑戰(zhàn)。傳統(tǒng)的數(shù)據(jù)挖掘算法允許多次遍歷數(shù)據(jù)集，但在數(shù)據(jù)流環(huán)境下，因為海量數(shù)據(jù)與動態(tài)變化的特性，數(shù)據(jù)流中的每一個數(shù)據(jù)元素只能訪問一次；而且快速輸入的特性給數(shù)據(jù)挖掘算法提出了很高的實時性要求。GC-Tree以及GC-Tree2.0是工作在數(shù)據(jù)流滑動窗口模型下的增量式算法。GC-T

5、ree在內(nèi)存中維持一棵樹狀結(jié)構(gòu)，樹中的節(jié)點與數(shù)據(jù)集中的閉合項集一一對應(yīng)，并且從每一個節(jié)點到根節(jié)點的序列構(gòu)成了該節(jié)點對應(yīng)的閉合項集唯一的有序生成項集序列。在該樹狀結(jié)構(gòu)的基礎(chǔ)上，GC-Tree算法設(shè)計高效的搜索空間裁剪策略以及節(jié)點更新技術(shù)。理論分析表明，GG-Tree的計算復(fù)雜度為事務(wù)的平均長度的二次方函數(shù)。在GC-Tree的基礎(chǔ)上，提出了改進算法GC-tree2.0。該算法通過簡單的交集操作來發(fā)現(xiàn)所有新增的閉合項集。理論分析表明，GC-T

6、ree2.0的時間復(fù)雜度為閉合項集平均長度的線性函數(shù)。上述的理論分析均可以得到實驗數(shù)據(jù)的有力支持。
　　 3.近似算法：
　　 由信息缺失，測量誤差導(dǎo)致的噪音數(shù)據(jù)廣泛的存在于各種數(shù)據(jù)庫中。最近的理論研究表明，這些噪音和誤差使得頻繁項集挖掘得到的模式嚴(yán)重失真，并且將較長的頻繁模式切割成許多對數(shù)級別大小的碎片。若能有效的去除噪音，則不僅可以恢復(fù)真實的頻繁模式，而且可以將數(shù)據(jù)挖掘輸出項集的數(shù)量成倍的減少。因此，開發(fā)具有高容錯性

7、的頻繁閉合項集挖掘算法是一個重要的課題。
　　 AFCIM是工作在噪音環(huán)境下的近似頻繁閉合項集挖掘算法。AFCIM算法是FCII算法的一個變種。該算法在搜索頻繁閉合項集的同時檢測數(shù)據(jù)集中的噪音數(shù)據(jù)，一旦發(fā)現(xiàn)噪音數(shù)據(jù)，立即更新數(shù)據(jù)集并動態(tài)更新已經(jīng)發(fā)現(xiàn)的頻繁閉合項集的集合。每一次這樣的噪音數(shù)據(jù)修正迭代，都能恢復(fù)一部分真實的頻繁模式，并將大量減少潛在的頻繁閉合項集的數(shù)量。實驗結(jié)果表明在輸出結(jié)果的質(zhì)量得到保證的前提下AFCIM的性能遠遠

8、高于同類算法AFI與AC-CLOSE。
　　 4.在推薦系統(tǒng)中的應(yīng)用：
　　 介紹了推薦系統(tǒng)的研究現(xiàn)狀，并分析了傳統(tǒng)的推薦系統(tǒng)存在的兩個內(nèi)在缺陷，即維度效應(yīng)與數(shù)據(jù)稀疏性。為了解決這兩個問題，根據(jù)“用戶偏好局部性假設(shè)”，本文提出了“局部化方法”的思路。即通過AFCIM算法從整體稀疏的數(shù)據(jù)矩陣中挖掘出局部稠密的子矩陣，然后在稠密子矩陣內(nèi)部建立局部的預(yù)測模型，通過計算不同局部模型的加權(quán)均值來為用戶做出綜合性的推薦。1-pLSI