加權頻繁模式挖掘算法研究.pdf

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

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

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

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

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

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

7、挖掘IWFTPM問題，提出了加權遍歷模式間的一種新穎特性——可拓展特性，把對候選模式的剪枝問題轉化為判斷候選模式的可擴展性問題?；诩訖嗄Ｊ铰劦目赏卣固匦裕岢隽艘环N基于加權有向圖結構的頻繁遍歷模式挖掘算法——WFTPMiner(Weighted Frequent Traversal PatternMiner)算法，并提出了實現(xiàn)該算法的兩種策略——EGTG(Evaluated by Global Topology of Graph)策略

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

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

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

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

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