廣工數(shù)據(jù)挖掘復(fù)習(xí)要點

第一章緒論.數(shù)據(jù)挖掘要解決的問題：面對高維，復(fù)雜，異構(gòu)的海量數(shù)據(jù)，如何集中獲取有用的信息和知識。.數(shù)據(jù)挖掘定義：?技術(shù)層面上：數(shù)據(jù)挖掘就是從大量數(shù)據(jù)提取有用信息的過程；?商業(yè)層面上：數(shù)據(jù)挖掘就是對大量業(yè)務(wù)數(shù)據(jù)進行抽取，轉(zhuǎn)換和分析以及建模處理，從中提取輔助商業(yè)決策的關(guān)鍵性數(shù)據(jù)。.數(shù)據(jù)挖掘的特征：先前未知，有效和實用。.數(shù)據(jù)挖掘?qū)ο螅?關(guān)系數(shù)據(jù)庫（借助集合代數(shù)等概念和方法來處理數(shù)據(jù)庫中的數(shù)據(jù)）?數(shù)據(jù)倉庫（數(shù)據(jù)集合，用于支持管理決策）?事務(wù)數(shù)據(jù)庫（每個記錄代表一個事務(wù)）?空間數(shù)據(jù)庫?事態(tài)數(shù)據(jù)庫和時間序列數(shù)據(jù)庫?流數(shù)據(jù)?多媒體數(shù)據(jù)庫?文本數(shù)據(jù)庫?萬維數(shù)據(jù)庫.數(shù)據(jù)挖掘任務(wù)：分類分析（按照某種規(guī)則），聚類分析（具有共性），回歸分析，關(guān)聯(lián)分析（具有關(guān)聯(lián)規(guī)則），離群點檢測（發(fā)現(xiàn)與眾不同的數(shù)據(jù)），演化分析（隨時間變化的數(shù)據(jù)對象的趨勢），序列模式挖掘（分析前后序列模式）.數(shù)據(jù)挖掘過程：數(shù)據(jù)清洗，數(shù)據(jù)集成（考慮數(shù)據(jù)一致性和冗余），數(shù)據(jù)選擇，數(shù)據(jù)轉(zhuǎn)換，數(shù)據(jù)挖掘，模式評估，知識表示。例題：1.1數(shù)據(jù)挖掘處理的對象有哪些？請從實際生活中舉出至少三種。答：數(shù)據(jù)挖掘處理的對象是某一專業(yè)領(lǐng)域中積累的數(shù)據(jù)，對象既可以來自社會科學(xué),又可以來自自然科學(xué)產(chǎn)生的數(shù)據(jù)，還可以是衛(wèi)星觀測得到的數(shù)據(jù)。數(shù)據(jù)形式和結(jié)構(gòu)也各不相同，可以是傳統(tǒng)的關(guān)系數(shù)據(jù)庫,可以是面向?qū)ο蟮母呒墧?shù)據(jù)庫系統(tǒng)，也可以是面向特殊應(yīng)用的數(shù)據(jù)庫，如空間數(shù)據(jù)庫、時序數(shù)據(jù)庫、文本數(shù)據(jù)庫和多媒體數(shù)據(jù)庫等，還可以是Web數(shù)據(jù)信息。實際生活的例子：①電信行業(yè)中利用數(shù)據(jù)挖掘技術(shù)進行客戶行為分析，包含客戶通話記錄、通話時間、所開通的服務(wù)等，據(jù)此進行客戶群體劃分以及客戶流失性分析。②天文領(lǐng)域中利用決策樹等數(shù)據(jù)挖掘方法對上百萬天體數(shù)據(jù)進行分類與分析，幫助天文學(xué)家發(fā)現(xiàn)其他未知星體。③制造業(yè)中應(yīng)用數(shù)據(jù)挖掘技術(shù)進行零部件故障診斷、資源優(yōu)化、生產(chǎn)過程分析等。④市場業(yè)中應(yīng)用數(shù)據(jù)挖掘技術(shù)進行市場定位、消費者分析、輔助制定市場營銷策略等。1.5定義下列數(shù)據(jù)挖掘功能：關(guān)聯(lián)、分類、聚類、演變分析、離群點檢測。使用你熟悉的生活中的數(shù)據(jù)，給出每種數(shù)據(jù)挖掘功能的例子。答：關(guān)聯(lián)是指發(fā)現(xiàn)樣本間或樣本不同屬性間的關(guān)聯(lián)。例如，一個數(shù)據(jù)挖掘系統(tǒng)可能發(fā)現(xiàn)的關(guān)聯(lián)規(guī)則為：major（X,**computingscience）owns（X,**personalcomputerw）[support=12%,confidence=98%]其中，X是一個表示學(xué)生的變量。該規(guī)則指出主修計算機科學(xué)并且擁有一臺個人計算機的學(xué)生所占比例為12%,同時，主修計算機專業(yè)的學(xué)生有98%擁有個人計算機。分類是構(gòu)造一系列能描述和區(qū)分?jǐn)?shù)據(jù)類型或概念的模型（或功能），分類被用作預(yù)測目標(biāo)數(shù)據(jù)的類的標(biāo)簽。例如，通過對過去銀行客戶流失與未流失客戶數(shù)據(jù)的分析，得到一個預(yù)測模型，預(yù)測新客戶是否可能會流失。聚類是將數(shù)據(jù)劃分為相似對象組的過程，使得同一組中對象相似度最大而不同組中對象相似度最小。例如，通過對某大型超市客戶購物數(shù)據(jù)進行聚類，將客戶聚類細(xì)分為低值客戶、高值客戶以及普通客戶等。數(shù)據(jù)演變分析描述和模型化隨時間變化的對象的規(guī)律或趨勢，盡管這可能包括時間相關(guān)數(shù)據(jù)的特征化、區(qū)分、關(guān)聯(lián)和相關(guān)分析、分類、或預(yù)測，這種分析的明確特征包括時間序列數(shù)據(jù)分析、序列或周期模式匹配、和基于相似性的數(shù)據(jù)分析。離群點檢測就是發(fā)現(xiàn)與眾不同的數(shù)據(jù)?？捎糜诎l(fā)現(xiàn)金融領(lǐng)域的欺詐檢測。第二章數(shù)據(jù)處理基礎(chǔ).數(shù)據(jù)及數(shù)據(jù)類型：數(shù)據(jù)是數(shù)據(jù)庫存儲的基本對象，數(shù)據(jù)類型：標(biāo)稱屬性，序數(shù)屬性，區(qū)間屬性，比率屬性。.數(shù)據(jù)集分為三類：記錄數(shù)據(jù)，基于圖形的數(shù)據(jù)和有序的數(shù)據(jù)集。補充：數(shù)據(jù)統(tǒng)計特征：均值，中位數(shù)，中列數(shù)（數(shù)據(jù)集中最大和最小值的平均值），眾數(shù)（出現(xiàn)頻率最高的值），截斷均值（指定。?10間的百分位數(shù)p.丟棄高端的和低端的（p/2）%的數(shù)據(jù)，然后按照計算均值那樣計算）.數(shù)據(jù)挖掘的效果直接受到數(shù)據(jù)源的影響。.數(shù)據(jù)清理的目的：試圖填充缺失數(shù)據(jù)，去除噪聲并識別離群點，糾正數(shù)據(jù)中的不一致值。.缺失值的處理方法：（分析時）忽略元組，（分析時）忽略屬性列，（估計缺失值）人工填寫缺失數(shù)據(jù)，（估計缺失值）自動填充缺失數(shù)據(jù)。.噪聲平滑方法：分箱，聚類。.數(shù)據(jù)聚合的目的：將兩個或多個數(shù)據(jù)源中的數(shù)據(jù)，存放在一個一致的數(shù)據(jù)存儲設(shè)備中。.數(shù)據(jù)變換的內(nèi)容：數(shù)據(jù)泛化（把學(xué)科分為理學(xué)和工學(xué)，忽略細(xì)節(jié)），規(guī)范化，特征構(gòu)造（集中數(shù)據(jù)特征構(gòu)造新的特征，減少特征維數(shù)），數(shù)據(jù)離散化（出現(xiàn)了嫡計算）。.數(shù)據(jù)歸約：維度歸約和特征變換：維度歸約可以刪除不相關(guān)的特征并降低噪聲，降低維度災(zāi)難風(fēng)險，降低數(shù)據(jù)挖掘的時間復(fù)雜度和空間復(fù)雜度，特征變幻可以反應(yīng)出數(shù)據(jù)的不同視角的不同特征。抽樣：長期用于數(shù)據(jù)的事先調(diào)查和最終的數(shù)據(jù)分析，在數(shù)據(jù)挖掘中，抽樣是選擇數(shù)據(jù)子集進行分析的常用方法。1）無放回的簡單隨機抽樣方法2）有放回的簡單隨機抽樣方法3）分層抽樣方法特征選擇：從一組已知特征的集合中選取最具有代表性的特征子集，使其保留原有數(shù)據(jù)的大部分特征，正確區(qū)分?jǐn)?shù)據(jù)集中的每個數(shù)據(jù)對象。根據(jù)特征選擇過程與后續(xù)數(shù)據(jù)挖掘任務(wù)的關(guān)聯(lián)可分為三種方法：過濾，封裝和嵌入。根據(jù)是否用到類信息的指導(dǎo)，分為監(jiān)督式，無監(jiān)督式和半監(jiān)督式特征選擇?特征子集選擇的搜索策略：逐步向前選擇（從空集開始，逐步添加），逐步向后刪除（從整個屬性集開始，逐個刪除），向前選擇和向后刪除相結(jié)合，決策樹歸約。特征搜索過程中不可缺少的環(huán)節(jié)就是逐步評估。★數(shù)據(jù)預(yù)處理方法：數(shù)據(jù)清理，數(shù)據(jù)集成，數(shù)據(jù)變換，數(shù)據(jù)歸約，數(shù)據(jù)離散化例題：假定用于分析的數(shù)據(jù)包含屬性age,數(shù)據(jù)元組中age的值如下（按遞增序）：13,15,16,16,19,20,20,21,22,22,25,25,25,25,30,33,33,33,35,35,35,35,36,40,45,46,52,7 0。（a）使用按箱平均值平滑對以上數(shù)據(jù)進行平滑，箱的深度為3。解釋你的步驟。評論對于給定的數(shù)據(jù)，該技術(shù)的效果。（b）對于數(shù)據(jù)平滑，還有哪些其它方法？答：（a）已知數(shù)據(jù)元組中age的值如下（按遞增序）：13,15,16,16,19,20,20,21,22,22,25,25,25,25,30,33,33,33,35,35,35,35,36,40,45,46,52,70,且箱的深度為3,劃分為（等頻）箱：箱1:13,15,16箱2：16,19,20箱3：20,21,22箱4：22,25,25箱5：25,25,30箱6：33,33,33箱7：35,35,35箱8：35,36,40箱9：45,46,52箱10：70用箱均值光滑：箱1：15,15,15箱2：18,18,18箱3：21,21,21箱4：24,24,24箱5：27,27,37箱6：33,33,33箱7：35,35,35箱8：37,37,37箱9：48,48,48箱10：70；(b)對于數(shù)據(jù)平滑，其它方法有：(1)回歸：可以用一個函數(shù)(如回歸函數(shù))擬合數(shù)據(jù)來光滑數(shù)據(jù)；(2)聚類：可以通過聚類檢測離群點，將類似的值組織成群或簇。直觀地，落在簇集合之外的值視為離群點。使用習(xí)題2.5給出的age數(shù)據(jù)，回答以下問題：(a)使用min-max規(guī)范化，將age值35轉(zhuǎn)換到［0.0,1.0］區(qū)間。(b)使用z-s8re規(guī)范化轉(zhuǎn)換age值35.其中，age的標(biāo)準(zhǔn)偏差為12.94年。(c)使用小數(shù)定標(biāo)規(guī)范化轉(zhuǎn)換age值35。(d)指出對于給定的數(shù)據(jù)，你愿意使用哪種方法。陳述你的理由。135-13答：(a)已知最大值為70,最小值為13,則可將35規(guī)范化為：* ,*=0.386；/U-Id一 35?30八c”(b)已知均值為30,標(biāo)準(zhǔn)差為12.94,則可將35規(guī)范化為： ?.^=0.386；35(c)使用小數(shù)定標(biāo)規(guī)范化可將35規(guī)范化為： ——=0.35；1002.17給定兩個向量對象，分別表示為p1(22,1,42,10),p2(20.0,36,8)：(a)計算兩個對象之間的歐幾里得距離(b)計算兩個對象之間的曼哈頓距離(c)計算兩個對象之間的閔可夫斯基距離.用x=3(d)計算兩個對象之間的切比雪夫距離答：(a)計算兩個對象之間的歐幾里得距離d=^2—20)2+(1—0)2+(42—36)2+(10—8)2=1/4512(b)計算兩個對象之間的曼哈頓距離d12=|22-20|+|1-0|+|42-36|+|10-8|=11(C)計算兩個對象之間的閔可夫斯基距離，其中參數(shù)r=3d=3722—20|3+11—0|3+|42—36|3+|10—12(d)切比雪夫距離：d12=max(|p—q|)=6以下是一個商場所銷售商品的價格清單(按遞增順序排列，括號中的數(shù)表示前面數(shù)字出現(xiàn)次數(shù))1(2)、5(5)、8(2)、10(4)、12、14(3)、15(5)、18(8)、20(7)、21(4)、25(5)、28、30(3)。請分別用等寬的方法和等高的方法對上面的數(shù)據(jù)集進行劃分。答：(D等寬方法：劃分為3個數(shù)據(jù)集，每個數(shù)據(jù)集的寬度為價格10。價格在1-10之間出現(xiàn)次數(shù)為13；價格在11-20之間出現(xiàn)的次數(shù)為24；價格在21-30之間出現(xiàn)的次數(shù)為13。(2)等高方法：劃分為2個數(shù)據(jù)集，每個數(shù)據(jù)集的高度為出現(xiàn)的次數(shù)4。出現(xiàn)次數(shù)1―4之間的價格為1、8、10、12、14、21、28、30,共8個數(shù)據(jù)；出現(xiàn)次數(shù)5—8之間的價格為5、15、18、20、25,共5個數(shù)據(jù)。討論數(shù)據(jù)聚合需要考慮的問題。答：數(shù)據(jù)聚合需要考慮的問題有：(1)模式識別：這主要是實體識別問題；(2)冗余：一個屬性是冗余的，即它能由另一個表導(dǎo)出，如果屬性或維的命名不一致，也可能導(dǎo)致冗余，可以用相關(guān)分析來檢測；(3)數(shù)據(jù)值沖突的檢測與處理：有些屬性因表示比例或編碼不同，會導(dǎo)致屬性不同。第三章分類與回歸.分類：分類是數(shù)據(jù)挖掘中的主要手段，其任務(wù)是對數(shù)據(jù)集進行學(xué)習(xí)并構(gòu)造一個擁有預(yù)測功能的分類模型，用于預(yù)測未知樣本的類標(biāo)號，把類標(biāo)號未知的樣本映射到某個預(yù)先給定的類標(biāo)號中。.分類模型學(xué)習(xí)方法：基于決策樹的分類方法，貝葉斯分類方法，k-最近鄰分類方法，神經(jīng)網(wǎng)絡(luò)方法。.決策樹的概念與構(gòu)建：決策樹是一種樹形結(jié)構(gòu)，包括決策節(jié)點，分支節(jié)點和頁節(jié)點三個部分。決策節(jié)點：代表某個測試，通常對應(yīng)帶分類對象的某個屬性。該屬性上的不同測試結(jié)果對應(yīng)一個分支。葉節(jié)點：每個葉節(jié)點對應(yīng)一個類標(biāo)號，表示一種可能的分類結(jié)果。決策樹的構(gòu)建：1)屬性的選擇(很重要，一般要最大限度地增大樣本集純度)2)獲得大小適合的決策樹3)使用ID3等經(jīng)典算法構(gòu)建決策樹.分類模型的評價：分類過程一般分為兩步：第一步是利用分類算法對訓(xùn)練集進行學(xué)習(xí)，建立分類模型：第二步是用分類模型對標(biāo)號未知的測試數(shù)據(jù)進行分類。.分類模型性能評價指標(biāo)：(1)分類準(zhǔn)確率：指模型正確地預(yù)測新的或先前未知的數(shù)據(jù)的類標(biāo)號的能力。(影響分類準(zhǔn)確率的因素：訓(xùn)練數(shù)據(jù)集，記錄的數(shù)目，屬性的數(shù)目，屬性中的信息，測試數(shù)據(jù)集記錄的分布情況)(2)計算復(fù)雜度：決定著算法執(zhí)行的速率和占用的資源，依賴于具體的實現(xiàn)細(xì)節(jié)和軟、硬件環(huán)境。(3)可解釋性：分類結(jié)果只有可解釋性好，容易理解，才能更好地用于決策支持。(4)可伸縮性。(5)穩(wěn)定性：指不會隨著數(shù)據(jù)的變化而發(fā)生劇烈變化。(6)強壯性：指數(shù)據(jù)集含有噪聲和空缺值的情況下，分類器正確分類數(shù)據(jù)的能力。.分類模型的誤差：(1)訓(xùn)練誤差和泛化誤差。.評估分類模型的性能的方法：(1)保持方法：以無放回抽樣方式把數(shù)據(jù)集分為兩個相互獨立的子集，訓(xùn)練集(2/3)

和測試集(1/3)；(2)隨機子抽樣：保持方法的多次迭代；3)k-折交叉驗證。例題：考慮表3-23所示二元分類問題的數(shù)據(jù)集。表3-23習(xí)題3.4數(shù)據(jù)集A B 類標(biāo)號TOC\o"1-5"\h\zT F +T +T T +(1)計算按照屬性A和B劃分時的信息增益。決策樹歸納算法將會選擇那個屬性？(2)計算按照屬性A和B劃分時Gini系數(shù)。決策樹歸納算法將會選擇那個屬性？按照屬性A和B劃分時，數(shù)據(jù)集可分為如下兩種情況：B=TB=FB=TB=F劃分前樣本集的信息懶為E=-0.4log20.4-0.6log20.6=0.9710按照屬性A劃分樣本集分別得到的兩個子集(A取值T和A取值F)的信息嫡分別為:43 3E=—log--log-=0.9852A=T7^277飛7r3, 30, 0oE=—log log—=0a=f323323按照屬性A劃分樣本集得到的信息增益為：A=E--^E-^-E=0.281310A=T10A=F按照屬性B劃分樣本集分別得到的兩個子集(B取值T和B取值F)的信息懶分別為:按照屬性B劃分樣本集得到的信息增益為：A=Er±ETe=0.256510B=T10B=F因此，決策樹歸納算法將會選擇屬性A。劃分前的Gini值為G=1-0.42-0.62=0.48按照屬性A劃分時Gini指標(biāo)：G=1JEfJ3y=0.4898A=T(7) (7)GJ-需囪=。Gini增益A=G-2g--^-G=0.137110A=T10A=F按照屬性B劃分時Gini指標(biāo)：Gbt=1 =0.3750G=1 =0.2778b-'(6)'(6jGini增益A=G-4g--G=0.163310B=T10B=F因此，決策樹歸納算法將會選擇屬性B。3.2考慮表3-24數(shù)據(jù)集，請完成以下問題：表3-24習(xí)題3.7數(shù)據(jù)集日記錄號ABC類1000+2001301140115001+6101710181019111+10101+⑴估計條件概率P(A|+),P(B|+),P(C|+),P(A|-),P(B|-),P(C|-).(2)根據(jù)(1)中的條件概率，使用樸素貝葉斯方法預(yù)測測試樣本(A=0,B=1,C=0)的類標(biāo)號；⑶使用Laplace估計方法，其中p=1/2,1=4,估計條件概率P(A|+),P(B|+),P(C|+),P(A|-).P(B|-).P(C|-).(4)同(2),使用(3)中的條件概率(5)比較估計概率的兩種方法，哪一種更好，為什么？答：⑴P(A|+)=3/5P(B|+)=1/5P(A|-)=2/5P(B|-)=2/5P(C|-)=1(2)假設(shè)P(A=0,B=1,C=0)=K則K屬于兩個類的概率為：P(+|A=0,B=1,C=0)=P(A=0,B=1,C=0|+)xP(+)/K(貝葉斯算法)=P(A=0|+)P(B|+)P(C=0|+)xP(+)/K=0.4x0.2x0.2x0.5/K=0.008/KP(-|A=0,B=1,C=0)=P(A=0,B=1,C=O|-)xP(-)/K=P(A=0|-)P(B|-)P(C=0|-)xP(-)/K=0.4x0.2x0x0.5/K=0/K則得到，此樣本的類標(biāo)號是+。(3)P(A|+)=(3+2)/(5+4)=5/9P(A|-)=(2+2)/(5+4)=4/9P(B|+)=(1+2)/(5+4)=1/3P(B|-)=(2+2)/(5+4)=4/9P(C|-)=(0+2)/(5+4)=2/9(4)假設(shè)P(A=0,B=1,C=0)=K則K屬于兩個類的概率為：P(+|A=0,B=1,C=0)=P(A=0,B=1,C=O)xP(+)/K=P(A=O|+)P(B|+)P(C=O|+)xP(+)/K=(4/9)x(1/3)x(1/3)x0.5/K=0.0247/KP(-|A=0,B=1,C=0)=P(A=0,B=1,C=O)xP(-)/K=P(A=O|-)P(B|-)P(C=O|-)xP(-)/K=(5/9)x(4/9)x(2/9)x0.5/K=0.0274/K則得到，此樣本的類標(biāo)號是“(5)當(dāng)條件概率為0的時候，條件概率的預(yù)測用Laplace估計方法比較好，因為我們不想整個條件概率計算結(jié)果為0.第四章聚類分析.聚類：聚類就是將數(shù)據(jù)集劃分為由若干相似對象組成的多個組或簇的過程，使得同一組中的對象的相似度最大化，不同組中的相似度最小化?；蛘哒f聚類是由彼此相似的一組對象構(gòu)成的集合。分類：分類是數(shù)據(jù)挖掘中的主要手段，其任務(wù)是對數(shù)據(jù)集進行學(xué)習(xí)并構(gòu)造一個擁有預(yù)測功能的分類模型，用于預(yù)測未知樣本的類標(biāo)號，把類標(biāo)號未知的樣本映射到某個預(yù)先給定的類標(biāo)記：聚類和分類的區(qū)別.典型的聚類分析任務(wù)包括的步驟：1)模式表示(聚類算法的基礎(chǔ))，2)適合于數(shù)據(jù)領(lǐng)域的模式相似性定義(是聚類分析最基本的問題)，3)聚類或者劃分算法(聚類分析的核心)，4)數(shù)據(jù)摘要(如有必要)，5)輸出結(jié)果的評估，有效性的評估(如有必要).數(shù)據(jù)挖掘?qū)垲惖牡湫鸵螅?)可伸縮性，2)處理不同類型屬性的能力3)發(fā)現(xiàn)任意形狀的聚類4)用于決定輸入?yún)?shù)的領(lǐng)域知識最小化5)處理噪聲數(shù)據(jù)的能力6)對輸入記錄的順序不敏感7)高維度8)基于約束的聚類9)可解釋性和可用性。.典型聚類方法：1)劃分方法(每個劃分表示一個聚類)2)層次方法(將數(shù)據(jù)對象組成一個聚類樹)3)基于密度的方法(絕大多數(shù)劃分方法都是基于對象之間的距離大小進行聚類)4)基于模型的方法(試圖將給定數(shù)據(jù)與某個數(shù)學(xué)模型搭成最佳擬合)5)基于圖的聚類算法(利用圖的許多重要性質(zhì)和特性).k-means算法，層次聚類算法的優(yōu)缺點：k-means算法：優(yōu)點：算法描述容易，實現(xiàn)簡單快速；不足：?簇的個數(shù)要預(yù)先給定，?對初始值的依賴極大?不適合大量數(shù)據(jù)的處理?對噪聲點和離群點很敏感?很難檢測到“自然的”簇。(2)層次聚類算法：BIRCH算法：優(yōu)點：利用聚類特征樹概括了聚類的有用信息，節(jié)省內(nèi)存空間；具有對象數(shù)目呈線性關(guān)系，可伸縮性和較好的聚類質(zhì)量。不足：?每個節(jié)點只能包含有限數(shù)目的條目，工作效率受簇的形狀的影響大。CURE算法：優(yōu)點：對孤立點的處理能力強；?適用于大規(guī)模數(shù)據(jù)處理，伸縮性好，沒有犧牲聚類質(zhì)量；缺點：算法在處理大量數(shù)據(jù)時必須基于抽樣，劃分等技術(shù)。ROCK算法：優(yōu)點：分類恰當(dāng)，可采用隨機抽樣處理數(shù)據(jù)；缺點：最壞的情況下時間復(fù)雜度級數(shù)大?；诿芏鹊木垲愃惴ǎ嚎勺R別具有任意形狀不同大小的簇，自動確定簇的數(shù)目，分離簇和環(huán)境噪聲，一次掃描即可完成聚類，使用空間索引時間復(fù)雜度為O(NlbN)例題：1.假設(shè)描述學(xué)生的信息包含屬性：性別，籍貫，年齡。有兩條記錄p、q及兩個簇C1>C2的信息如下，分別求出記錄和簇彼此之間的距離。(k-means算法的拓展)p=｛男,廣州，18｝q=｛女,深圳，20)C1=｛男：25,女：5；廣州：20,深圳：6,韶關(guān)：4；19)C2=｛男：3,女：12；汕頭：12,深圳：1,湛江：2；24)解：按定義4-3,取x=1,得到的各距離如下：d(p,q)=1+1+20-18=4d(p,C1)=(1-25/30)+(1-20/30)+(19-18)=1.5d(p,C2)=(1-3/15)+(1-0/15)+(24-18)=7.8d(q,C1)=(1-5/30)+(1-6/30)+(20-19)=79/30d(q,C2)=(1-12/15)+(1-1/15)+(24-20)=77/15d(C1,C2)=[1-(25*3+5*12)/(30*15)]+[1-(6*1)/(30*15)]+(24-19)=1003/1504.1什么是聚類？簡單描述如下的聚類方法：劃分方法，層次方法，基于密度的方法，基于模型的方法。為每類方法給出例子。答：聚類是將數(shù)據(jù)劃分為相似對象組的過程，使得同一組中對象相似度最大而不同組中對象相似度最小。主要有以下幾種類型方法：(1)劃分方法給定一個有N個元組或者記錄的數(shù)據(jù)集，分裂法將構(gòu)造K個分組，每一個分組就代表一個聚類，K<No而且這K個分組滿足下列條件：第一，每一個分組至少包含一條記錄；第二，每一條記錄屬于且僅屬于一個分組(注意：這個要求在某些模糊聚類算法中可以放寬)；對于給定的K,算法首先給出一個初始的分組方法，以后通過反復(fù)迭代的方法改變分組，使得每一次改進之后的分組方案都較前一次好，而所謂好的標(biāo)準(zhǔn)就是：同一分組中的記錄越近越好，而不同分組中的記錄越遠(yuǎn)越好。使用這個基本思想的算法有：K-MEANS算法、K-MEDOIDS算法、CLARANS算法。

（2）層次方法這種方法對給定的數(shù)據(jù)集進行層次似的分解，直到某種條件滿足為止。具體又可分為“自底向上”和“自頂向下''兩種方案。例如在“自底向上''方案中，初始時每一個數(shù)據(jù)記錄都組成一個單獨的組，在接下來的迭代中，它把那些相互鄰近的組合并成一個組，直到所有的記錄組成一個分組或者某個條件滿足為止。代表算法有：BIRCH算法、CURE算法、CHAMELEON算法等。（3）基于密度的方法基于密度的方法與其它方法的一個根本區(qū)別是：它不是基于各種各樣的距離，而是基于密度的。這樣就能克服基于距離的算法只能發(fā)現(xiàn)"類圓形''的聚類的缺點。這個方法的指導(dǎo)思想就是：只要一個區(qū)域中的點的密度大過某個閾值，就把它加到與之相近的聚類中去。代表算法有：DBSCAN算法、OPTICS算法、DENCLUE算法等。（4）基于模型的方法基于模型的方法給每一個聚類假定一個模型，然后去尋找能夠很好的滿足這個模型的數(shù)據(jù)。這樣一個模型可能是數(shù)據(jù)點在空間中的密度分布函數(shù)或者其它。它的一個潛在假定就是：目標(biāo)數(shù)據(jù)集是由一系列的概率分布所決定的。基于模型的方法主要有兩類：統(tǒng)計學(xué)方法和神經(jīng)網(wǎng)絡(luò)方法（SOM）。4.10下表中列出了4個點的兩個最近鄰。使用SNN相似度定義，計算每對點之間的SNN相似度 E點第一個近鄰第二個近鄰143234342431答：SNN即共享最近鄰個數(shù)為其相似度。點1和點2的SNN相似度：0（沒有共享最近鄰）點1和點3的SNN相似度：1（共享點4這個最近鄰）點1和點4的SNN相似度：1（共享點3這個最近鄰）點2和點3的SNN相似度：1（共享點4這個最近鄰）點2和點4的SNN相似度：1（共享點3這個最近鄰）點3和點4的SNN相似度：0（沒有共享最近鄰）第五章關(guān)聯(lián)分析.FP-tree（基于FP-growth算法）FP樹的構(gòu)建.Apriori算法的例子(最小支持度計數(shù)閾值=2)SUft.金成貨集文拷厘計效(Cola)3(Diap?r)3(Beer)3{Ham}2L1■交最小支持?計敏.fliSUft.金成貨集文拷厘計效(Cola)3(Diap?r)3(Beer)3{Ham}2L1■交最小支持?計敏.fli集項集

(ColaDiaper}

(ColaBeer)

(ColaHanf"

(DiaperBee「)

(DiaperHam|

{BeerHam)*st七個計度集支紿度計數(shù){ColaDiaper)2(ColsBeer)2(ColaHam!2{DiaperBeer}1(DiaperHam}a{BeerHarrl1支持度計收{(diào)ColaDiaper) 2(ColaBeer) 2{CotaHam) 2(DiaperBeer) 3電口生成候Cl(C(＞『DiaperBe€r).概述：在關(guān)聯(lián)分析中，包含。個或多個項的集合稱為項集，一個包含k個數(shù)據(jù)項的項集就稱為k-項集。若一個項集的支持度大于或等于某個閾值，則稱為頻繁項集。★：(1)產(chǎn)生頻繁項集：發(fā)現(xiàn)滿足最小支持度閾值的所有項集，即頻繁項集。(2)產(chǎn)生規(guī)則：從上一步發(fā)現(xiàn)的頻繁項集中提取大于置信度閾值的規(guī)則，即強規(guī)則。列舉關(guān)聯(lián)規(guī)則在不同領(lǐng)域中應(yīng)用的實例。答：在醫(yī)學(xué)領(lǐng)域：發(fā)現(xiàn)某些癥狀與某種疾病之間的關(guān)聯(lián)，為醫(yī)生進行疾病診斷和治療提供線索；在商業(yè)領(lǐng)域：發(fā)現(xiàn)商品間的聯(lián)系，為商場進行商品促銷及擺放貨架提供輔助決策信息;在地球科學(xué)領(lǐng)域：揭示海洋、陸地和大氣過程之間的關(guān)系。給出如下幾種類型的關(guān)聯(lián)規(guī)則的例子，并說明它們是否是有價值的。(a)高支持度和高置信度的規(guī)則：(b)高支持度和低置信度的規(guī)則；(c)低支持度和低置信度的規(guī)則；(d)低支持度和高置信度的規(guī)則。數(shù)據(jù)集如表舁14所示:表5-14習(xí)題5.3數(shù)據(jù)集^CustomerIDTransactionIDItemsBought10001{a,d,e)10024{a,b,c,e}20012{a,b,d,e}20031{a,c,d,e}30015{b,c,e}30022{b,d,e)40029{c,d}40040{a,b,c}50033{a,d,e}50038{a,b,e}(a)把每一個事務(wù)作為一個購物籃，計算項集{e},{b,d}和{b,d,e}的支持度。(b)利用(a)中結(jié)果計算關(guān)聯(lián)規(guī)則{b,d}-{e}和{e}-{b,d}的置信度。置信度是一個對稱的度量嗎？(c)把每一個用戶購買的所有商品作為一個購物籃，計算項集{e},{b,d}和{b,d,e}的支持度.(d)利用(b)中結(jié)果計算關(guān)聯(lián)規(guī)則{b,d}-{e}和{e}-{b,d}的置信度。置信度是一個對稱的度量嗎？答：(a)s({e})=8/10=0.8;s({b,d})=2/10=0.2;s({b,d,e})=2/10=0.2.(b)c({b,d}->{e})=s({b,d,e})/s({b,d})=0.2/0.2=1;c({e}->{b,d})=s({b,d,e})/s({e})=0.2/0.8=0.25.由于c({b,db>{e})Wc({e}>>{b,d}),所以置信度不是一個對稱的度量。(c)如果把每一個用戶購買所有的所有商品作為一個購物籃，則s({e})=4/5=0.8;s({b,d))=5/5=1;s({b,d,e})=4/5=0.8.(d)利用c中結(jié)果計算關(guān)聯(lián)規(guī)則{b,dL{e}和{e}一{b,d}的置信度，則c({b,d}->{e})=0.8/1=0.8c({e}->{b,d})=0.8/0.8=1置信度不是一個對稱的度量考慮如下的頻繁3-項集：{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{2,3,4},{2,3,5},{3,4,5)。(a)根據(jù)Apriori算法的候選項集生成方法，寫出利用頻繁3-項集生成的所有候選4-項集。(b)寫出經(jīng)過剪枝后的所有候選4-項集答：(a)利用頻繁3-項集生成的所有候選4-項集：{1,2,3,4}{1,2,3,5} {1,2,4,5}{1,3,4,5}{2,3,4,5}(b)經(jīng)過剪枝后的所有候選4-項集：{1,2,3,4}{1,2,3,5)一個數(shù)據(jù)庫有5個事務(wù)，如表5-15所示。設(shè)min_sup=60%,min_conf=80%□表5*15習(xí)題5.7數(shù)據(jù)集當(dāng)務(wù)ID購買的商品T100{M,0,N,K,E,Y)T200{D,0,N,K,E,Y}T300{M,A,K,日T400{M,U,C,K,Y)T500{C,0,0,K,I,E)(a)分別用Apriori算法和FP-growth算法找出所有頻繁項集。比較兩種挖掘方法的效率。(b)比較窮舉法和Apriori算法生成的候選項集的數(shù)量。(c)利用(1)所找出的頻繁項集，生成所有的強關(guān)聯(lián)規(guī)則和對應(yīng)的支持度和置信度。答：(1)頻繁1-項集：M,O,K,E,Y頻繁2-項集：{M,K}, {0,K}, {0,E},{K,Y},{K,E}頻繁3-項集：{O,K,E)(2)窮舉法：M=2k-1=2ii-1