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

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

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

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

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

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

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

6).模式評(píng)估：識(shí)別代表知識(shí)的有趣模式

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.迭代的模式融合：從當(dāng)前池中隨機(jī)選取k個(gè)種子，對(duì)每個(gè)種子找出直徑為T的球內(nèi)所有模式，將這些球融合成超模式集。由于每個(gè)超模式的支集隨迭代而收縮，因此迭代過程終止。模式融合合并打魔石的小的子模式，而不是用單個(gè)項(xiàng)增量地?cái)U(kuò)展模式。

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