廣工數(shù)據(jù)挖掘復(fù)習(xí)要點(diǎn)匯總

1、-第一章 緒論1.數(shù)據(jù)挖掘要解決的問題：面對高維，復(fù)雜，異構(gòu)的海量數(shù)據(jù)，如何集中獲取有用的信息和知識(shí)。2.數(shù)據(jù)挖掘定義：·技術(shù)層面上：數(shù)據(jù)挖掘就是從大量數(shù)據(jù)提取有用信息的過程；·商業(yè)層面上：數(shù)據(jù)挖掘就是對大量業(yè)務(wù)數(shù)據(jù)進(jìn)展抽取，轉(zhuǎn)換和分析以及建模處理，從中提取輔助商業(yè)決策的關(guān)鍵性數(shù)據(jù)。3.數(shù)據(jù)挖掘的特征：先前未知，有效和實(shí)用。4.數(shù)據(jù)挖掘?qū)ο螅?#183;關(guān)系數(shù)據(jù)庫借助集合代數(shù)等概念和方法來處理數(shù)據(jù)庫中的數(shù)據(jù)·數(shù)據(jù)倉庫(數(shù)據(jù)集合，用于支持管理決策)·事務(wù)數(shù)據(jù)庫每個(gè)記錄代表一個(gè)事務(wù)·空間數(shù)據(jù)庫·事態(tài)數(shù)據(jù)庫和時(shí)間序列數(shù)據(jù)庫·流數(shù)據(jù)

2、·多媒體數(shù)據(jù)庫·文本數(shù)據(jù)庫·萬維數(shù)據(jù)庫5. 數(shù)據(jù)挖掘任務(wù)：分類分析按照*種規(guī)則，聚類分析具有共性，回歸分析，關(guān)聯(lián)分析具有關(guān)聯(lián)規(guī)則，離群點(diǎn)檢測發(fā)現(xiàn)與眾不同的數(shù)據(jù)，演化分析隨時(shí)間變化的數(shù)據(jù)對象的趨勢，序列模式挖掘分析前后序列模式6.數(shù)據(jù)挖掘過程：數(shù)據(jù)清洗，數(shù)據(jù)集成考慮數(shù)據(jù)一致性和冗余，數(shù)據(jù)選擇，數(shù)據(jù)轉(zhuǎn)換，數(shù)據(jù)挖掘，模式評估，知識(shí)表示。例題：1.1 數(shù)據(jù)挖掘處理的對象有哪些.請從實(shí)際生活中舉出至少三種。答：數(shù)據(jù)挖掘處理的對象是*一專業(yè)領(lǐng)域中積累的數(shù)據(jù)，對象既可以來自社會(huì)科學(xué),又可以來自自然科學(xué)產(chǎn)生的數(shù)據(jù),還可以是衛(wèi)星觀測得到的數(shù)據(jù)。數(shù)據(jù)形式和構(gòu)造也各不一樣,可以是傳統(tǒng)的

3、關(guān)系數(shù)據(jù)庫,可以是面向?qū)ο蟮母呒?jí)數(shù)據(jù)庫系統(tǒng),也可以是面向特殊應(yīng)用的數(shù)據(jù)庫,如空間數(shù)據(jù)庫、時(shí)序數(shù)據(jù)庫、文本數(shù)據(jù)庫和多媒體數(shù)據(jù)庫等,還可以是Web 數(shù)據(jù)信息。實(shí)際生活的例子：電信行業(yè)中利用數(shù)據(jù)挖掘技術(shù)進(jìn)展客戶行為分析，包含客戶通話記錄、通話時(shí)間、所開通的效勞等，據(jù)此進(jìn)展客戶群體劃分以及客戶流失性分析。天文領(lǐng)域中利用決策樹等數(shù)據(jù)挖掘方法對上百萬天體數(shù)據(jù)進(jìn)展分類與分析，幫助天文學(xué)家發(fā)現(xiàn)其他未知星體。制造業(yè)中應(yīng)用數(shù)據(jù)挖掘技術(shù)進(jìn)展零部件故障診斷、資源優(yōu)化、生產(chǎn)過程分析等。市場業(yè)中應(yīng)用數(shù)據(jù)挖掘技術(shù)進(jìn)展市場定位、消費(fèi)者分析、輔助制定市場營銷策略等。1.5定義以下數(shù)據(jù)挖掘功能：關(guān)聯(lián)、分類、聚類、演變分析、離群點(diǎn)

4、檢測。使用你熟悉的生活中的數(shù)據(jù)，給出每種數(shù)據(jù)挖掘功能的例子。答：關(guān)聯(lián)是指發(fā)現(xiàn)樣本間或樣本不同屬性間的關(guān)聯(lián)。例如，一個(gè)數(shù)據(jù)挖掘系統(tǒng)可能發(fā)現(xiàn)的關(guān)聯(lián)規(guī)則為：major(*, “puting science)owns(*, “personal puter)support=12%, confidence=98% 其中，* 是一個(gè)表示學(xué)生的變量。該規(guī)則指出主修計(jì)算機(jī)科學(xué)并且擁有一臺(tái)個(gè)人計(jì)算機(jī)的學(xué)生所占比例為12%，同時(shí)，主修計(jì)算機(jī)專業(yè)的學(xué)生有98%擁有個(gè)人計(jì)算機(jī)。分類是構(gòu)造一系列能描述和區(qū)分?jǐn)?shù)據(jù)類型或概念的模型(或功能)，分類被用作預(yù)測目標(biāo)數(shù)據(jù)的類的標(biāo)簽。例如，通過對過去銀行客戶流失與未流失客戶數(shù)據(jù)的分析

5、，得到一個(gè)預(yù)測模型，預(yù)測新客戶是否可能會(huì)流失。聚類是將數(shù)據(jù)劃分為相似對象組的過程，使得同一組中對象相似度最大而不同組中對象相似度最小。例如，通過對*大型超市客戶購物數(shù)據(jù)進(jìn)展聚類，將客戶聚類細(xì)分為低值客戶、高值客戶以及普通客戶等。數(shù)據(jù)演變分析描述和模型化隨時(shí)間變化的對象的規(guī)律或趨勢，盡管這可能包括時(shí)間相關(guān)數(shù)據(jù)的特征化、區(qū)分、關(guān)聯(lián)和相關(guān)分析、分類、或預(yù)測，這種分析的明確特征包括時(shí)間序列數(shù)據(jù)分析、序列或周期模式匹配、和基于相似性的數(shù)據(jù)分析。離群點(diǎn)檢測就是發(fā)現(xiàn)與眾不同的數(shù)據(jù)?？捎糜诎l(fā)現(xiàn)金融領(lǐng)域的欺詐檢測。第二章 數(shù)據(jù)處理根底1.數(shù)據(jù)及數(shù)據(jù)類型：數(shù)據(jù)是數(shù)據(jù)庫存儲(chǔ)的根本對象，數(shù)據(jù)類型：標(biāo)稱屬性，序數(shù)屬性，

6、區(qū)間屬性，比率屬性。2. 數(shù)據(jù)集分為三類：記錄數(shù)據(jù)，基于圖形的數(shù)據(jù)和有序的數(shù)據(jù)集。補(bǔ)充：數(shù)據(jù)統(tǒng)計(jì)特征：均值，中位數(shù)，中列數(shù)數(shù)據(jù)集中最大和最小值的平均值，眾數(shù)出現(xiàn)頻率最高的值，截?cái)嗑抵付?10間的百分位數(shù)p，丟棄高端的和低端的p/2%的數(shù)據(jù)，然后按照計(jì)算均值那樣計(jì)算3. 數(shù)據(jù)挖掘的效果直承受到數(shù)據(jù)源的影響。4.數(shù)據(jù)清理的目的：試圖填充缺失數(shù)據(jù)，去除噪聲并識(shí)別離群點(diǎn)，糾正數(shù)據(jù)中的不一致值。5. 缺失值的處理方法：分析時(shí)忽略元組，分析時(shí)忽略屬性列，估計(jì)缺失值人工填寫缺失數(shù)據(jù)，估計(jì)缺失值自動(dòng)填充缺失數(shù)據(jù)。6.噪聲平滑方法：分箱，聚類。7. 數(shù)據(jù)聚合的目的：將兩個(gè)或多個(gè)數(shù)據(jù)源中的數(shù)據(jù)，存放在一個(gè)一致的

7、數(shù)據(jù)存儲(chǔ)設(shè)備中。8.數(shù)據(jù)變換的容：數(shù)據(jù)泛化把學(xué)科分為理學(xué)和工學(xué)，忽略細(xì)節(jié)，規(guī)化，特征構(gòu)造集中數(shù)據(jù)特征構(gòu)造新的特征，減少特征維數(shù)，數(shù)據(jù)離散化出現(xiàn)了熵計(jì)算。9.數(shù)據(jù)歸約：·維度歸約和特征變換：維度歸約可以刪除不相關(guān)的特征并降低噪聲，降低維度災(zāi)難風(fēng)險(xiǎn)，降低數(shù)據(jù)挖掘的時(shí)間復(fù)雜度和空間復(fù)雜度，特征變幻可以反響出數(shù)據(jù)的不同視角的不同特征。·抽樣：長期用于數(shù)據(jù)的事先調(diào)查和最終的數(shù)據(jù)分析，在數(shù)據(jù)挖掘中，抽樣是選擇數(shù)據(jù)子集進(jìn)展分析的常用方法。1） 無放回的簡單隨機(jī)抽樣方法2） 有放回的簡單隨機(jī)抽樣方法3） 分層抽樣方法·特征選擇：從一組特征的集合中選取最具有代表性的特征子集，使其保

8、存原有數(shù)據(jù)的大局部特征，正確區(qū)分?jǐn)?shù)據(jù)集中的每個(gè)數(shù)據(jù)對象。根據(jù)特征選擇過程與后續(xù)數(shù)據(jù)挖掘任務(wù)的關(guān)聯(lián)可分為三種方法：過濾，封裝和嵌入。根據(jù)是否用到類信息的指導(dǎo)，分為監(jiān)視式，無監(jiān)視式和半監(jiān)視式特征選擇·特征子集選擇的搜索策略：逐步向前選擇從空集開場，逐步添加，逐步向后刪除從整個(gè)屬性集開場，逐個(gè)刪除，向前選擇和向后刪除相結(jié)合,決策樹歸約。特征搜索過程中不可缺少的環(huán)節(jié)就是逐步評估。*數(shù)據(jù)預(yù)處理方法：數(shù)據(jù)清理，數(shù)據(jù)集成，數(shù)據(jù)變換，數(shù)據(jù)歸約，數(shù)據(jù)離散化例題：2.5 假定用于分析的數(shù)據(jù)包含屬性age，數(shù)據(jù)元組中age 的值如下(按遞增序)：13,15,16,16,19,20,20,21,22,22,

9、25,25,25,25,30,33,33,33,35,35,35,35,36,40,45,46,52,70。(a) 使用按箱平均值平滑對以上數(shù)據(jù)進(jìn)展平滑，箱的深度為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

10、箱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)回歸：可以用一個(gè)函數(shù)(如回歸函數(shù))擬合數(shù)據(jù)來光滑數(shù)據(jù)；(2)聚類：可以通過聚類檢測離群點(diǎn)，將類似的值組織成群或簇。直觀地，落在簇集合之外的值視為離群點(diǎn)。2.6 使用習(xí)題2.5 給出的age數(shù)據(jù)，答復(fù)以下問題： (a

11、) 使用min-ma*規(guī)化，將age 值35 轉(zhuǎn)換到0.0，1.0區(qū)間。 (b) 使用z-score 規(guī)化轉(zhuǎn)換age 值35，其中，age 的標(biāo)準(zhǔn)偏差為12.94 年。 (c) 使用小數(shù)定標(biāo)規(guī)化轉(zhuǎn)換age 值35。 (d) 指出對于給定的數(shù)據(jù)，你愿意使用哪種方法。述你的理由。 答：(a)最大值為70，最小值為13，則可將35規(guī)化為：；(b)均值為30，標(biāo)準(zhǔn)差為12.94，則可將35規(guī)化為：；(c)使用小數(shù)定標(biāo)規(guī)化可將35規(guī)化為：；2.17 給定兩個(gè)向量對象，分別表示為p1(22，1，42，10)，p2(20，0，36，8)： (a) 計(jì)算兩個(gè)對象之間的歐幾里得距離(b) 計(jì)算兩個(gè)對象之間的曼哈

12、頓距離 (c) 計(jì)算兩個(gè)對象之間的閔可夫斯基距離，用*=3(d) 計(jì)算兩個(gè)對象之間的切比雪夫距離答：(a) 計(jì)算兩個(gè)對象之間的歐幾里得距離(b) 計(jì)算兩個(gè)對象之間的曼哈頓距離(c) 計(jì)算兩個(gè)對象之間的閔可夫斯基距離，其中參數(shù)r=3(d)切比雪夫距離：=62.8以下是一個(gè)商場所銷售商品的價(jià)格清單(按遞增順序排列，括號(hào)中的數(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ù)集進(jìn)展劃分。答：(1)等寬方法：劃分為3個(gè)數(shù)據(jù)集，每個(gè)數(shù)據(jù)集的寬度為價(jià)格10

13、。價(jià)格在110之間出現(xiàn)次數(shù)為13；價(jià)格在1120之間出現(xiàn)的次數(shù)為24；價(jià)格在2130之間出現(xiàn)的次數(shù)為13。(2)等高方法：劃分為2個(gè)數(shù)據(jù)集，每個(gè)數(shù)據(jù)集的高度為出現(xiàn)的次數(shù)4。出現(xiàn)次數(shù)14之間的價(jià)格為1、8、10、12、14、21、28、30，共8個(gè)數(shù)據(jù)；出現(xiàn)次數(shù)58之間的價(jià)格為5、15、18、20、25，共5個(gè)數(shù)據(jù)。2.9 討論數(shù)據(jù)聚合需要考慮的問題。 答：數(shù)據(jù)聚合需要考慮的問題有：(1)模式識(shí)別：這主要是實(shí)體識(shí)別問題；(2)冗余：一個(gè)屬性是冗余的，即它能由另一個(gè)表導(dǎo)出，如果屬性或維的命名不一致，也可能導(dǎo)致冗余，可以用相關(guān)分析來檢測；(3)數(shù)據(jù)值沖突的檢測與處理：有些屬性因表示比例或編碼不同，會(huì)

14、導(dǎo)致屬性不同。第三章 分類與回歸1.分類：分類是數(shù)據(jù)挖掘中的主要手段，其任務(wù)是對數(shù)據(jù)集進(jìn)展學(xué)習(xí)并構(gòu)造一個(gè)擁有預(yù)測功能的分類模型，用于預(yù)測未知樣本的類標(biāo)號(hào)，把類標(biāo)號(hào)未知的樣本映射到*個(gè)預(yù)先給定的類標(biāo)號(hào)中。2.分類模型學(xué)習(xí)方法：基于決策樹的分類方法，貝葉斯分類方法，k-最近鄰分類方法，神經(jīng)網(wǎng)絡(luò)方法。3.決策樹的概念與構(gòu)建：決策樹是一種樹形構(gòu)造，包括決策節(jié)點(diǎn)，分支節(jié)點(diǎn)和頁節(jié)點(diǎn)三個(gè)局部。·決策節(jié)點(diǎn)：代表*個(gè)測試，通常對應(yīng)帶分類對象的*個(gè)屬性。該屬性上的不同測試結(jié)果對應(yīng)一個(gè)分支。·葉節(jié)點(diǎn)：每個(gè)葉節(jié)點(diǎn)對應(yīng)一個(gè)類標(biāo)號(hào)，表示一種可能的分類結(jié)果。·決策樹的構(gòu)建：1） 屬性的選擇很重

15、要，一般要最大限度地增大樣本集純度2） 獲得大小適合的決策樹3） 使用ID3等經(jīng)典算法構(gòu)建決策樹4.分類模型的評價(jià)：分類過程一般分為兩步：第一步是利用分類算法對訓(xùn)練集進(jìn)展學(xué)習(xí)，建立分類模型；第二步是用分類模型對標(biāo)號(hào)未知的測試數(shù)據(jù)進(jìn)展分類。5.分類模型性能評價(jià)指標(biāo)：1分類準(zhǔn)確率：指模型正確地預(yù)測新的或先前未知的數(shù)據(jù)的類標(biāo)號(hào)的能力。影響分類準(zhǔn)確率的因素：訓(xùn)練數(shù)據(jù)集，記錄的數(shù)目，屬性的數(shù)目，屬性中的信息，測試數(shù)據(jù)集記錄的分布情況2計(jì)算復(fù)雜度：決定著算法執(zhí)行的速率和占用的資源，依賴于具體的實(shí)現(xiàn)細(xì)節(jié)和軟、硬件環(huán)境。3可解釋性：分類結(jié)果只有可解釋性好，容易理解，才能更好地用于決策支持。4可伸縮性。5穩(wěn)定性

16、：指不會(huì)隨著數(shù)據(jù)的變化而發(fā)生劇烈變化。6強(qiáng)壯性：指數(shù)據(jù)集含有噪聲和空缺值的情況下，分類器正確分類數(shù)據(jù)的能力。6.分類模型的誤差：1訓(xùn)練誤差和泛化誤差。7.評估分類模型的性能的方法：1保持方法：以無放回抽樣方式把數(shù)據(jù)集分為兩個(gè)相互獨(dú)立的子集，訓(xùn)練集2/3和測試集1/3；2隨機(jī)子抽樣：保持方法的屢次迭代；3k-折穿插驗(yàn)證。例題：3.1 考慮表3-23所示二元分類問題的數(shù)據(jù)集。表3-23 習(xí)題3.4數(shù)據(jù)集AB類標(biāo)號(hào)TF+TT+TT+TF-TT+FF-FF-FF-TT-TF-(1) 計(jì)算按照屬性A和B劃分時(shí)的信息增益。決策樹歸納算法將會(huì)選擇那個(gè)屬性.(2) 計(jì)算按照屬性A和B劃分時(shí)Gini系數(shù)。決策樹

17、歸納算法將會(huì)選擇那個(gè)屬性.答：按照屬性A和B劃分時(shí)，數(shù)據(jù)集可分為如下兩種情況：A=TA=F+40-33B=TB=F+31-15劃分前樣本集的信息熵為 E=-0.4log220.6=0.9710按照屬性A劃分樣本集分別得到的兩個(gè)子集(A取值T和A取值F)的信息熵分別為:按照屬性A劃分樣本集得到的信息增益為：按照屬性B劃分樣本集分別得到的兩個(gè)子集(B取值T和B取值F)的信息熵分別為:按照屬性B劃分樣本集得到的信息增益為：因此，決策樹歸納算法將會(huì)選擇屬性A。(2) 劃分前的Gini值為G=1-0.42-0.62=0.48按照屬性A劃分時(shí)Gini指標(biāo):Gini增益按照屬性B劃分時(shí)Gini指標(biāo):Gini

18、增益因此，決策樹歸納算法將會(huì)選擇屬性B。3.2 考慮表3-24數(shù)據(jù)集，請完成以下問題：表3-24 習(xí)題3.7數(shù)據(jù)集記錄號(hào)ABC類1000+2001-3011-4011-5001+6101+7101-8101-9111+10101+(1) 估計(jì)條件概率，。(2) 根據(jù)(1)中的條件概率，使用樸素貝葉斯方法預(yù)測測試樣本(A=0，B=1，C=0)的類標(biāo)號(hào)；(3) 使用Laplace估計(jì)方法，其中p=1/2，l=4，估計(jì)條件概率，。(4) 同(2)，使用(3)中的條件概率(5) 比較估計(jì)概率的兩種方法，哪一種更好，為什么.答：(1)=3/5=1/5=2/5=2/5=1(2) 假設(shè)P(A=0,B=1,C

19、=0)=K則K屬于兩個(gè)類的概率為：P(+|A=0,B=1,C=0)=P(A=0,B=1,C=0|+)×P(+)/K(貝葉斯算法)=P(A=0|+)P(B|+)P(C=0|+)×P(+)/K=0.4×0.2×0.2×0.5/K=0.008/KP(-|A=0,B=1,C=0)=P(A=0,B=1,C=0|-)×P(-)/K=P(A=0|-)P(B|-)P(C=0|-)×P(-)/K=0.4×0.2×0×0.5/K=0/K則得到，此樣本的類標(biāo)號(hào)是+。(3)P(A|+)=(3+2)/(5+4)=5/9P

20、(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屬于兩個(gè)類的概率為：P(+|A=0,B=1,C=0)=P(A=0,B=1,C=0)×P(+)/K=P(A=0|+)P(B|+)P(C=0|+)×P(+)/K=(4/9) ×(1/3) ×(1/3) ×0.5/K=0.0247/KP(-|A=0,B=1,C=0)=P(A=0,B=1,C=0)×P(-)/K=P(A=0|

21、-)P(B|-)P(C=0|-)×P(-)/K=(5/9) ×(4/9) ×(2/9) ×0.5/K=0.0274/K則得到，此樣本的類標(biāo)號(hào)是-。(5)當(dāng)條件概率為0的時(shí)候，條件概率的預(yù)測用Laplace估計(jì)方法比較好，因?yàn)槲覀儾幌胝麄€(gè)條件概率計(jì)算結(jié)果為0.第四章 聚類分析1.聚類：聚類就是將數(shù)據(jù)集劃分為由假設(shè)干相似對象組成的多個(gè)組或簇的過程，使得同一組中的對象的相似度最大化，不同組中的相似度最小化。或者說聚類是由彼此相似的一組對象構(gòu)成的集合。分類：分類是數(shù)據(jù)挖掘中的主要手段，其任務(wù)是對數(shù)據(jù)集進(jìn)展學(xué)習(xí)并構(gòu)造一個(gè)擁有預(yù)測功能的分類模型，用于預(yù)測未知樣本的類

22、標(biāo)號(hào)，把類標(biāo)號(hào)未知的樣本映射到*個(gè)預(yù)先給定的類標(biāo)號(hào)中。記：聚類和分類的區(qū)別2.典型的聚類分析任務(wù)包括的步驟：1模式表示聚類算法的根底，2適合于數(shù)據(jù)領(lǐng)域的模式相似性定義(是聚類分析最根本的問題)，3聚類或者劃分算法聚類分析的核心，4數(shù)據(jù)摘要如有必要，5輸出結(jié)果的評估，有效性的評估如有必要3. 數(shù)據(jù)挖掘?qū)垲惖牡湫鸵螅?可伸縮性，2處理不同類型屬性的能力3發(fā)現(xiàn)任意形狀的聚類4用于決定輸入?yún)?shù)的領(lǐng)域知識(shí)最小化5處理噪聲數(shù)據(jù)的能力6對輸入記錄的順序不敏感7高維度8基于約束的聚類9可解釋性和可用性。4.典型聚類方法：1劃分方法每個(gè)劃分表示一個(gè)聚類2層次方法將數(shù)據(jù)對象組成一個(gè)聚類樹3基于密度的方法絕大多

23、數(shù)劃分方法都是基于對象之間的距離大小進(jìn)展聚類4基于模型的方法試圖將給定數(shù)據(jù)與*個(gè)數(shù)學(xué)模型搭成最正確擬合5基于圖的聚類算法利用圖的許多重要性質(zhì)和特性5.k-means算法，層次聚類算法的優(yōu)缺點(diǎn)：1k-means算法：優(yōu)點(diǎn)：算法描述容易，實(shí)現(xiàn)簡單快速；缺乏：·簇的個(gè)數(shù)要預(yù)先給定，·對初始值的依賴極大·不適合大量數(shù)據(jù)的處理·對噪聲點(diǎn)和離群點(diǎn)很敏感·很難檢測到“自然的簇。2層次聚類算法：BIRCH算法：優(yōu)點(diǎn)：利用聚類特征樹概括了聚類的有用信息，節(jié)省存空間；具有對象數(shù)目呈線性關(guān)系，可伸縮性和較好的聚類質(zhì)量。缺乏：·每個(gè)節(jié)點(diǎn)只能包含有限數(shù)目的條目

24、，工作效率受簇的形狀的影響大。CURE算法：優(yōu)點(diǎn)：對孤立點(diǎn)的處理能力強(qiáng)；·適用于大規(guī)模數(shù)據(jù)處理，伸縮性好，沒有犧牲聚類質(zhì)量；缺點(diǎn)：算法在處理大量數(shù)據(jù)時(shí)必須基于抽樣，劃分等技術(shù)。ROCK算法：優(yōu)點(diǎn)：分類恰當(dāng)，可采用隨機(jī)抽樣處理數(shù)據(jù)；缺點(diǎn)：最壞的情況下時(shí)間復(fù)雜度級(jí)數(shù)大?；诿芏鹊木垲愃惴ǎ嚎勺R(shí)別具有任意形狀不同大小的簇，自動(dòng)確定簇的數(shù)目，分離簇和環(huán)境噪聲，一次掃描即可完成聚類，使用空間索引時(shí)間復(fù)雜度為O(NlbN)例題：1.假設(shè)描述學(xué)生的信息包含屬性：性別，籍貫，年齡。有兩條記錄p、q及兩個(gè)簇C1、C2的信息如下，分別求出記錄和簇彼此之間的距離。k-means算法的拓展p=男，18 q=

25、女，20C1=男：25，女：5；：20，：6，：4；19C2=男：3，女：12；：12，：1，：2；24解：按定義4-3，取*=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 什么是聚類.簡單描述如下的聚類方法：劃

26、分方法，層次方法，基于密度的方法，基于模型的方法。為每類方法給出例子。答：聚類是將數(shù)據(jù)劃分為相似對象組的過程，使得同一組中對象相似度最大而不同組中對象相似度最小。主要有以下幾種類型方法：(1)劃分方法給定一個(gè)有N個(gè)元組或者記錄的數(shù)據(jù)集，分裂法將構(gòu)造K個(gè)分組，每一個(gè)分組就代表一個(gè)聚類，K<N。而且這K個(gè)分組滿足以下條件：第一，每一個(gè)分組至少包含一條記錄；第二，每一條記錄屬于且僅屬于一個(gè)分組(注意：這個(gè)要求在*些模糊聚類算法中可以放寬)；對于給定的K，算法首先給出一個(gè)初始的分組方法，以后通過反復(fù)迭代的方法改變分組，使得每一次改進(jìn)之后的分組方案都較前一次好，而所謂好的標(biāo)準(zhǔn)就是：同一分組中的記錄

27、越近越好，而不同分組中的記錄越遠(yuǎn)越好。使用這個(gè)根本思想的算法有：K-MEANS算法、K-MEDOIDS算法、CLARANS算法。(2)層次方法這種方法對給定的數(shù)據(jù)集進(jìn)展層次似的分解，直到*種條件滿足為止。具體又可分為“自底向上和“自頂向下兩種方案。例如在“自底向上方案中，初始時(shí)每一個(gè)數(shù)據(jù)記錄都組成一個(gè)單獨(dú)的組，在接下來的迭代中，它把那些相互鄰近的組合并成一個(gè)組，直到所有的記錄組成一個(gè)分組或者*個(gè)條件滿足為止。代表算法有：BIRCH算法、CURE算法、CHAMELEON算法等。(3)基于密度的方法基于密度的方法與其它方法的一個(gè)根本區(qū)別是：它不是基于各種各樣的距離，而是基于密度的。這樣就能抑制基于

28、距離的算法只能發(fā)現(xiàn)“類圓形的聚類的缺點(diǎn)。這個(gè)方法的指導(dǎo)思想就是：只要一個(gè)區(qū)域中的點(diǎn)的密度大過*個(gè)閾值，就把它加到與之相近的聚類中去。代表算法有：DBSCAN算法、OPTICS算法、DENCLUE算法等。(4)基于模型的方法基于模型的方法給每一個(gè)聚類假定一個(gè)模型，然后去尋找能夠很好的滿足這個(gè)模型的數(shù)據(jù)。這樣一個(gè)模型可能是數(shù)據(jù)點(diǎn)在空間中的密度分布函數(shù)或者其它。它的一個(gè)潛在假定就是：目標(biāo)數(shù)據(jù)集是由一系列的概率分布所決定的。基于模型的方法主要有兩類：統(tǒng)計(jì)學(xué)方法和神經(jīng)網(wǎng)絡(luò)方法(SOM)。4.10 下表中列出了4個(gè)點(diǎn)的兩個(gè)最近鄰。使用SNN相似度定義，計(jì)算每對點(diǎn)之間的SNN相似度。點(diǎn)第一個(gè)近鄰第二個(gè)近鄰1

29、43234342431答：SNN即共享最近鄰個(gè)數(shù)為其相似度。點(diǎn)1和點(diǎn)2的SNN相似度：0沒有共享最近鄰點(diǎn)1和點(diǎn)3的SNN相似度：1共享點(diǎn)4這個(gè)最近鄰點(diǎn)1和點(diǎn)4的SNN相似度：1共享點(diǎn)3這個(gè)最近鄰點(diǎn)2和點(diǎn)3的SNN相似度：1共享點(diǎn)4這個(gè)最近鄰點(diǎn)2和點(diǎn)4的SNN相似度：1共享點(diǎn)3這個(gè)最近鄰點(diǎn)3和點(diǎn)4的SNN相似度：0沒有共享最近鄰第五章 關(guān)聯(lián)分析1.FP-tree基于FP-growth算法2.Apriori算法的例子(最小支持度計(jì)數(shù)閾值=2)3.概述：在關(guān)聯(lián)分析中，包含0個(gè)或多個(gè)項(xiàng)的集合稱為項(xiàng)集，一個(gè)包含k個(gè)數(shù)據(jù)項(xiàng)的項(xiàng)集就稱為k-項(xiàng)集。假設(shè)一個(gè)項(xiàng)集的支持度大于或等于*個(gè)閾值，則稱為頻繁項(xiàng)集。*：1

30、產(chǎn)生頻繁項(xiàng)集：發(fā)現(xiàn)滿足最小支持度閾值的所有項(xiàng)集，即頻繁項(xiàng)集。 2產(chǎn)生規(guī)則：從上一步發(fā)現(xiàn)的頻繁項(xiàng)集中提取大于置信度閾值的規(guī)則，即強(qiáng)規(guī)則。5.1 列舉關(guān)聯(lián)規(guī)則在不同領(lǐng)域中應(yīng)用的實(shí)例。答：在醫(yī)學(xué)領(lǐng)域：發(fā)現(xiàn)*些病癥與*種疾病之間的關(guān)聯(lián)，為醫(yī)生進(jìn)展疾病診斷和治療提供線索； 在商業(yè)領(lǐng)域：發(fā)現(xiàn)商品間的聯(lián)系，為商場進(jìn)展商品促銷及擺放貨架提供輔助決策信息； 在地球科學(xué)領(lǐng)域：提醒海洋、陸地和大氣過程之間的關(guān)系。5.2 給出如下幾種類型的關(guān)聯(lián)規(guī)則的例子，并說明它們是否是有價(jià)值的。(a)高支持度和高置信度的規(guī)則；(b)高支持度和低置信度的規(guī)則；(c)低支持度和低置信度的規(guī)則；(d)低支持度和高置信度的規(guī)則。5.3 數(shù)

31、據(jù)集如表5-14所示：表5-14 習(xí)題5.3數(shù)據(jù)集Customer IDTransaction IDItems Bought11223344550001002400120031001500220029004000330038a, d, ea, b, c, ea, b, d, ea, c, d, eb, c, eb, d, ec, da, b, ca, d, ea, b, e(a) 把每一個(gè)事務(wù)作為一個(gè)購物籃，計(jì)算項(xiàng)集e, b, d和b, d, e的支持度。(b) 利用(a)中結(jié)果計(jì)算關(guān)聯(lián)規(guī)則b, de 和 eb, d的置信度。置信度是一個(gè)對稱的度量嗎.(c) 把每一個(gè)用戶購置的所有商品作為一個(gè)

32、購物籃，計(jì)算項(xiàng)集e, b, d和b, d, e的支持度。(d) 利用(b)中結(jié)果計(jì)算關(guān)聯(lián)規(guī)則b, de 和 eb, d的置信度。置信度是一個(gè)對稱的度量嗎.答：(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,d->e)c(e->b,d)，所以置信度不是一個(gè)對稱的度量。 (c)如果把每一個(gè)用戶購置所有的

33、所有商品作為一個(gè)購物籃，則 s(e) = 4/5 =0.8 ; s(b,d) = 5/5 = 1 ; s(b,d,e) = 4/5 = 0.8.(d) 利用c中結(jié)果計(jì)算關(guān)聯(lián)規(guī)則b, de 和 eb, d的置信度,則 c(b,d->e) = 0.8/1 = 0.8 c(e->b,d) = 0.8/0.8 = 1置信度不是一個(gè)對稱的度量5.6 考慮如下的頻繁3-項(xiàng)集：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算法的候選項(xiàng)集生成方法，寫出利用頻繁3-項(xiàng)集生成的所有候選4-項(xiàng)集。(

34、b)寫出經(jīng)過剪枝后的所有候選4-項(xiàng)集答：(a)利用頻繁3-項(xiàng)集生成的所有候選4-項(xiàng)集： 1,2,3,4 1,2,3,5 1,2,4,5 1,3,4,5 2,3,4,5 (b)經(jīng)過剪枝后的所有候選4-項(xiàng)集： 1,2,3,4 1,2,3,55.7 一個(gè)數(shù)據(jù)庫有5個(gè)事務(wù)，如表5-15所示。設(shè)min_sup=60%，min_conf = 80%。表5-15 習(xí)題5.7數(shù)據(jù)集事務(wù)ID購置的商品T100T200T300T400T500M, O, N, K, E, YD, O, N, K, E, YM, A, K, EM, U, C, K, YC, O, O, K, I ,E(a) 分別用Apriori算法和FP-growth算法找出所有頻繁項(xiàng)集。比較兩種挖掘方法的效率。(b) 比較窮舉法和Apriori算法生成的候選項(xiàng)集的數(shù)量。(c) 利用(1)所找出的頻繁項(xiàng)集，生成所有的強(qiáng)關(guān)聯(lián)規(guī)則和對應(yīng)的支持度和置信度。答：(1) 頻繁1-項(xiàng)集：M,O,K,E,Y 頻繁2-項(xiàng)集：M,K， O,K， O,E，K,Y，K,E 頻繁3-項(xiàng)集：O,K,E (2)窮舉法：M=2k-1=211-1=2047 Apriori算法：23(3) O,K>E，支持度0.6，置信度1 O,E>k，支持度0