數(shù)據(jù)挖掘概念復(fù)習(xí)

1、數(shù)據(jù)挖掘：是從大量數(shù)據(jù)中發(fā)現(xiàn)有趣（非平凡的、隱含的、先前未知、潛在有用）模式，這些數(shù)據(jù)可以存放在數(shù)據(jù)庫(kù)，數(shù)據(jù)倉(cāng)庫(kù)或其他信息存儲(chǔ)中。挖掘流程：(1)學(xué)習(xí)應(yīng)用域（2）目標(biāo)數(shù)據(jù)創(chuàng)建集（3）數(shù)據(jù)清洗和預(yù)處理（4）數(shù)據(jù)規(guī)約和轉(zhuǎn)換（5）選擇數(shù)據(jù)挖掘函數(shù)（總結(jié)、分類(lèi)、回歸、關(guān)聯(lián)、分類(lèi)）（6）選擇挖掘算法（7）找尋興趣度模式（8）模式評(píng)估和知識(shí)展示（9）使用挖掘的知識(shí)概念/類(lèi)描述：一種數(shù)據(jù)泛化形式，用匯總的、簡(jiǎn)潔的和精確的方法描述各個(gè)類(lèi)和概念，通過(guò)（1）數(shù)據(jù)特征化：目標(biāo)類(lèi)數(shù)據(jù)的一般特性或特征的匯總；（2）數(shù)據(jù)區(qū)分：將目標(biāo)類(lèi)數(shù)據(jù)的一般特性與一個(gè)或多個(gè)可比較類(lèi)進(jìn)行比較；（3）數(shù)據(jù)特征化和比較來(lái)得到。關(guān)聯(lián)分析：發(fā)現(xiàn)

2、關(guān)聯(lián)規(guī)則，這些規(guī)則展示屬性-值頻繁地在給定數(shù)據(jù)集中一起出現(xiàn)的條件，通常要滿(mǎn)足最小支持度閾值和最小置信度閾值。分類(lèi)：找出能夠描述和區(qū)分?jǐn)?shù)據(jù)類(lèi)或概念的模型，以便能夠使用模型預(yù)測(cè)類(lèi)標(biāo)號(hào)未知的對(duì)象類(lèi)，導(dǎo)出的模型是基于訓(xùn)練集的分析。導(dǎo)出模型的算法：決策樹(shù)、神經(jīng)網(wǎng)絡(luò)、貝葉斯、（遺傳、粗糙集、模糊集）。預(yù)測(cè)：建立連續(xù)值函數(shù)模型，預(yù)測(cè)空缺的或不知道的數(shù)值數(shù)據(jù)集。孤立點(diǎn)：與數(shù)據(jù)的一般行為或模型不一致的數(shù)據(jù)對(duì)象。聚類(lèi)：分析數(shù)據(jù)對(duì)象，而不考慮已知的類(lèi)標(biāo)記。訓(xùn)練數(shù)據(jù)中不提供類(lèi)標(biāo)記，對(duì)象根據(jù)最大化類(lèi)內(nèi)的相似性和最小化類(lèi)間的原則進(jìn)行聚類(lèi)或分組，從而產(chǎn)生類(lèi)標(biāo)號(hào)。第二章數(shù)據(jù)倉(cāng)庫(kù)數(shù)據(jù)倉(cāng)庫(kù)是一個(gè)面向主題的、集成的、時(shí)變的、非易失

3、的數(shù)據(jù)集合，支持管理部門(mén)的決策過(guò)程。從一個(gè)或多個(gè)數(shù)據(jù)源收集信息，存放在一個(gè)一致的模式下，并且通常駐留在單個(gè)站點(diǎn)。數(shù)據(jù)倉(cāng)庫(kù)通過(guò)數(shù)據(jù)清理、變換、繼承、裝入和定期刷新過(guò)程來(lái)構(gòu)造。 面向主題：排除無(wú)用數(shù)據(jù)，提供特定主題的簡(jiǎn)明視圖。集成的：多個(gè)異構(gòu)數(shù)據(jù)源。時(shí)變的：從歷史角度提供信息，隱含時(shí)間信息。非易失的：和操作數(shù)據(jù)的分離，只提供初始裝入和訪(fǎng)問(wèn)。聯(lián)機(jī)事務(wù)處理OLTP：主要任務(wù)是執(zhí)行聯(lián)機(jī)事務(wù)和查詢(xún)處理。聯(lián)系分析處理OLAP：數(shù)據(jù)倉(cāng)庫(kù)系統(tǒng)在數(shù)據(jù)分析和決策方面為用戶(hù)或知識(shí)工人提供服務(wù)。這種系統(tǒng)可以用不同的格式和組織提供數(shù)據(jù)。OLAP是一種分析技術(shù)，具有匯總、合并和聚集功能，以及從不同的角度觀(guān)察信息的能力。特征

4、特征面向用戶(hù)功能DB數(shù)據(jù)訪(fǎng)問(wèn)OLTP操作處理事務(wù)DBA，辦事員日常操作基于ER當(dāng)前最新讀/寫(xiě)OLAP信息處理分析知識(shí)工人決策支持星型，雪花時(shí)間跨度讀特征匯總用戶(hù)操作訪(fǎng)問(wèn)記錄優(yōu)先DB規(guī)模度量OLTP原始，詳細(xì)數(shù)千主碼索引數(shù)十個(gè)高性能可用100mb-gb事務(wù)OLAP匯總，統(tǒng)一數(shù)百大量掃描數(shù)百萬(wàn)高靈活100gb-tb查詢(xún) 多維數(shù)據(jù)模型:多維數(shù)據(jù)模型將數(shù)據(jù)看作數(shù)據(jù)立方體，允許從多個(gè)維度對(duì)數(shù)據(jù)建模和觀(guān)察。包含維表和事實(shí)表。最流行的數(shù)據(jù)倉(cāng)庫(kù)數(shù)據(jù)模型是多維數(shù)據(jù)模型，這種模型可以是星形模式（事實(shí)表在中間，連接到多個(gè)維表）、雪花模式（星型的變種，某些維表規(guī)范化，分解到附加維表，以減少冗余）、事實(shí)星座模式（多個(gè)事

5、實(shí)表共享維表）。數(shù)據(jù)立方體：允許從多維對(duì)數(shù)據(jù)建模和觀(guān)察。它由維和事實(shí)定義。維：關(guān)于一個(gè)組織想要保存記錄的透視圖和實(shí)體，每個(gè)維都有一個(gè)表與之相關(guān)聯(lián)，成為維表。事實(shí)表：包括事實(shí)的名稱(chēng)和度量，以及每個(gè)相關(guān)維表的碼。方體Cuboid：每個(gè)數(shù)據(jù)立方體?；痉襟wBase Cuboid：存放最底層匯總。頂點(diǎn)方體Apex Cuboid：最高層匯總，all。數(shù)據(jù)立方體Data Cube：給定維的集合，可以對(duì)維的每個(gè)可能子集產(chǎn)生一個(gè)方體。結(jié)果成為方體的格。多維數(shù)據(jù)立方體：提供數(shù)據(jù)的多維視圖，并允許預(yù)計(jì)算和快速訪(fǎng)問(wèn)匯總數(shù)據(jù)。度量：數(shù)值函數(shù)，通過(guò)對(duì)給定點(diǎn)的各維-值對(duì)聚集數(shù)據(jù)，計(jì)算該點(diǎn)的度量值。概念分層：映射序列，將底

6、層概念映射到更一般的較高層概念。OLAP操作:上卷：上卷操作通過(guò)一個(gè)維的概念分層向上攀升或者通過(guò)維規(guī)約，在數(shù)據(jù)立方體上進(jìn)行聚集。下鉆：下鉆是上卷的逆操作，它由不太詳細(xì)的數(shù)據(jù)到更詳細(xì)的數(shù)據(jù)。切片和切塊：切片對(duì)一個(gè)維進(jìn)行選擇。切塊對(duì)兩個(gè)以上維進(jìn)行選擇，定義子立方體。轉(zhuǎn)軸：可視化操作，轉(zhuǎn)動(dòng)視角。鉆過(guò)：跨越多個(gè)事實(shí)表。鉆透：鉆到后端關(guān)系表。數(shù)據(jù)倉(cāng)庫(kù)模型的不同類(lèi)型：1、企業(yè)倉(cāng)庫(kù)：收集了關(guān)于跨部門(mén)的整個(gè)組織主題的所有信息，跨越整個(gè)組織，因此是企業(yè)范圍的。2、數(shù)據(jù)集市：是企業(yè)倉(cāng)庫(kù)的一個(gè)部門(mén)子集，它針對(duì)選定的主題，對(duì)于特定的用戶(hù)是有用的，因此是部門(mén)范圍的，其數(shù)據(jù)通常是匯總的。3、虛擬倉(cāng)庫(kù)：虛擬倉(cāng)庫(kù)是操作數(shù)據(jù)庫(kù)

7、上視圖的集合，易于建立，但需要操作數(shù)據(jù)庫(kù)服務(wù)器具有剩余能力。數(shù)據(jù)倉(cāng)庫(kù)的三層結(jié)構(gòu)：1、倉(cāng)庫(kù)數(shù)據(jù)服務(wù)器：使用后端工具（抽取、清晰、轉(zhuǎn)換、裝載、刷新）和實(shí)用程序由操作數(shù)據(jù)庫(kù)和其他外部數(shù)據(jù)源提取數(shù)據(jù)，進(jìn)行數(shù)據(jù)清理和變換并放入倉(cāng)庫(kù)底層2、OLAP服務(wù)器：直接實(shí)現(xiàn)對(duì)多維數(shù)據(jù)的操作,直接為商務(wù)用戶(hù)提供來(lái)自數(shù)據(jù)倉(cāng)庫(kù)或數(shù)據(jù)集市的多維數(shù)據(jù)。ROLAP:多維數(shù)據(jù)操作映射到標(biāo)準(zhǔn)關(guān)系操作。MOLAP：多維數(shù)據(jù)視圖映射到數(shù)組中.HOLAP:結(jié)合，歷史數(shù)據(jù)ROLAP,頻繁訪(fǎng)問(wèn)數(shù)據(jù)放到MOLAP.3、前端客戶(hù)層：包括查詢(xún)和報(bào)表工具、分析工具或數(shù)據(jù)挖掘工具。數(shù)據(jù)倉(cāng)庫(kù)的設(shè)計(jì)：1、分析建立企業(yè)模型并映射到數(shù)據(jù)倉(cāng)庫(kù)概念模型；2、邏輯

8、模型的設(shè)計(jì)3、物理模型的設(shè)計(jì)OLAP建模：維表設(shè)計(jì)（維的變化，維表的共享，層次信息和分類(lèi)信息的位置）、事實(shí)表設(shè)計(jì)（事實(shí)表的特性，通用數(shù)據(jù)和專(zhuān)用數(shù)據(jù)事實(shí)表）邏輯模型設(shè)計(jì)：1、 系統(tǒng)數(shù)據(jù)量估算；2、 數(shù)據(jù)粒度的選擇；3、 數(shù)據(jù)的分割（到各自的物理單元單獨(dú)處理）4、 表的合理劃分（字段的更新頻率和訪(fǎng)問(wèn)頻率不一樣穩(wěn)定性）5、 刪除純操作數(shù)據(jù)（“收款人”），增加導(dǎo)出字段（“銷(xiāo)售總量”）元數(shù)據(jù)：描述數(shù)據(jù)的數(shù)據(jù)，定義數(shù)據(jù)倉(cāng)庫(kù)對(duì)象的數(shù)據(jù)。包括數(shù)據(jù)倉(cāng)庫(kù)的結(jié)構(gòu)、操作元數(shù)據(jù)（數(shù)據(jù)血統(tǒng)、流通，監(jiān)控信息）、用于匯總的算法、從操作環(huán)境到數(shù)據(jù)倉(cāng)庫(kù)的映射；關(guān)于系統(tǒng)性能的數(shù)據(jù)、商務(wù)元數(shù)據(jù)。部分物化：選擇性預(yù)計(jì)算各種方體子集或子

9、立方體。冰山立方體：是一個(gè)數(shù)據(jù)立方體，只存放聚集值大于某個(gè)最小支持度閾值的立方體單元。數(shù)據(jù)立方體計(jì)算中多路數(shù)組聚集，多路計(jì)算BUC：bottom-up computation 自底向上構(gòu)造，一種計(jì)算稀疏冰山立方體的算法。數(shù)據(jù)立方體允許以多維數(shù)據(jù)建模和觀(guān)察，它由維和事實(shí)定義。維是關(guān)于一個(gè)組織想要記錄的透視或?qū)嶓w，事實(shí)是數(shù)值度量的。物理模型的設(shè)計(jì)：1.確定數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（并行RAID）2.索引策略（位圖索引、連接索引）3.數(shù)據(jù)存儲(chǔ)策略與性能優(yōu)化（多路聚集優(yōu)化、表的歸并、分割表的存放、按列存儲(chǔ)、存儲(chǔ)分配優(yōu)化）4.數(shù)據(jù)裝載接口5.并行優(yōu)化設(shè)計(jì)位圖索引：在給定屬性的位圖索引中，屬性的每一個(gè)值v都有一個(gè)位

10、向量，長(zhǎng)度為記錄的總數(shù)，如果數(shù)據(jù)表中給定行上該屬性的值為v, 則在位圖索引的對(duì)應(yīng)行上標(biāo)注該值的位為1，其余為0.，不適用于基數(shù)很大的屬性。連接索引：傳統(tǒng)的索引將給定列上的值映射到具有該值的行的列表上，連接索引登記來(lái)自關(guān)系數(shù)據(jù)庫(kù)的兩個(gè)關(guān)系的可連接行，對(duì)于維護(hù)來(lái)自可連接的關(guān)系的外碼和與之匹配的主碼的聯(lián)系特別有用（事實(shí)表維表）。N維，且每個(gè)維有Li概念封層，可得到的立方體有多路數(shù)組聚集：是數(shù)據(jù)立方體的高效計(jì)算方式。使用多維數(shù)組作為基本數(shù)據(jù)結(jié)構(gòu)，自底向上的、共享地計(jì)算完全數(shù)據(jù)立方體。使用數(shù)組直接尋址的典型MOLAP。方法：最大維在形成單塊的平面上。最小為在形成單面的平面上，每個(gè)平面必須被排序，并按大小

11、遞增的順序被計(jì)算。數(shù)據(jù)預(yù)處理數(shù)據(jù)預(yù)處理：不完整的、含噪音的、不一致的1、數(shù)據(jù)清洗（缺失值（缺少屬性值或某些感興趣的屬性，或僅包含聚集數(shù)據(jù)）、噪聲（錯(cuò)誤或存在偏離期望的離群值）、非一致）、2、數(shù)據(jù)集成（模式集成（識(shí)別實(shí)體）、發(fā)現(xiàn)冗余（相關(guān)分析檢測(cè)）、數(shù)據(jù)值沖突檢測(cè)和處理（不同數(shù)據(jù)源屬性值不同）、3、數(shù)據(jù)變換（光滑（去掉噪聲）、聚集（數(shù)據(jù)匯總）、泛化（概念分層，高層替換低層）、規(guī)范化（按比例縮放）、屬性構(gòu)造）4、數(shù)據(jù)規(guī)約（數(shù)據(jù)立方體聚集、維度規(guī)約(屬性子集選擇)、數(shù)值規(guī)約、離散化和概念分層產(chǎn)生）、5、數(shù)據(jù)離散化（數(shù)值數(shù)據(jù)：分箱、直方圖、聚類(lèi)、基于熵的離散化、基于直觀(guān)劃分離散化3-4-5規(guī)則（區(qū)間的

12、最高有效位的取值個(gè)數(shù)）；分類(lèi)數(shù)據(jù)：用戶(hù)或?qū)＜以谀Ｊ郊?jí)顯示說(shuō)明屬性偏序、通過(guò)顯示數(shù)據(jù)分組說(shuō)明分層結(jié)構(gòu)的一部分、說(shuō)明屬性集但不說(shuō)明偏序（層次高，屬性值個(gè)數(shù)越少）、只說(shuō)明部分屬性集（嵌入數(shù)據(jù)語(yǔ)義，是語(yǔ)義相關(guān)的屬性集捆綁在一起）。噪聲：被測(cè)量的變量的隨機(jī)誤差或方差。噪音數(shù)據(jù)處理：分箱（按箱平均值平滑、按箱中值平滑、按箱邊界平滑）、回歸、聚類(lèi)。規(guī)范化：最小-最大規(guī)范化；Z-score規(guī)范化；小數(shù)定標(biāo)規(guī)范化數(shù)據(jù)規(guī)約技術(shù)：得到數(shù)據(jù)集的規(guī)約顯示，小得多，但保持原數(shù)據(jù)的完整性。挖掘更有效。屬性子集選擇：檢測(cè)并刪除不相關(guān)、弱相關(guān)或冗余的屬性和維維規(guī)約：使用編碼機(jī)制減小數(shù)據(jù)集的規(guī)模,如壓縮。數(shù)值規(guī)約：用替代的、較小

13、的數(shù)據(jù)表示替換或估計(jì)數(shù)據(jù)，如參數(shù)模型or非參方法（聚類(lèi)、抽樣、直方圖（Equi-depth、equi-width、v-optimal（最小方差）、maxdiff（考慮每對(duì)相鄰的之間的差，桶的邊界具有<桶數(shù)-1 >的最大對(duì)）。概念分層：對(duì)一個(gè)屬性遞歸地進(jìn)行離散化，產(chǎn)生屬性值的分層或多分辨率劃分。屬性的原始數(shù)據(jù)用更高層或離散化的值替換。離散化：用少數(shù)區(qū)間標(biāo)記替換連續(xù)屬性的數(shù)值，從而減少和簡(jiǎn)化原來(lái)的數(shù)據(jù)。特征化和區(qū)分：描述性數(shù)據(jù)挖掘：以簡(jiǎn)潔概要的方式描述概念或數(shù)據(jù)集，并提供數(shù)據(jù)的有趣的一般性質(zhì)。預(yù)測(cè)性數(shù)據(jù)挖掘：分析數(shù)據(jù)，建立一個(gè)或一組連續(xù)值函數(shù)模型，預(yù)測(cè)不知道的數(shù)值數(shù)據(jù)值。概念描述包括特

14、征化和區(qū)分。特征化：提供給定數(shù)據(jù)匯集的簡(jiǎn)潔匯總。區(qū)分：提供兩個(gè)或多個(gè)數(shù)據(jù)集的比較描述。OLAP VS 概念描述：處理類(lèi)型、自動(dòng)化方面比較各自?xún)?yōu)缺點(diǎn)。· Concept description: u can handle complex data types of the attributes and their aggregationsu a more automated process· OLAP: u restricted to a small number of dimension and measure typesu user-controlled process決

15、策樹(shù)：一種類(lèi)似于流程圖的樹(shù)結(jié)構(gòu)，其中每個(gè)結(jié)點(diǎn)代表在一個(gè)屬性值上的測(cè)試，每個(gè)分支代表測(cè)試的一個(gè)輸出，而樹(shù)葉代表類(lèi)或類(lèi)分布。數(shù)據(jù)泛化：將數(shù)據(jù)庫(kù)中的大量任務(wù)相關(guān)數(shù)據(jù)從低概念層提升到更高概念層的過(guò)程。數(shù)據(jù)泛化途徑：1、數(shù)據(jù)立方體（OLAP途徑）2、面向?qū)傩缘臍w納面向?qū)傩缘臍w納：1、使用數(shù)據(jù)庫(kù)查詢(xún)收集任務(wù)相關(guān)的數(shù)據(jù)；2、考察相關(guān)任務(wù)集中的各個(gè)屬性并進(jìn)行泛化：通過(guò)屬性刪除（兩種情況）或者屬性泛化3、通過(guò)合并相等的廣義元組（每個(gè)廣義元組代表一個(gè)規(guī)則析?。┎⒗塾?jì)對(duì)應(yīng)的計(jì)數(shù)值進(jìn)行聚集面向?qū)傩詺w納方法產(chǎn)生的泛化描述表現(xiàn)形式：廣義關(guān)系（表）、交叉表、圖、量化特征規(guī)則。屬性泛化控制：屬性泛化閾值控制（對(duì)所有的屬性設(shè)置

16、一個(gè)泛化閾值，或者對(duì)每個(gè)屬性設(shè)置一個(gè)閾值。如果屬性的不同值個(gè)數(shù)大于屬性泛化閾值，則應(yīng)當(dāng)進(jìn)行進(jìn)一步的屬性刪除或?qū)傩苑夯V義關(guān)系閾值控制：為廣義關(guān)系設(shè)置一個(gè)閾值。如果廣義關(guān)系中不同元組的個(gè)數(shù)超過(guò)該閾值，則當(dāng)進(jìn)一步泛化；否則，不再進(jìn)一步泛化。特征化 VS OLAP: 相同點(diǎn)：在不同抽象層次數(shù)據(jù)匯總展示；迭代的上卷、下鉆、旋轉(zhuǎn)、切片/塊。不同點(diǎn)：特征化：自動(dòng)產(chǎn)生層次的分配；多個(gè)相關(guān)維時(shí)進(jìn)行維的相關(guān)分析和排序；維和度量的類(lèi)型可以很復(fù)雜量化規(guī)則：帶有量化信息的邏輯規(guī)則解析特征化：1、收集任務(wù)相關(guān)數(shù)據(jù)2、根據(jù)屬性分析閾值分析泛化（對(duì)目標(biāo)類(lèi)和對(duì)比類(lèi)的候選關(guān)系）：屬性刪除、屬性泛化、候選關(guān)系3、屬性的相關(guān)性分

17、析（信息增益）4、（去除不/弱相關(guān)，對(duì)比類(lèi)的候選關(guān)系）形成目標(biāo)類(lèi)的初始工作關(guān)系5、在初始工作關(guān)系上根據(jù)屬性泛化閾值使用面向?qū)傩缘臍w納類(lèi)對(duì)比：1、通過(guò)查詢(xún)處理收集數(shù)據(jù)庫(kù)中的相關(guān)數(shù)據(jù)集，并分別劃分成目標(biāo)類(lèi)和一個(gè)或多個(gè)對(duì)比類(lèi)。2、維相關(guān)分析（僅選擇高度相關(guān)的維進(jìn)一步分析，屬性移除和泛化）3、同步泛化（目標(biāo)類(lèi)泛化到維閾值控制的層，對(duì)比類(lèi)概念泛化到相同層）4、通過(guò)對(duì)目標(biāo)類(lèi)和對(duì)比類(lèi)使用下鉆、上卷和其他OLAP操作調(diào)整比較描述的抽象層次。5、導(dǎo)出比較的表示量化特征規(guī)則（必要）：T權(quán)：P-135，代表典型性量化判別規(guī)則（充分）：D權(quán)：p-138，代表和對(duì)比類(lèi)比有多大差別（高D權(quán)：概念主要從目標(biāo)類(lèi)導(dǎo)出）量化描述

18、規(guī)則(充分必要)：關(guān)聯(lián)規(guī)則挖掘：關(guān)聯(lián)規(guī)則挖掘：從操作型數(shù)據(jù)庫(kù)、關(guān)聯(lián)數(shù)據(jù)庫(kù)或者其他信息庫(kù)中的項(xiàng)集、對(duì)象中，發(fā)現(xiàn)頻繁模式、關(guān)聯(lián)、相關(guān)或者因果結(jié)構(gòu)。應(yīng)用:Basket data analysis, cross-marketing, catalog design, loss-leader analysis, clustering, classification, etc.例子：Rule form: “Body® Head support, confidence”.buys(x, “diapers”) ®buys(x, “beers”) 0.5%, 60%major(x, “CS”)

19、 takes(x, “DB”) ®grade(x, “A”) 1%, 75%頻繁項(xiàng)集：頻繁地在事務(wù)數(shù)據(jù)集中一起出現(xiàn)的項(xiàng)的集合，滿(mǎn)足最小支持度。支持度：規(guī)則X & Y Þ Z的支持度，事務(wù)中包括X、Y、Z的概率。置信度：在X,Y存在的情況下，Z也在事務(wù)中的概率。兩步過(guò)程：1、找出所有的頻繁項(xiàng)集2、由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則Apriori 算法：該算法利用了頻繁項(xiàng)集所具有的任意頻繁項(xiàng)集的子集都是頻繁項(xiàng)集的這一性質(zhì)對(duì)數(shù)據(jù)庫(kù)進(jìn)行多次掃描:第一次掃描得到頻繁項(xiàng)集的集合L0 ，第k趟掃描前先利用上次掃描的結(jié)果項(xiàng)目集Lk-1,產(chǎn)生候選k項(xiàng)集的集合Ck，然后再通過(guò)掃描數(shù)據(jù)庫(kù)確定C中每

20、一候選k項(xiàng)集的支持?jǐn)?shù)，最后在該次掃描結(jié)束時(shí)求出頻繁k項(xiàng)集的集合Lk，算法的終止條件是Ck或Lk為空。如何通過(guò)Lk-1找到Lk。使用候選產(chǎn)生發(fā)現(xiàn)頻繁項(xiàng)集（1）連接步： Ck根據(jù)Lk-1與自身連接生成（2）剪枝步（子集測(cè)試）Ck是Lk的超集，掃描數(shù)據(jù)庫(kù)，確定Ck中的每個(gè)候選的計(jì)數(shù)，剪去小于最小支持度的項(xiàng)集。Apriori 性質(zhì)：頻繁項(xiàng)集的所有非空子集也必須是頻繁Apriori 核心：用k 項(xiàng)集生成k+1 項(xiàng)集；使用數(shù)據(jù)庫(kù)掃描和模式匹配收集候選項(xiàng)集計(jì)數(shù)Apriori 瓶頸：候選項(xiàng)集計(jì)算量大尤其是1頻繁項(xiàng)集自交叉生成2候選項(xiàng)集時(shí)；數(shù)據(jù)庫(kù)多次掃描，每次抽取都要掃描由Apriori 產(chǎn)生頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)

21、則：由頻繁項(xiàng)集直接產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則s->(l-s),s為l的非空子集提高Apriori 算法的效率：1、基于散列的技術(shù)：一種基于散列的技術(shù)可以用于壓縮候選k 項(xiàng)集Ck（eg:在C1中產(chǎn)生L1的過(guò)程中，可對(duì)每個(gè)事務(wù)產(chǎn)生所有的2項(xiàng)集，并將它們散列到散列表結(jié)構(gòu)的不同桶中，并增加對(duì)應(yīng)的桶計(jì)數(shù)，計(jì)數(shù)低于最小支持桶中的2項(xiàng)集應(yīng)從2候選項(xiàng)集中刪除）2、事務(wù)壓縮：不包含任何K頻繁項(xiàng)集的事務(wù)不可能產(chǎn)生>K的FI應(yīng)在后繼的掃描中刪除3、劃分：任何頻繁項(xiàng)集必須作為局部頻繁項(xiàng)集至少出現(xiàn)在一個(gè)劃分中。4、抽樣：在樣本上降低閾值5、動(dòng)態(tài)項(xiàng)集計(jì)數(shù)：只有子項(xiàng)集都頻繁才將其加入候選項(xiàng)集FP樹(shù)：發(fā)現(xiàn)頻繁項(xiàng)集而不產(chǎn)生候選

22、；分治策略：首先將提供頻繁項(xiàng)的數(shù)據(jù)庫(kù)壓縮到一棵FP樹(shù)上，仍然保留項(xiàng)集相關(guān)信息。然后將壓縮后的數(shù)據(jù)庫(kù)劃分為一組條件數(shù)據(jù)庫(kù)，每個(gè)關(guān)聯(lián)一個(gè)頻繁項(xiàng)或模式段，并分別挖掘每個(gè)條件數(shù)據(jù)庫(kù)。FP核心：利用FP樹(shù)遞歸地增長(zhǎng)頻繁模式路徑（分治）FP優(yōu)點(diǎn)：去除了不相關(guān)的信息；出去節(jié)點(diǎn)連接和計(jì)數(shù)規(guī)模比原數(shù)據(jù)庫(kù)?。豢焖?；將發(fā)現(xiàn)長(zhǎng)頻繁模式的問(wèn)題轉(zhuǎn)換成遞歸地搜索一些較短的模式。· Completeness:u never breaks a long pattern of any transactionu preserves complete information for frequent pattern min

23、ing· Other advantages:u reduce irrelevant informationinfrequent items are goneu never be larger than the original database (if not count node-links and counts)u much faster than AprioriFP性能優(yōu)于Apriori的原因：1、 沒(méi)有候選的產(chǎn)生2、 采用緊湊的數(shù)據(jù)結(jié)構(gòu)3、 消除了對(duì)數(shù)據(jù)庫(kù)的重復(fù)掃描4、 基本的操作既是對(duì)FP的構(gòu)建和計(jì)數(shù)提升度（lift）: ，=1表示A、B獨(dú)立，<1 A、B負(fù)相關(guān)，&g

24、t;1A、B正相關(guān)單維關(guān)聯(lián)規(guī)則：包含單個(gè)謂詞的關(guān)聯(lián)規(guī)則。buys(X, “milk”) Þ buys(X, “bread”)多維關(guān)聯(lián)規(guī)則：一個(gè)以上屬性或謂詞之間的關(guān)聯(lián)規(guī)則。維間關(guān)聯(lián)規(guī)則：具有名不重復(fù)謂詞?；旌详P(guān)聯(lián)規(guī)則：某些謂詞重復(fù)出現(xiàn)。age(X,”19-25”) Ù occupation(X,“student”) Þ buys(X,“coke”)多層關(guān)聯(lián)規(guī)則：在多個(gè)抽象層上挖掘數(shù)據(jù)產(chǎn)生的關(guān)聯(lián)規(guī)則。高層：milk > bread 20%, 60%.底層：Sweet milk-> wheat bread 6%, 50%.一致支持度(對(duì)于所有層使用一致的最

25、小支持度)、遞減支持度（在較低層使用遞減的最小支持度）、基于分組的支持度（基于項(xiàng)或基于分組的最小支持度）分層獨(dú)立策略：檢查所有的節(jié)點(diǎn)而不考慮其父節(jié)點(diǎn)是否頻繁分類(lèi)和預(yù)測(cè)：分類(lèi)：找出描述并區(qū)分?jǐn)?shù)據(jù)類(lèi)或概念的模型，以便能夠使用模型預(yù)測(cè)未知對(duì)象類(lèi)的類(lèi)標(biāo)記，模型的構(gòu)建依賴(lài)于訓(xùn)練集和分類(lèi)屬性的類(lèi)標(biāo)號(hào)的使用。預(yù)測(cè)：建立連續(xù)值函數(shù)模型，預(yù)測(cè)某些空缺的或不知道的數(shù)據(jù)值而不是類(lèi)標(biāo)記。從數(shù)據(jù)分析的角度來(lái)看監(jiān)督學(xué)習(xí)（分類(lèi)）：提供了每個(gè)訓(xùn)練元組的類(lèi)標(biāo)號(hào)，未知元組通過(guò)由訓(xùn)練元組構(gòu)造的模型來(lái)定性類(lèi)標(biāo)號(hào)的預(yù)測(cè)非監(jiān)督學(xué)習(xí)（聚類(lèi)）：每個(gè)訓(xùn)練元組的類(lèi)標(biāo)號(hào)是未知的，并且要學(xué)習(xí)的類(lèi)的個(gè)數(shù)或集合也可能事先不知道，力求尋找類(lèi)或聚類(lèi)的存在。

26、· Typical Applicationsu credit approvalu target marketingu medical diagnosisu treatment effectiveness analysis測(cè)試集來(lái)評(píng)估模型的正確性決策樹(shù)：一種類(lèi)似于流程圖的樹(shù)結(jié)構(gòu)，其中每個(gè)結(jié)點(diǎn)代表在一個(gè)屬性值上的測(cè)試，每個(gè)分支代表測(cè)試的一個(gè)輸出，而樹(shù)葉代表類(lèi)或類(lèi)分布。決策樹(shù)算法：Basic algorithm (a greedy algorithm)自頂向下、遞歸、分治的貪心策略：1、Tree is constructed in a top-down recursive divide-a

27、nd-conquer manner2、At start, all the training examples are at the root3、Attributes are categorical (if continuous-valued, they are discretized in advance)4、Examples are partitioned recursively based on selected attributes5、Test attributes are selected on the basis of a heuristic or statistical measu

28、re (e.g., information gain)結(jié)束條件：1、 所有的樣本都屬于同一個(gè)類(lèi)2、 沒(méi)有剩余的樣本可用3、 沒(méi)有剩余的屬性用來(lái)劃分（投票）避免過(guò)度擬合：· The generated tree may overfit the training data u Too many branches, some may reflect anomalies due to noise or outliersu Result is in poor accuracy for unseen samples前剪枝（在構(gòu)造過(guò)程中，預(yù)定義閾值，如果分裂低于閾值，提前停止樹(shù)的構(gòu)造。一旦停止，該

29、節(jié)點(diǎn)成為樹(shù)葉。） VS 后剪枝（構(gòu)造完成，由完全生長(zhǎng)的樹(shù)剪去子樹(shù)，用其子樹(shù)中最頻繁的類(lèi)標(biāo)記替換。）：貝葉斯：概率學(xué)習(xí)、增量、概率預(yù)測(cè)、標(biāo)準(zhǔn)，可以解決不可見(jiàn)樣本問(wèn)題sample X ，class label C 尋找使 P(C|X)最大的X樸素假設(shè)：類(lèi)條件獨(dú)立P(x1,xk|C) = P(x1|C)··P(xk|C)，當(dāng)出現(xiàn)新的獨(dú)立類(lèi)時(shí)可在原基礎(chǔ)上直接計(jì)算，即增量神經(jīng)網(wǎng)絡(luò)：一組連接的輸入輸出單元，每個(gè)連接都有一個(gè)權(quán)重與之相關(guān)聯(lián)，在學(xué)習(xí)階段通過(guò)調(diào)整這些權(quán)重能夠預(yù)測(cè)輸入元組的正確類(lèi)標(biāo)號(hào)。后向傳播(圖)：初始化權(quán)重向前傳播輸入向后傳播誤差調(diào)整權(quán)值終止條件終止：超過(guò)預(yù)先指定的周期數(shù)；

30、前一周期的權(quán)值調(diào)整小于預(yù)定值/誤分的百分比小于預(yù)定值。后向傳播算法：1. 將從輸入層進(jìn)過(guò)隱藏層到達(dá)輸出層，得到網(wǎng)絡(luò)預(yù)測(cè)值。2. 計(jì)算出網(wǎng)絡(luò)預(yù)測(cè)與實(shí)際已知目標(biāo)的差值（error）3. 將error從輸出層后向傳播到隱藏層4. 修改權(quán)重和偏值，使得預(yù)測(cè)網(wǎng)絡(luò)值和實(shí)際目標(biāo)值的軍方誤差最小5. 如果滿(mǎn)足標(biāo)準(zhǔn)則停止，否則從循環(huán)到step1。后向傳播：通過(guò)迭代地處理一組訓(xùn)練樣本，將每個(gè)樣本的網(wǎng)絡(luò)預(yù)測(cè)與實(shí)際知道的類(lèi)標(biāo)號(hào)比較，進(jìn)行學(xué)習(xí)。對(duì)于每個(gè)訓(xùn)練樣本，修改權(quán)，使得網(wǎng)絡(luò)預(yù)測(cè)和實(shí)際類(lèi)之間的均方誤差最小，這種修改“后向”進(jìn)行。向前傳播輸入：計(jì)算隱藏層和輸出層每個(gè)單元的凈輸入和輸出。向后傳播誤差：通過(guò)更新權(quán)和偏置以反

31、映網(wǎng)絡(luò)預(yù)測(cè)的誤差，向后傳播誤差。急切學(xué)習(xí)法：在接收待分類(lèi)的新元組之前構(gòu)造分類(lèi)模型。懶惰學(xué)習(xí)法：給定訓(xùn)練元組時(shí)，只是簡(jiǎn)單存儲(chǔ)，并一直等到待檢驗(yàn)元組出現(xiàn)才進(jìn)行泛化，比便根據(jù)存儲(chǔ)的訓(xùn)練元組的相似性對(duì)元組進(jìn)行分類(lèi)。1、K-近鄰 找到最接近未知元組的K個(gè)訓(xùn)練元組2、基于案例推理粗糙集：基于等價(jià)類(lèi)的建立，給定類(lèi)的粗糙集定義用兩個(gè)集合近似：上近似，不能認(rèn)為不屬于C的集合；下近似：必定屬于C的集合。分類(lèi)精度高，處理離散屬性。模糊集：對(duì)每個(gè)類(lèi)定義“模糊”的閾值和邊界，模糊邏輯0-0.1之間的真值表示一個(gè)特定的值是一個(gè)給定類(lèi)成員的隸屬程度，而不是用精確的截?cái)啵總€(gè)類(lèi)表示一個(gè)模糊集。分類(lèi)正確性的驗(yàn)證：劃分（獨(dú)立的訓(xùn)

32、練集和測(cè)試集，大規(guī)模）；交叉驗(yàn)證（K個(gè)子樣本集，中等規(guī)模，k-1個(gè)訓(xùn)練集，1個(gè)驗(yàn)證集）分類(lèi)和預(yù)測(cè)的組裝方法：裝袋：對(duì)訓(xùn)練集有放回隨機(jī)抽樣產(chǎn)生N個(gè)訓(xùn)練子集，導(dǎo)出N個(gè)模型，對(duì)未知數(shù)據(jù)，給出對(duì)應(yīng)的N個(gè)結(jié)果。每個(gè)分類(lèi)器投出一票，統(tǒng)計(jì)得票，將得票最高的類(lèi)賦予X。分類(lèi)-多數(shù)表決；預(yù)測(cè)-均值提升：對(duì)訓(xùn)練集有放回隨即抽樣產(chǎn)生N個(gè)訓(xùn)練子集，導(dǎo)出N個(gè)模型。每個(gè)訓(xùn)練元組都賦予一個(gè)權(quán)重。對(duì)每個(gè)訓(xùn)練元組從1-N模型迭代地進(jìn)行，重整每個(gè)元組的權(quán)重；使得在下一輪更關(guān)注上一輪誤分的元組，并計(jì)算每個(gè)模型的投票權(quán)重。分類(lèi)返回具有最大權(quán)重的類(lèi)聚類(lèi)挖掘：聚類(lèi)：要?jiǎng)澐值念?lèi)是未知的，將數(shù)據(jù)對(duì)象分組成為多個(gè)類(lèi)或簇，在同一個(gè)簇中的對(duì)象之間具

33、有較高的相似度，而不同簇中的對(duì)象差別較大。General Applications：· Pattern Recognition· Spatial Data Analysis · Image Processing· Economic Science (especially market research)· WWWu Document classificationu Cluster Weblog data to discover groups of similar access patterns劃分方法：K-均值：以K為輸入?yún)?shù)，將對(duì)象分為K個(gè)簇，是簇內(nèi)，簇外1、隨機(jī)選擇K個(gè)對(duì)象作為K個(gè)簇的中心2、選擇離K最近的點(diǎn)形成簇3、根據(jù)簇中的點(diǎn)計(jì)算新的均值，這個(gè)