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

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

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

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

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

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

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

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