加權(quán)頻繁模式挖掘算法研究.pdf

1、隨著信息技術(shù)尤其是網(wǎng)絡(luò)技術(shù)的快速發(fā)展，人們收集、存儲(chǔ)和傳輸數(shù)據(jù)的能力不斷提高，各類應(yīng)用領(lǐng)域的數(shù)據(jù)量大量產(chǎn)生，數(shù)據(jù)挖掘日益成為數(shù)據(jù)分析和決策支持的一種重要工具。頻繁模式挖掘是數(shù)據(jù)挖掘領(lǐng)域內(nèi)的一個(gè)基本問(wèn)題，它被廣泛應(yīng)用到多種領(lǐng)域和挖掘任務(wù)中，例如Web挖掘、零售業(yè)數(shù)據(jù)挖掘、科學(xué)研究、關(guān)聯(lián)規(guī)則挖掘、序列模式挖掘、路徑分析等。
　　 在傳統(tǒng)的頻繁模式挖掘方法中，事務(wù)數(shù)據(jù)庫(kù)(Transaction Database.TDB)中的每個(gè)項(xiàng)都被

2、看成是同等重要的，而在實(shí)際應(yīng)用中，每個(gè)項(xiàng)通常具有不同的重要性。為解決這個(gè)問(wèn)題，本文研究了加權(quán)頻繁模式挖掘(Weighted Frequent Pattern Mining，WFPM)問(wèn)題，其主要特征就是在挖掘過(guò)程中通過(guò)給TDB中各個(gè)項(xiàng)目賦予不同的權(quán)值來(lái)體現(xiàn)它們的重要性不同。經(jīng)過(guò)十幾年的研究，已經(jīng)奠定了較成熟的頻繁模式挖掘算法理論基礎(chǔ)，但對(duì)于加權(quán)頻繁模式挖掘算法及其應(yīng)用的研究工作尚處在初始階段，值得深入研究和探討。在加權(quán)事例中，加權(quán)支持度

3、度量不再滿足向下閉合特性(亦稱反單調(diào)性(Antimonotonicity))，傳統(tǒng)的頻繁模式挖掘算法已經(jīng)不再適用，因此在加權(quán)頻繁模式算法中，研究的主要關(guān)注點(diǎn)是如何使加權(quán)支持度或興趣度度量滿足向下閉合特性(Downward Closure Prop-erty)，以便高效地剪枝搜索空間。本文主要以基于Web頻繁遍歷路徑模式挖掘和零售業(yè)數(shù)據(jù)挖掘?yàn)閷?shí)例，詳細(xì)闡述了基于加權(quán)有向圖(Weighted Directed Graph，WDG)的加權(quán)頻繁

4、遍歷模式挖掘和加權(quán)強(qiáng)相關(guān)頻繁模式挖掘的有關(guān)思想。
　　 圖遍歷模式挖掘一直是數(shù)據(jù)挖掘研究的熱點(diǎn)之一，圖及其遍歷可廣泛地模擬現(xiàn)實(shí)世界的多種數(shù)據(jù)訪問(wèn)形式，比較有代表性的實(shí)例就是Web路徑訪問(wèn).Web結(jié)構(gòu)可被抽象為一個(gè)加權(quán)有向圖：頂點(diǎn)代表網(wǎng)頁(yè)或站點(diǎn)，有向邊代表網(wǎng)頁(yè)間的網(wǎng)頁(yè)或站點(diǎn)間的超級(jí)鏈接，權(quán)值代表Web結(jié)構(gòu)元素的不同重要性，然而傳統(tǒng)的遍歷模式挖掘算法僅僅考慮了非加權(quán)的遍歷模式挖掘。為解決加權(quán)遍歷模式挖掘問(wèn)題，本文主要從以下幾個(gè)方面做

5、了深入研究：
　　 歸納了加權(quán)頻繁遍歷模式挖掘(Weighted Frequent Traversal Pattern Mining，WFTPM)的種類，將Web加權(quán)頻繁遍歷模式挖掘，從用戶類型角度分為個(gè)體加權(quán)頻繁遍歷模式挖掘(IndividualWFTPM，IWFTPM)和整體加權(quán)頻繁遍歷模式挖掘(Holistic WFTPM，HWFTPM)；從采取的挖掘方法角度分為普通遍歷模式挖掘和序列遍歷模式挖掘。
　　 提出了加

6、權(quán)有向圖模型，總結(jié)了加權(quán)有向圖的種類，提出了兩類加權(quán)有向圖——頂點(diǎn)加權(quán)有向圖(Vertex-Weighted Directed Graph， VWDG)和邊加權(quán)有向圖(Edge-Weighted Directed Graph，EWDG)，并詳細(xì)闡述了兩類WDG間的轉(zhuǎn)換方法，簡(jiǎn)化了基于加權(quán)有向圖的頻繁遍歷模式挖掘問(wèn)題，完善了基于圖遍歷的模式挖掘問(wèn)題的理論基礎(chǔ)。
　　 基于加權(quán)有向圖模型，本文做了以下幾方面工作。
　　 針對(duì)

7、挖掘IWFTPM問(wèn)題，提出了加權(quán)遍歷模式間的一種新穎特性——可拓展特性，把對(duì)候選模式的剪枝問(wèn)題轉(zhuǎn)化為判斷候選模式的可擴(kuò)展性問(wèn)題。基于加權(quán)模式聞的可拓展特性，提出了一種基于加權(quán)有向圖結(jié)構(gòu)的頻繁遍歷模式挖掘算法——WFTPMiner(Weighted Frequent Traversal PatternMiner)算法，并提出了實(shí)現(xiàn)該算法的兩種策略——EGTG(Evaluated by Global Topology of Graph)策略

8、和ELTG( Evaluated by Local Topology of Graph)策略。
　　 當(dāng)最小支持度閾值較小時(shí)，用算法WFTPMiner挖掘加權(quán)頻繁模式將導(dǎo)致效率低下，為克服以上不足，提出了一種修訂的加權(quán)支持度表示法，然后利用加權(quán)FP-tree模式增長(zhǎng)方法，提出了兩種高效的基于加權(quán)有向圖的頻繁遍歷模式挖掘算法：CWFTPMiner(Closed Weighted Frequent TraversalPattern

9、Miner)和WTMaxMiner(Weighted Traversal-based Maximal frequent pattern Miner)，前者用于挖掘閉合加權(quán)頻繁遍歷模式，后者用于挖掘最大加權(quán)頻繁遍歷模式。此外，在實(shí)現(xiàn)這兩種算法的過(guò)程中，詳細(xì)分析了閉合約束和加權(quán)約束的不同結(jié)合順序可能造成的信息丟失現(xiàn)象，提出了兩種約束的正確結(jié)合順序。
　　 針對(duì)加權(quán)FP-tree模式增長(zhǎng)算法的弊端和遍歷路徑中相關(guān)項(xiàng)目的連續(xù)性特點(diǎn)，把遍

10、歷模式看作是序列模式，提出了一種基于圖遍歷的加權(quán)序列模式挖掘算法WTSPMiner(Weighted Traversal-basedSequential Pattern Miner)，該算法采用一種改進(jìn)的加權(quán)前綴投影模式增長(zhǎng)方法，運(yùn)用分而治之策略，把挖掘原來(lái)加權(quán)序列數(shù)據(jù)庫(kù)的任務(wù)分解成一組挖掘局部加權(quán)投影數(shù)據(jù)庫(kù)的小任務(wù)，通過(guò)將加權(quán)約束添加到挖掘過(guò)程中，實(shí)現(xiàn)加權(quán)頻繁序列遍歷模式的挖掘。
　　 為解決HWFTP挖掘問(wèn)題，提出了一種挖掘

11、基于統(tǒng)計(jì)理論的加權(quán)頻繁遍歷模式挖掘算法SWFTPMiner(Statistical theory-based Weighted Frequent Traversal Pattern Miner)，該算法利用統(tǒng)計(jì)理論中的置信度概念，首先清除掉原始遍歷數(shù)據(jù)庫(kù)T中帶有噪聲權(quán)值的“異常點(diǎn)”(Outlier)，從而得到能反映整體絕大多數(shù)用戶遍歷行為的修訂加權(quán)有向圖Gr及遍歷數(shù)據(jù)庫(kù)Tr，然后具體提出了兩種從修訂的Tr中挖掘WFTPs的策略方法——逐

12、層挖掘策略和分而治之挖掘策略。
　　 此外，本文以零售業(yè)為例，提出了一種加權(quán)強(qiáng)相關(guān)頻繁模式挖掘算法WHFPMiner(WeightedHighly-correlated Frequent Pattern Miner)，在算法中，提出了一種新的目標(biāo)興趣度度量標(biāo)準(zhǔn)——加權(quán)h-置信度，通過(guò)采用修訂的加權(quán)支持度，證明了加權(quán)h-置信度具有反單調(diào)性和交叉加權(quán)支持性，最終基于加權(quán)FP-tree模式增長(zhǎng)方法，利用加權(quán)h-置信度的兩種特性快速地挖