數(shù)據(jù)挖掘概念與技術

PAGE2PAGE5數(shù)據(jù)挖掘概念與技術一.什么是數(shù)據(jù)挖掘，數(shù)據(jù)挖掘的知識體系及應用范圍1.定義：又稱數(shù)據(jù)中的知識發(fā)現(xiàn)，從大量的數(shù)據(jù)中挖掘有趣模式和知識的過程。知識發(fā)現(xiàn)的過程：

1).數(shù)據(jù)清理：除噪聲和刪除不一致數(shù)據(jù)

2).數(shù)據(jù)集成：多種數(shù)據(jù)源的組合

3).數(shù)據(jù)選擇：取和分析與任務相關的數(shù)據(jù)

4).數(shù)據(jù)變換：數(shù)據(jù)變換和統(tǒng)一成適合挖掘的形式

5).數(shù)據(jù)挖掘：使用智能方法提取數(shù)據(jù)格式

6).模式評估：識別代表知識的有趣模式

7).知識表示：使用可視化和知識表示技術，向用戶提供挖掘的知識2.為什么要進行數(shù)據(jù)挖掘

未來將是大數(shù)據(jù)時代，IDC（國際數(shù)據(jù)公司）研究報告指出2012年全球信息資料量為2.8ZB（2的40次方GB）,而在2020年預計會達到40ZB，平均每人擁有5247GB的數(shù)據(jù)。龐大的數(shù)據(jù)量背后隱藏著巨大的潛在價值，人們手握巨量的數(shù)據(jù)卻沒有很好的手段去充分挖掘其中的價值，因此對數(shù)據(jù)挖掘的研究可以幫助我們將數(shù)據(jù)轉化成知識。3.數(shù)據(jù)挖掘的知識體系

數(shù)據(jù)挖掘作為一個應用驅動的領域，吸納了許多應用領域的技術，包括：統(tǒng)計學、機器學習、模式識別、數(shù)據(jù)庫和數(shù)據(jù)倉庫、信息檢索、可視化、算法、高性能計算等。數(shù)據(jù)挖掘的任務分類：描述性任務：刻畫目標數(shù)據(jù)的一般性質預測性任務：歸納及做出預測數(shù)據(jù)挖掘功能：1).數(shù)據(jù)特征化與數(shù)據(jù)區(qū)分2).頻繁模式3).關聯(lián)和相關性挖掘4).分類和回歸5).聚類分析6).離群點分析4.數(shù)據(jù)挖掘應用領域1.金融數(shù)據(jù)分析2.零售與電信業(yè)：例如分析零售數(shù)據(jù)有利于做出正確的決策；產(chǎn)品推薦；顧客保有及促銷策略3.科學與工程數(shù)據(jù)挖掘4.網(wǎng)絡數(shù)據(jù)挖掘：社交網(wǎng)絡用戶行為分析，多媒體、文本和web數(shù)據(jù)分析5.信息檢索：搜索引擎、云計算、數(shù)據(jù)倉庫

二.認識數(shù)據(jù)1.屬性總結：標稱屬性：一些符號和事物的名稱，如頭發(fā)顏色和學歷是描述人的屬性。二元屬性：只有0、1兩種狀態(tài)序數(shù)屬性：可能的值具有有意義的序，如教師職稱數(shù)值屬性：定量的，用實數(shù)值表示2.度量數(shù)據(jù)的相似性和相異性（即數(shù)據(jù)的鄰近性）非對稱二元屬性：Jaccard屬性數(shù)值屬性：歐幾里得距離、曼哈頓距離、閔可夫斯基距離、上確界距離相似性評估：余弦相似性（用于比較文檔）、Tanimoto系數(shù)3.數(shù)據(jù)預處理1).數(shù)據(jù)清理：填補缺失值、光滑噪聲、識別離群點、糾正數(shù)據(jù)不一致性，通常是一個兩步迭代過程，包括偏差檢測盒數(shù)據(jù)變換

處理缺失值：有忽略元組、人工填寫、全局常量填充、

均值或中位數(shù)填充、同類均值或中位數(shù)填充、最可能值填充六種方法。

噪聲數(shù)據(jù)處理：分箱（考察近鄰數(shù)據(jù)值，有箱均值、箱中位數(shù)、箱邊界光滑方法）

回歸、離群點分析2).數(shù)據(jù)集成：將來自多個數(shù)據(jù)源的數(shù)據(jù)整合成一致的數(shù)據(jù)存儲實體識別問題：模式集成和對象匹配。如在一個系統(tǒng)中discount用于訂單，而在另一個系統(tǒng)中用于商品，集成不正確導致商品不正確打折冗余和相關分析：冗余指一個屬性能由另一個或另一組屬性導出，則這個屬性是冗余的，可用相關分析檢測到。標稱數(shù)據(jù)使用卡方檢驗，數(shù)值屬性用相關系數(shù)和協(xié)方差3).數(shù)據(jù)規(guī)約：簡化數(shù)據(jù)集的表示，包括維規(guī)約和數(shù)值規(guī)約維規(guī)約：數(shù)據(jù)壓縮技術（如小波變換和主成分分析），屬性子集選擇，屬性構造數(shù)值規(guī)約：參數(shù)模型（如回歸），非參數(shù)模型（聚類、抽樣、直方圖）4).數(shù)據(jù)變換：將數(shù)據(jù)變換成適于挖掘的形式變換策略包括：光滑，屬性構造，聚集，規(guī)范化，離散化，由標稱數(shù)據(jù)產(chǎn)生概念分層。

2).規(guī)則興趣度的度量：支持度和置信度支持度：兩種商品同時被購買占事務總數(shù)的比例，反映發(fā)現(xiàn)該規(guī)則的有用性置信度：購買一個商品的顧客中同時購買另一個商品的顧客所占比例，反映規(guī)則的確定性。項集：項的集合，如集合{computer，antivirus_software}是一個2項集支持度計數(shù)：項集的事務數(shù)頻繁項集：相對支持度滿足最小支持度閾值的項集閉頻繁項集：項集X在數(shù)據(jù)集D中是閉的，如果不存在真超項集Y使得Y與X在D中具有相同的支持度計數(shù)，如果X在D中是閉的和頻繁的，則X是數(shù)據(jù)集的閉頻繁項集。極大頻繁項集：X是頻繁的，并且不存在超項集Y使得Y在D中是頻繁的。關聯(lián)規(guī)則的挖掘包含兩步：（1）.找出所有的頻繁項集（2）.由頻繁項集產(chǎn)生強關聯(lián)規(guī)則（同時滿足最小支持度閾值和最小置信度閾值的規(guī)則）2.頻繁項集挖掘方法可以分為三類：類Apriori算法，基于頻繁模式增長的算法（如FP-growth算法），使用垂直數(shù)據(jù)格式的算法1).Apriori算法（數(shù)據(jù)挖掘十大經(jīng)典算法）頻繁項集先驗性質：頻繁項集的所有非空子集也一定是頻繁的?；舅枷耄菏褂弥饘铀阉鞯牡椒?，其中k項集用于探索（k+1）項集，使用先驗性質壓縮搜索空間。如何使用L(k-1)找到L(k):通過連接步和剪枝步完成。連接步通過將L(k-1)與自身連接產(chǎn)生候選k項集集合。剪枝步從候選k項集確定L(k)。

提高Apriori算法效率：基于散列的技術：將事務產(chǎn)生的k項集散列到散列表的不同桶中，并增加相應桶計數(shù)，對應桶計數(shù)小于支持度閾值不可能是頻繁的，可以從候選集中刪除。這一技術可以顯著地壓縮需要考察的k項集事務壓縮：不包含任何頻繁k項集的事務不可能包含任何頻繁(k+1)項集，因此在其后的考慮時，可以加上標記或刪除。

劃分：分兩個階段，階段一把D劃分成n個分區(qū)，找出每個分區(qū)的局部頻繁項集，組合所有局部頻繁項集形成候選項集；階段二評估每個候選的實際支持度，找出候選項集中的全局頻繁項集。整個過程只需要兩次數(shù)據(jù)庫掃描。

抽樣：基本思想是選取數(shù)據(jù)庫D的隨機樣本S，然后再S中搜索頻繁項集。這種方法犧牲了一些精度換取了有效性，可能會丟失一些全局頻繁項集

動態(tài)項集計數(shù)：基本思想是獎數(shù)據(jù)庫劃分為用開始點標記的塊。不像Apriori算法僅在每次完整的數(shù)據(jù)庫掃描前確定新的候選，這種變形中，可以再任何開始點添加新的候選集。該變形需要的數(shù)據(jù)庫掃描筆Apriori算法少。Apriori算法優(yōu)缺點優(yōu)點：顯著壓縮了候選項集的規(guī)模，產(chǎn)生很好的性能缺點：仍需要產(chǎn)生大量候選項集，需要重復掃描整個數(shù)據(jù)庫2).頻繁模式增長（FP-growth）目標：挖掘全部頻繁項集而無需代價昂貴的候選產(chǎn)生過程基本思想：采取分治策略，首先將頻繁項集的數(shù)據(jù)庫壓縮到一棵頻繁模式樹（FP樹），該樹仍保留項集的關聯(lián)信息。然后把壓縮后的數(shù)據(jù)庫劃分成一組條件數(shù)據(jù)庫，每個數(shù)據(jù)庫關聯(lián)一個頻繁項或模式段，并分別挖掘每個條件數(shù)據(jù)庫。隨著被考察模式的增長，這種方法顯著地壓縮被搜索的數(shù)據(jù)集的大小。概括起來可分為構造FP樹和挖掘FP樹兩個步驟。當數(shù)據(jù)庫很大時，構造的FP數(shù)可能太大而不能放進主存，可以遞歸地將數(shù)據(jù)庫劃分成投影數(shù)據(jù)庫集合。FP-growth方法對于挖掘長的頻繁模式和短的頻繁模式，都是有效的和可伸縮的，并且大約比Apriori算法快一個數(shù)量級。3).使用垂直數(shù)據(jù)格式挖掘頻繁項集Apriori算法和FP-growth算法都是使用水平數(shù)據(jù)格式，即{TID:itemset}，其中TID為事務標識符，itemset是TID中購買的商品。垂直數(shù)據(jù)格式：{item:TID}基本思想：通過掃描一次數(shù)據(jù)庫，把水平格式的數(shù)據(jù)轉換成垂直格式，根據(jù)先驗性質，使用頻繁k項集來構造候選k+1項集，通過去頻繁k項集的TID集的交，計算對應k+1項集的TID集，重復該過程，知道不能找到頻繁項集或候選項集。優(yōu)點：利用先驗性質，不需要掃描數(shù)據(jù)庫來確定k+1項集的支持度。缺點：TID集可能很長，需要大量內存，長集合的交運算還需要大量的計算時間。3.模式評估并非所有強關聯(lián)規(guī)則都是有趣的，比如項集計算機游戲和錄像可能滿足強關聯(lián)規(guī)則，但是它們是負相關的。提升度：一種相關性的度量，結果值大于1是正相關，為1表示獨立，小于1表示負相關。相關性度量還有最大置信度和余弦。

五.挖掘頻繁模式、關聯(lián)和相關性1.高級模式形式：多層關聯(lián)、多維關聯(lián)、量化關聯(lián)規(guī)則、稀有模式、負模式2.基于約束的挖掘：模式剪枝約束、數(shù)據(jù)剪枝約束模式搜索空間剪枝：檢查候選模式，使用先驗性質，剪掉一個模式，如果它的超模式都不可能產(chǎn)生。數(shù)據(jù)搜索空間剪枝：檢查數(shù)據(jù)集，判斷特定數(shù)據(jù)片段是否對其后的可滿足模式產(chǎn)生有貢獻。

模式剪枝約束分為五類：反單調的：如果一個項集不滿足規(guī)則約束，則它的任何超集不可能滿足該約束單調的：如果一個項集滿足這個規(guī)則約束，則它的所有超集也滿足。簡潔的：可以枚舉并且僅枚舉可以確保該約束的所有集合，該類約束不必迭代檢驗可轉變的：不屬于以上三類，但該約束在項集一特定次序排列時可能成為單調的或反單調的。不可轉變的：大部分都屬于以上四類。3.挖掘高維數(shù)據(jù)和巨型模式：包括利用垂直數(shù)據(jù)格式擴充模式增長方法和模式融合方法。垂直數(shù)據(jù)格式模式增長：將具有較少行但具有大量維的數(shù)據(jù)集變換成具有大量航少量維的數(shù)據(jù)集。模式融合：基本思想：融合少量較短的頻繁模式，形成巨型模式候選。首先，他以有限的寬度遍歷樹，只使用有限大小的候選池中的模式作為模式樹向下搜索的開始結點，避免了指數(shù)搜索空間問題。它產(chǎn)生巨型模式的近似解，可以找出大部分巨型模式。步驟：1.池初始化：一個短長度（長度不超過3）頻繁模式的完全集。

2.迭代的模式融合：從當前池中隨機選取k個種子，對每個種子找出直徑為T的球內所有模式，將這些球融合成超模式集。由于每個超模式的支集隨迭代而收縮，因此迭代過程終止。模式融合合并打魔石的小的子模式，而不是用單個項增量地擴展模式。

4.挖掘壓縮或近似模式：1.基于聚類的壓縮：采用一個好的相似性度量，把相似的對象聚合到一個簇中，代表模式從每個簇中選取，從而提供頻繁模式集的一個壓縮版本。模式距離：閉模式之間的距離度量。