數(shù)據(jù)挖掘概論

第一章數(shù)據(jù)挖掘概論什么是數(shù)據(jù)挖掘？數(shù)據(jù)挖掘（DataMiningDM）從大量的數(shù)據(jù)中挖掘出令人感興趣的、有用的、隱含的、先前未知的和可能有用的模式或知識數(shù)據(jù)挖掘的替換詞數(shù)據(jù)庫中的知識挖掘、知識發(fā)現(xiàn)（KDD）知識提煉、數(shù)據(jù)/模式分析數(shù)據(jù)考古數(shù)據(jù)捕撈、信息收獲等等KDD的步驟數(shù)據(jù)清理:（這個可能要占全過程60%的工作量）數(shù)據(jù)集成數(shù)據(jù)選擇數(shù)據(jù)變換數(shù)據(jù)挖掘（選擇適當(dāng)?shù)乃惴▉碚业礁信d趣的模式）模式評估知識表示體系結(jié)構(gòu):典型數(shù)據(jù)挖掘系統(tǒng)知識庫過濾數(shù)據(jù)倉庫知識庫過濾數(shù)據(jù)倉庫數(shù)據(jù)挖掘的主要功能概念/類描述：特性化和區(qū)分歸納，總結(jié)和對比數(shù)據(jù)的特性。關(guān)聯(lián)分析發(fā)現(xiàn)數(shù)據(jù)之間的關(guān)聯(lián)規(guī)則，這些規(guī)則展示屬性一值頻繁的在給定的數(shù)據(jù)中所一起出現(xiàn)的條件。分類和預(yù)測通過構(gòu)造模型（或函數(shù)）用來描述和區(qū)別類或概念，用來預(yù)測類型標(biāo)志未知的對象類。聚類分析將類似的數(shù)據(jù)歸類到一起，形成一個新的類別進(jìn)行分析。孤立點分析通常孤立點被作為“噪音”或異常被丟棄，但在欺騙檢測中卻可以通過對罕見事件進(jìn)行孤立點分析而得到結(jié)論。趨勢和演變分析描述行為隨時間變化的對象的發(fā)展規(guī)律或趨勢數(shù)據(jù)挖掘系統(tǒng)與DB或DW系統(tǒng)的集成方式不耦合松散耦合半緊密耦合緊密耦合概念P23第三章數(shù)據(jù)倉庫和OLAP技術(shù)什么是數(shù)據(jù)倉庫？數(shù)據(jù)倉庫的定義很多，但卻很難有一種嚴(yán)格的定義.“數(shù)據(jù)倉庫是一個面向主題的、集成的、隨時間而變化的、不容易丟失的數(shù)據(jù)集合，支持管理部門的決策過程.”一W.H.Inmon（數(shù)據(jù)倉庫構(gòu)造方面的領(lǐng)頭設(shè)計師）數(shù)據(jù)倉庫關(guān)鍵特征數(shù)據(jù)倉庫關(guān)鍵特征一一一面向主題數(shù)據(jù)倉庫關(guān)鍵特征二一一數(shù)據(jù)集成數(shù)據(jù)倉庫關(guān)鍵特征三 隨時間而變化數(shù)據(jù)倉庫關(guān)鍵特征四一一數(shù)據(jù)不易丟失數(shù)據(jù)倉庫與異種數(shù)據(jù)庫集成傳統(tǒng)的異種數(shù)據(jù)庫集成：在多個異種數(shù)據(jù)庫上建立包裝程序和中介程序采用查詢驅(qū)動方法一一當(dāng)從客戶端傳過來一個查詢時，首先使用元數(shù)據(jù)字典將查詢轉(zhuǎn)換成相應(yīng)異種數(shù)據(jù)庫上的查詢；然后，將這些查詢映射和發(fā)送到局部查詢處理器缺點：復(fù)雜的信息過慮和集成處理，競爭資源數(shù)據(jù)倉庫：采用更新驅(qū)動將來自多個異種源的信息預(yù)先集成，并存儲在數(shù)據(jù)倉庫中，供直接查詢和分析高性能.從關(guān)系表和電子表格到數(shù)據(jù)立方體數(shù)據(jù)倉庫和數(shù)據(jù)倉庫技術(shù)基于多維數(shù)據(jù)模型。這個模型把數(shù)據(jù)看作是數(shù)據(jù)立方體形式。多維數(shù)據(jù)模型圍繞中心主題組織，該主題用事實表表示。事實是數(shù)值度量的。數(shù)據(jù)立方體由維和事實定義。維：是關(guān)于一個組織想要記錄的視角或觀點。每個維都有一個表與之相關(guān)聯(lián)，稱為維表。事實表包括事實的名稱或度量以及每個相關(guān)維表的關(guān)鍵字在最低抽象層建立的立方體是存放最底層匯總的方體叫做基本方體。0維方體存放最高層的匯總，也就是最高層抽象的立方體稱作頂點方體。多維數(shù)據(jù)模型(數(shù)據(jù)立方體)使得從不同的角度對數(shù)據(jù)進(jìn)行觀察成為可能，而概念分層則提供了從不同層次對數(shù)據(jù)進(jìn)行觀察的能力。度量的分類一個數(shù)據(jù)立方體的度量是一個數(shù)值函數(shù)。度量可以根據(jù)其所用的聚集函數(shù)分為三類：分布的(distributive)：將函數(shù)用于n個聚集值得到的結(jié)果和將函數(shù)用于所有數(shù)據(jù)得到的結(jié)果一樣。比如：count()，sum()，min()，max()等代數(shù)的(algebraic)：函數(shù)可以由一個帶M個參數(shù)的代數(shù)函數(shù)計算(M為有界整數(shù))，而每個參數(shù)值都可以有一個分布的聚集函數(shù)求得。比如：avg()，min_N()，standard_deviation()整體的(holistic)：比如：median。，mode()，rank()數(shù)據(jù)倉庫的概念模型最流行的數(shù)據(jù)倉庫概念模型是多維數(shù)據(jù)模型。這種模型可以以星型模式、雪花模式、或事實星座模式的形式存在。星型模式、雪花模式、或事實星座模式畫圖星型模式(Starschema):事實表在中心，周圍圍繞地連接著維表(每維一個)，事實表含有大量數(shù)據(jù)，沒有冗余。雪花模式(Snowflakeschema):是星型模式的變種，其中某些維表是規(guī)范化的，因而把數(shù)據(jù)進(jìn)一步分解到附加表中。結(jié)果，模式圖形成類似于雪花的形狀。事實星座(Factconstellations):多個事實表共享維表，這種模式可以看作星型模式集，因此稱為星系模式(galaxyschema)，或者事實星座(factconstellation)。星型模式實例雪花模式實例timetime_key ,dsyd3ftr_ofjhe_weekmonthquarteryearSalesFactTablebranchMeasuresbranch_keybranch_naniebranchtype事實星座模式實例.itemitem_keyitem_namebrandtype.supplier_keylocationlocation_keystreetcitvkey.supplier_supplierJ<eysupplier_rypecil^7_keydtystate_Q匚time_key ,dsyd3ftr_ofjhe_weekmonthquarteryearSalesFactTablebranchMeasuresbranch_keybranch_naniebranchtype事實星座模式實例.itemitem_keyitem_namebrandtype.supplier_keylocationlocation_keystreetcitvkey.supplier_supplierJ<eysupplier_rypecil^7_keydtystate_Q匚proviiicecountrytimetinie_keydayday_of_the_weekmanlthquarteryearitembranchkeylocation_keyunits_solddollars_soldlocation^k^streetcityprovinee_or_statecountry7\ShippingFactTabletime_k^ritem_keyshipper_key...fromJocationto_lcx:ationdollarsjcostunits_shippedavg_salesshipper/ 1——shippet^_keyshipper_nai]ielocation_ke：yshipperfype多維數(shù)據(jù)模型上的OLAP操作上卷(roll-up):匯總數(shù)據(jù)通過一個維的概念分層向上攀升或者通過維規(guī)約下鉆(drill-down)：上卷的逆操作由不太詳細(xì)的數(shù)據(jù)到更詳細(xì)的數(shù)據(jù)，可以通過沿維的概念分層向下或引入新的維來實現(xiàn)切片和切塊(sliceanddice)切片操作在給定的數(shù)據(jù)立方體的一個維上進(jìn)行選擇，導(dǎo)致一個子立方體切塊操作通過對兩個或多個維進(jìn)行選擇，定義子立方體轉(zhuǎn)軸(pivot)立方體的重定位，可視化，或?qū)⒁粋€3維立方體轉(zhuǎn)化維一個2維平面序列其他OLAP操作鉆過(drill_across)：執(zhí)行涉及多個事實表的查詢鉆透(drill_through)：使用關(guān)系SQL機(jī)制，鉆到數(shù)據(jù)立方體的底層，到后端關(guān)系表。典型的數(shù)據(jù)倉庫設(shè)計過程選取待建模的商務(wù)過程選取商務(wù)過程的顆粒度比如：記錄每條詳細(xì)訂單，或是開始于每日的匯總數(shù)據(jù)選取用于每個事實表記錄的維常用的維有：時間、貨物、客戶、供應(yīng)商等選取將安放在事實表中的度量常用的數(shù)字度量包括：售價、貨物數(shù)量等三種數(shù)據(jù)倉庫模型企業(yè)倉庫數(shù)據(jù)集市虛擬倉庫10.OLAP服務(wù)器類型邏輯上，OLAP服務(wù)器從數(shù)據(jù)倉庫或數(shù)據(jù)集市中給商業(yè)用戶提供多維數(shù)據(jù)物理上，OLAP的底層數(shù)據(jù)存儲實現(xiàn)可以有多種不同的方式關(guān)系OLAP服務(wù)器多維OLAP服務(wù)器混合OLAP服務(wù)器特殊的SQL服務(wù)器在星型和雪花模型上支持SQL查詢。第三章數(shù)據(jù)預(yù)處理為什么要預(yù)處理數(shù)據(jù)？現(xiàn)實世界的數(shù)據(jù)是“骯臟的”不完整的：有些感興趣的屬性缺少屬性值，或僅包含聚集數(shù)據(jù)。含噪聲的：包含錯誤或者“孤立點”。不一致的：在編碼或者命名上存在差異。數(shù)據(jù)預(yù)處理的主要任務(wù)數(shù)據(jù)清理填寫空缺的值，平滑噪聲數(shù)據(jù)，識別、刪除孤立點，解決不一致性數(shù)據(jù)集成集成多個數(shù)據(jù)庫、數(shù)據(jù)立方體或文件數(shù)據(jù)變換規(guī)范化和聚集數(shù)據(jù)歸約：得到數(shù)據(jù)集的壓縮表示，它小得多，但可以得到相同或相近的結(jié)果數(shù)據(jù)離散化數(shù)據(jù)歸約的一部分通過概念分層和數(shù)據(jù)的離散化來規(guī)約數(shù)據(jù)對數(shù)字型數(shù)據(jù)特別重。如何處理空缺值忽略元組：。人工填寫空缺值：工作量大，可行性低。使用一個全局變量填充空缺值：比如使用unknown或-8。使用屬性的平均值填充空缺值。使用與給定元組屬同一類的所有樣本的平均值。使用最可能的值填充空缺值。P63頁習(xí)題2.4(a~f)特征化和比較兩種不同類別的數(shù)據(jù)挖掘從數(shù)據(jù)分析的角度看，數(shù)據(jù)挖掘可以分為描述性挖掘和預(yù)測性挖掘什么是概念描述？概念描述：為數(shù)據(jù)的特征化和比較產(chǎn)生描述(當(dāng)所描述的概念所指的是一類對象時，也稱為類描述)特征化：提供給定數(shù)據(jù)集的簡潔匯總。區(qū)分：提供兩個或多個數(shù)據(jù)集的比較描述。數(shù)據(jù)概化數(shù)據(jù)庫中的數(shù)據(jù)和對象通常包含原始概念層的細(xì)節(jié)信息，數(shù)據(jù)概化就是將數(shù)據(jù)庫中的跟任務(wù)相關(guān)的數(shù)據(jù)集從較低的概念層抽象到較高的概念層的過程。概念層第六章關(guān)聯(lián)規(guī)則挖掘什么是關(guān)聯(lián)規(guī)則挖掘？關(guān)聯(lián)規(guī)則挖掘：從事務(wù)數(shù)據(jù)庫，關(guān)系數(shù)據(jù)庫和其他信息存儲中的大量數(shù)據(jù)的項集之間發(fā)現(xiàn)有趣的、頻繁出現(xiàn)的模式、關(guān)聯(lián)和相關(guān)性。應(yīng)用：購物籃分析、分類設(shè)計、捆綁銷售和虧本銷售分析由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則同時滿足最小支持度和最小置信度的才是強關(guān)聯(lián)規(guī)則，從頻繁項集產(chǎn)生的規(guī)則都滿足支持度要求，而其置信度則可由一下公式計算：confidence(AB)=P(A\B)= = support_countyA)每個關(guān)聯(lián)規(guī)則可由如下過程產(chǎn)生：對于每個頻繁項集1，產(chǎn)生l的所有非空子集；對于每個非空子集s，如果suppartcount(I) , 。 = >nnn_canf zj_x，則輸出規(guī)則“-—J：—”。3Apriori算法 示例DatabaseTDBr',l：＞10A,C,D20B,C,E30A,B,C,E40B?E1stscanItemsetsup{A}2{B}3{C}3{□}1{E}3Itemsetsup{A}2擔(dān)｝3{C}3{E}3l2Itemsetsup4c}20C}2但E}3(C,E}2Itemsetsup1{A,C}2{W}1但C}2{B.E}3{C,E}2?ndItemsetCmItemset◎C,E}|{A、B}佻C}{A、E}俱C}{B；E}{C,E}Itemsetsup|{B，E}|4.多層關(guān) 致支持度VS.遞減支持度一致支持度：對所有層都使用一致的最小支持度遞減支持度：在較低層使用遞減的最小支持度第七章分類和預(yù)測分類：預(yù)測分類標(biāo)號（或離散值）根據(jù)訓(xùn)練數(shù)據(jù)集和類標(biāo)號屬性，構(gòu)建模型來分類現(xiàn)有數(shù)據(jù)，并用來分類新數(shù)據(jù)數(shù)據(jù)分類 個兩步過程第一步，建立一個模型，描述預(yù)定數(shù)據(jù)類集和概念集假定每個元組屬于一個預(yù)定義的類，由一個類標(biāo)號屬性確定。學(xué)習(xí)模型可以用分類規(guī)則、判定樹或數(shù)學(xué)公式的形式提供。第二步，使用模型，對將來的或未知的對象進(jìn)行分類首先評估模型的預(yù)測準(zhǔn)確率。若預(yù)測準(zhǔn)確率可接受，則用該模型對未知元組進(jìn)行分類。用判定樹歸納分類判定樹的生成由兩個階段組成判定樹構(gòu)建樹剪枝判定樹的使用：對未知樣本進(jìn)行分類通過將樣本的屬性值與判定樹相比較防止分類中的過分適應(yīng)產(chǎn)生的判定樹會出現(xiàn)過分適應(yīng)數(shù)據(jù)的問題由于數(shù)據(jù)中的噪聲和孤立點，許多分枝反應(yīng)的是訓(xùn)練數(shù)據(jù)中的異常對新樣本的判定很不精確防止過分適應(yīng)的兩種方法先剪枝：后剪枝：后向傳播分類后向傳播是一種神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法。模糊分類Fuzzy基本思想：用屬于程度即隸屬度來代替屬于或不屬于個體識別(分類)最大隸屬原則：閾值原則：群體識別貼近度1例三角形識別(用于識別染色體及白血球分類)M={工=\A>B>C,A+B^C=180}近似直角三角形：R(x)=R(A,B,C}=1—土M—90|近似等腰三角形：I(x)=1-—minO-B\(B-60近似等邊三角形：E(x)=E(A^B^C)=1--(4-C)閾值原則：型三角形：r=RcnrnEc計算4](工。)4(也)〉——「4(0；給定閾值aw?1],若4(工。)>%J(x0)>?. ￡ ii稱X。相對隸屬于40廣-,&.■L工 苗例如：在例2中，若氣=(A.B.C)=(85,50,45)貝葉斯分類7?(t0)=0.95?7(x0)=0.91?￡(t0)=0.87T(0=(1—R(x0))/\(l-J(x0))a(1-E(x0))=0.05取a二0.9,由閾值原則，辦應(yīng)為近似等腰直角三角形貝葉斯分類利用統(tǒng)計學(xué)中的貝葉斯定理，來預(yù)測類成員的概率，即給定一個樣本，計算該樣本屬于一個特定的類的概率。樸素貝葉斯分類：假設(shè)每個屬性之間都是相互獨立的，并且每個屬性對非類問題產(chǎn)生的影響都是一樣的。第八章聚類分析什么是聚類分析？聚類分析將物理或抽象對象的集合分組成為由類似的對象組成的多個類的過程。聚類是一種無指導(dǎo)的學(xué)習(xí)：沒有預(yù)定義的類編號。聚類分析的數(shù)據(jù)挖掘功能作為一個獨立的工具來獲得數(shù)據(jù)分布的情況。作為其他算法(如：特征和分類)的預(yù)處理步驟。主要的聚類方法及特點聚類分析算法種類繁多，具體的算法選擇取決于數(shù)據(jù)類型，聚類的應(yīng)用和目的，常用的聚類算法包括：劃分方法：一般按距離劃分，適宜發(fā)現(xiàn)球形的簇。層次的方法，缺點：合并或分裂的步驟不能被撤銷?；诿芏鹊姆椒ǎ嚎梢赃^濾掉“噪聲”和“孤立點”，發(fā)現(xiàn)任意形狀的簇?；诰W(wǎng)格的方法：處理速度快?；谀Ｐ偷姆椒ǎ簽槊總€簇假定一個模型，尋找數(shù)據(jù)對給定模型的最佳擬合。實際應(yīng)用中的聚類算法，往往是上述聚類方法中多種方法的整合。相異度計算許多聚類算法都是以相異度矩陣為基礎(chǔ)，如果數(shù)據(jù)是用數(shù)據(jù)矩陣形式表示，則往往要將其先轉(zhuǎn)化為相異度矩陣。相異度d(ij)的具體計算會因所使用的數(shù)據(jù)類型不同而不同，常用的數(shù)據(jù)類型包括：區(qū)間標(biāo)度變量二元變量標(biāo)稱型、序數(shù)型和比例標(biāo)度型變量混合類型的變量二元變量(1)一個二元變量只有兩種狀態(tài)：0或1；e.g.smoker來表示是否吸煙一個對象可以包含多個二元變量。二元變量的可能性表：如何