關聯(lián)規(guī)則挖掘在分類數據領域的擴展性研究.pdf

1、隨著計算機技術在社會各個領域的廣泛應用，人們對信息系統(tǒng)的依賴程度越來越高。面對數據豐富而信息匱乏的困境，在統(tǒng)計學、數據庫技術、機器學習、人工智能、模式識別和可視化技術等相關領域發(fā)展的基礎上，以發(fā)現(xiàn)有用知識為目的的新興交叉學科-數據挖掘技術應運而生。
　　關聯(lián)規(guī)則挖掘作為數據挖掘領域重要的研究方向之一，由于其在零售交易分析、客戶關系管理、網絡入侵檢測、設備故障診斷、天文光譜分析、蛋白質結構分析和軟件缺陷發(fā)現(xiàn)等應用領域的廣泛適用性和特

2、有價值，盡管歷經二十多年的發(fā)展，仍然備受企業(yè)和學術界的高度關注，且正在向著新興的研究領域擴展。
　　本文通過對關聯(lián)規(guī)則發(fā)展現(xiàn)狀的系統(tǒng)性研究，選擇了分類數據(Taxonomy)這一特殊領域作為擴展研究對象。這是因為分類數據作為一種結構化的數據不僅普遍存在，而且基于分類數據挖掘產生的關聯(lián)規(guī)則蘊含更豐富、更靈活、更具參考價值的信息，因此該領域的擴展性研究對于實際應用和學術理論都具有非常特殊且重要的意義。
　　本文的主要研究內容如下

3、：
　　首先，本文研究了分類數據關聯(lián)規(guī)則挖掘的特殊情形--多層關聯(lián)規(guī)則挖掘問題，這是基于分類數據擴展性研究的基礎。本文根據挖掘遍歷策略的不同，提出了兩種新穎高效的多層關聯(lián)規(guī)則挖掘方法TD-CBP-MLARM和BU-CBP-MLARM。其基本思想在于，首先利用分類數據所屬領域的先驗知識對通用的相關性度量函數進行有效修正，使之更加適合于分類數據項之間相關性的度量；然后基于修正后的相關性函數對分類數據各層次上的項依次進行聚類，根據各層項

4、的層次聚類結果對事務數據庫進行約簡劃分，從而縮小了事務數據庫的規(guī)模，節(jié)省了挖掘算法掃描事務數據庫的I/O操作時間，達到了提高算法挖掘效率的目的。
　　其次，本文針對多層關聯(lián)規(guī)則挖掘的一般情形--概化關聯(lián)規(guī)則挖掘問題進行了研究。本文首先基于有候選項集方法的思想，提出了一種基于集合枚舉樹的概化頻繁項集寬度優(yōu)先挖掘方法SET-BFS。該方法可以確保所有k-項集產生之前，其所有的(k-1)-子項集已經產生，進而可以確保Apriori性質在

5、分類數據領域的有效運用，實現(xiàn)對非頻繁項集的高效剪枝，不僅避免了大量非頻繁項集的計數和判定操作，還減少項集擴展空間的規(guī)模，從而提升此類算法的執(zhí)行效率。進而結合最新的無候選項集方法的思想，提出了一種高效的概化關聯(lián)規(guī)則挖掘方法GEAOT-tax。該方法引入了一種新穎的擴展升序前綴樹GEAOT，采用自上而下、深度優(yōu)先的遍歷策略，結合雙頭表輔助結構以及合并、剪枝等一系列優(yōu)化操作，進一步減少了算法的遍歷開銷，從而提升了算法整體效率。
　　最后

6、，本文將研究視角從靜態(tài)分類數據進一步擴展至動態(tài)變化環(huán)境下，對概化關聯(lián)規(guī)則更新保持問題進行了研究，并提出了一種基于概化擴展自然序樹的增量挖掘方法GECT-IM。該方法只需掃描一次原始分類事務數據庫，就可以將所有交易中的葉子項及其概化項映射至一棵壓縮格式的自然序前綴樹GECT，并通過引入更新頭表來實現(xiàn)只對GECT中更新項集計數，然后結合相關性質及運算就能發(fā)現(xiàn)大部分更新后的頻繁項集，而只對部分原來非頻繁的項集才需重新遍歷初始GECI、樹來得到