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

1、第一章 緒論1.數(shù)據(jù)挖掘要解決的問題：面對高維，復(fù)雜，異構(gòu)的海量數(shù)據(jù)，如何集中獲取有用的信息和知識。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ù)挖掘的特征：先前未知，有效和實用。4.數(shù)據(jù)挖掘?qū)ο螅?#183;關(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ù)庫·

2、流數(shù)據(jù)·多媒體數(shù)據(jù)庫·文本數(shù)據(jù)庫·萬維數(shù)據(jù)庫5. 數(shù)據(jù)挖掘任務(wù)：分類分析（按照某種規(guī)則），聚類分析（具有共性），回歸分析，關(guān)聯(lián)分析（具有關(guān)聯(lián)規(guī)則），離群點檢測（發(fā)現(xiàn)與眾不同的數(shù)據(jù)），演化分析（隨時間變化的數(shù)據(jù)對象的趨勢），序列模式挖掘（分析前后序列模式）6.數(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ù)

3、形式和結(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ù)進(jìn)行客戶行為分析，包含客戶通話記錄、通話時間、所開通的服務(wù)等，據(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)行市場定位、消費者分析、輔助制定市場營銷策略等。1.5 定義下列數(shù)據(jù)挖掘功能

4、：關(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, “computing science”)owns(X, “personal computer”)support=12%, confidence=98% 其中，X 是一個表示學(xué)生的變量。該規(guī)則指出主修計算機(jī)科學(xué)并且擁有一臺個人計算機(jī)的學(xué)生所占比例為12%，同時，主修計算機(jī)專業(yè)的學(xué)生有98%擁有個人計算機(jī)。分類是構(gòu)造一系列能描述和區(qū)分?jǐn)?shù)據(jù)類型或概念的模型(或功能)，分類被用作預(yù)測目標(biāo)數(shù)據(jù)的類的標(biāo)簽

5、。例如，通過對過去銀行客戶流失與未流失客戶數(shù)據(jù)的分析，得到一個預(yù)測模型，預(yù)測新客戶是否可能會流失。聚類是將數(shù)據(jù)劃分為相似對象組的過程，使得同一組中對象相似度最大而不同組中對象相似度最小。例如，通過對某大型超市客戶購物數(shù)據(jù)進(jìn)行聚類，將客戶聚類細(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ǔ)1.數(shù)據(jù)及數(shù)據(jù)類型：數(shù)據(jù)是

6、數(shù)據(jù)庫存儲的基本對象，數(shù)據(jù)類型：標(biāo)稱屬性，序數(shù)屬性，區(qū)間屬性，比率屬性。2. 數(shù)據(jù)集分為三類：記錄數(shù)據(jù)，基于圖形的數(shù)據(jù)和有序的數(shù)據(jù)集。補(bǔ)充：數(shù)據(jù)統(tǒng)計特征：均值，中位數(shù)，中列數(shù)（數(shù)據(jù)集中最大和最小值的平均值），眾數(shù)（出現(xiàn)頻率最高的值），截斷均值（指定010間的百分位數(shù)p，丟棄高端的和低端的（p/2）%的數(shù)據(jù)，然后按照計算均值那樣計算）3. 數(shù)據(jù)挖掘的效果直接受到數(shù)據(jù)源的影響。4.數(shù)據(jù)清理的目的：試圖填充缺失數(shù)據(jù)，去除噪聲并識別離群點，糾正數(shù)據(jù)中的不一致值。5. 缺失值的處理方法：（分析時）忽略元組，（分析時）忽略屬性列，（估計缺失值）人工填寫缺失數(shù)據(jù)，（估計缺失值）自動填充缺失數(shù)據(jù)。6.噪聲平滑

7、方法：分箱，聚類。7. 數(shù)據(jù)聚合的目的：將兩個或多個數(shù)據(jù)源中的數(shù)據(jù)，存放在一個一致的數(shù)據(jù)存儲設(shè)備中。8.數(shù)據(jù)變換的內(nèi)容：數(shù)據(jù)泛化（把學(xué)科分為理學(xué)和工學(xué)，忽略細(xì)節(jié)），規(guī)范化，特征構(gòu)造（集中數(shù)據(jù)特征構(gòu)造新的特征，減少特征維數(shù)），數(shù)據(jù)離散化（出現(xiàn)了熵計算）。9.數(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ù)子集進(jìn)行分析的常用方法。1） 無放回的簡單隨機(jī)抽樣方法2） 有放回的簡單隨機(jī)

8、抽樣方法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ù)離散化例題：2.5 假定用于分析的數(shù)據(jù)包含屬

9、性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,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，且箱的深

10、度為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)聚類：可以通過聚類檢測離群點，將類似的值

11、組織成群或簇。直觀地，落在簇集合之外的值視為離群點。2.6 使用習(xí)題2.5 給出的age數(shù)據(jù)，回答以下問題： (a) 使用min-max 規(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 給定兩個向量對象

12、，分別表示為p1(22，1，42，10)，p2(20，0，36，8)： (a) 計算兩個對象之間的歐幾里得距離 (b) 計算兩個對象之間的曼哈頓距離 (c) 計算兩個對象之間的閔可夫斯基距離，用x=3(d) 計算兩個對象之間的切比雪夫距離答：(a) 計算兩個對象之間的歐幾里得距離(b) 計算兩個對象之間的曼哈頓距離(c) 計算兩個對象之間的閔可夫斯基距離，其中參數(shù)r=3(d)切比雪夫距離：=62.8以下是一個商場所銷售商品的價格清單(按遞增順序排列，括號中的數(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(

13、5)、28、30(3)。請分別用等寬的方法和等高的方法對上面的數(shù)據(jù)集進(jìn)行劃分。答：(1)等寬方法：劃分為3個數(shù)據(jù)集，每個數(shù)據(jù)集的寬度為價格10。價格在110之間出現(xiàn)次數(shù)為13；價格在1120之間出現(xiàn)的次數(shù)為24；價格在2130之間出現(xiàn)的次數(shù)為13。(2)等高方法：劃分為2個數(shù)據(jù)集，每個數(shù)據(jù)集的高度為出現(xiàn)的次數(shù)4。出現(xiàn)次數(shù)14之間的價格為1、8、10、12、14、21、28、30，共8個數(shù)據(jù)；出現(xiàn)次數(shù)58之間的價格為5、15、18、20、25，共5個數(shù)據(jù)。2.9 討論數(shù)據(jù)聚合需要考慮的問題。 答：數(shù)據(jù)聚合需要考慮的問題有：(1)模式識別：這主要是實體識別問題；(2)冗余：一個屬性是冗余的，即它能

14、由另一個表導(dǎo)出，如果屬性或維的命名不一致，也可能導(dǎo)致冗余，可以用相關(guān)分析來檢測；(3)數(shù)據(jù)值沖突的檢測與處理：有些屬性因表示比例或編碼不同，會導(dǎo)致屬性不同。第三章 分類與回歸1.分類：分類是數(shù)據(jù)挖掘中的主要手段，其任務(wù)是對數(shù)據(jù)集進(jìn)行學(xué)習(xí)并構(gòu)造一個擁有預(yù)測功能的分類模型，用于預(yù)測未知樣本的類標(biāo)號，把類標(biāo)號未知的樣本映射到某個預(yù)先給定的類標(biāo)號中。2.分類模型學(xué)習(xí)方法：基于決策樹的分類方法，貝葉斯分類方法，k-最近鄰分類方法，神經(jīng)網(wǎng)絡(luò)方法。3.決策樹的概念與構(gòu)建：決策樹是一種樹形結(jié)構(gòu)，包括決策節(jié)點，分支節(jié)點和頁節(jié)點三個部分。·決策節(jié)點：代表某個測試，通常對應(yīng)帶分類對象的某個屬性。該屬性上的

15、不同測試結(jié)果對應(yīng)一個分支。·葉節(jié)點：每個葉節(jié)點對應(yīng)一個類標(biāo)號，表示一種可能的分類結(jié)果。·決策樹的構(gòu)建：1） 屬性的選擇（很重要，一般要最大限度地增大樣本集純度）2） 獲得大小適合的決策樹3） 使用ID3等經(jīng)典算法構(gòu)建決策樹4.分類模型的評價：分類過程一般分為兩步：第一步是利用分類算法對訓(xùn)練集進(jìn)行學(xué)習(xí)，建立分類模型；第二步是用分類模型對標(biāo)號未知的測試數(shù)據(jù)進(jìn)行分類。5.分類模型性能評價指標(biāo)：（1）分類準(zhǔn)確率：指模型正確地預(yù)測新的或先前未知的數(shù)據(jù)的類標(biāo)號的能力。（影響分類準(zhǔn)確率的因素：訓(xùn)練數(shù)據(jù)集，記錄的數(shù)目，屬性的數(shù)目，屬性中的信息，測試數(shù)據(jù)集記錄的分布情況）（2）計算復(fù)雜度：決

16、定著算法執(zhí)行的速率和占用的資源，依賴于具體的實現(xiàn)細(xì)節(jié)和軟、硬件環(huán)境。（3）可解釋性：分類結(jié)果只有可解釋性好，容易理解，才能更好地用于決策支持。（4）可伸縮性。（5）穩(wěn)定性：指不會隨著數(shù)據(jù)的變化而發(fā)生劇烈變化。（6）強(qiáng)壯性：指數(shù)據(jù)集含有噪聲和空缺值的情況下，分類器正確分類數(shù)據(jù)的能力。6.分類模型的誤差：（1）訓(xùn)練誤差和泛化誤差。7.評估分類模型的性能的方法：（1）保持方法：以無放回抽樣方式把數(shù)據(jù)集分為兩個相互獨立的子集，訓(xùn)練集（2/3）和測試集（1/3）；（2）隨機(jī)子抽樣：保持方法的多次迭代；（3）k-折交叉驗證。例題：3.1 考慮表3-23所示二元分類問題的數(shù)據(jù)集。表3-23 習(xí)題3.4數(shù)據(jù)集

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

18、劃分樣本集得到的信息增益為：因此，決策樹歸納算法將會選擇屬性A。(2) 劃分前的Gini值為G=1-0.42-0.62=0.48按照屬性A劃分時Gini指標(biāo):Gini增益按照屬性B劃分時Gini指標(biāo):Gini增益因此，決策樹歸納算法將會選擇屬性B。3.2 考慮表3-24數(shù)據(jù)集，請完成以下問題：表3-24 習(xí)題3.7數(shù)據(jù)集記錄號ABC類1000+2001-3011-4011-5001+6101+7101-8101-9111+10101+(1) 估計條件概率，。(2) 根據(jù)(1)中的條件概率，使用樸素貝葉斯方法預(yù)測測試樣本(A=0，B=1，C=0)的類標(biāo)號；(3) 使用Laplace估計方法，其中

19、p=1/2，l=4，估計條件概率，。(4) 同(2)，使用(3)中的條件概率(5) 比較估計概率的兩種方法，哪一種更好，為什么？答：(1) =3/5=1/5=2/5=2/5=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|+)×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=

20、0|-)P(B|-)P(C=0|-)×P(-)/K=0.4×0.2×0×0.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=0)×P(+)/K=P(A=0|+)P(B|+)P(C=0|+)×P

21、(+)/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|-)P(B|-)P(C=0|-)×P(-)/K=(5/9) ×(4/9) ×(2/9) ×0.5/K=0.0274/K則得到，此樣本的類標(biāo)號是-。(5) 當(dāng)條件概率為0的時候，條件概率的預(yù)測用Laplace估計方法比較好，因為我們不想整個條件概率計算結(jié)果為0.第四章 聚類分析1.聚類：聚類就是將數(shù)據(jù)集劃分為由若干相似對象組成的多個組或簇的過程，使

22、得同一組中的對象的相似度最大化，不同組中的相似度最小化?；蛘哒f聚類是由彼此相似的一組對象構(gòu)成的集合。分類：分類是數(shù)據(jù)挖掘中的主要手段，其任務(wù)是對數(shù)據(jù)集進(jìn)行學(xué)習(xí)并構(gòu)造一個擁有預(yù)測功能的分類模型，用于預(yù)測未知樣本的類標(biāo)號，把類標(biāo)號未知的樣本映射到某個預(yù)先給定的類標(biāo)號中。記：聚類和分類的區(qū)別2.典型的聚類分析任務(wù)包括的步驟：1）模式表示（聚類算法的基礎(chǔ)），2）適合于數(shù)據(jù)領(lǐng)域的模式相似性定義(是聚類分析最基本的問題)，3）聚類或者劃分算法（聚類分析的核心），4）數(shù)據(jù)摘要（如有必要），5）輸出結(jié)果的評估，有效性的評估（如有必要）3. 數(shù)據(jù)挖掘?qū)垲惖牡湫鸵螅?）可伸縮性，2）處理不同類型屬性的能力3）

23、發(fā)現(xiàn)任意形狀的聚類4）用于決定輸入?yún)?shù)的領(lǐng)域知識最小化5）處理噪聲數(shù)據(jù)的能力6）對輸入記錄的順序不敏感7）高維度8）基于約束的聚類9）可解釋性和可用性。4.典型聚類方法：1）劃分方法（每個劃分表示一個聚類）2）層次方法（將數(shù)據(jù)對象組成一個聚類樹）3）基于密度的方法（絕大多數(shù)劃分方法都是基于對象之間的距離大小進(jìn)行聚類）4）基于模型的方法（試圖將給定數(shù)據(jù)與某個數(shù)學(xué)模型搭成最佳擬合）5）基于圖的聚類算法（利用圖的許多重要性質(zhì)和特性）5.k-means算法，層次聚類算法的優(yōu)缺點：（1）k-means算法：優(yōu)點：算法描述容易，實現(xiàn)簡單快速；不足：·簇的個數(shù)要預(yù)先給定，·對初始值的依賴

24、極大·不適合大量數(shù)據(jù)的處理·對噪聲點和離群點很敏感·很難檢測到“自然的”簇。（2）層次聚類算法：BIRCH算法：優(yōu)點：利用聚類特征樹概括了聚類的有用信息，節(jié)省內(nèi)存空間；具有對象數(shù)目呈線性關(guān)系，可伸縮性和較好的聚類質(zhì)量。不足：·每個節(jié)點只能包含有限數(shù)目的條目，工作效率受簇的形狀的影響大。CURE算法：優(yōu)點：對孤立點的處理能力強(qiáng)；·適用于大規(guī)模數(shù)據(jù)處理，伸縮性好，沒有犧牲聚類質(zhì)量；缺點：算法在處理大量數(shù)據(jù)時必須基于抽樣，劃分等技術(shù)。ROCK算法：優(yōu)點：分類恰當(dāng)，可采用隨機(jī)抽樣處理數(shù)據(jù)；缺點：最壞的情況下時間復(fù)雜度級數(shù)大?；诿芏鹊木垲愃惴ǎ嚎勺R別具

25、有任意形狀不同大小的簇，自動確定簇的數(shù)目，分離簇和環(huán)境噪聲，一次掃描即可完成聚類，使用空間索引時間復(fù)雜度為O(NlbN)例題：1.假設(shè)描述學(xué)生的信息包含屬性：性別，籍貫，年齡。有兩條記錄p、q及兩個簇C1、C2的信息如下，分別求出記錄和簇彼此之間的距離。（k-means算法的拓展）p=男，廣州，18 q=女，深圳，20C1=男：25，女：5；廣州：20，深圳：6，韶關(guān)：4；19C2=男：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.5

26、d(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)劃

27、分方法給定一個有N個元組或者記錄的數(shù)據(jù)集，分裂法將構(gòu)造K個分組，每一個分組就代表一個聚類，K<N。而且這K個分組滿足下列條件：第一，每一個分組至少包含一條記錄；第二，每一條記錄屬于且僅屬于一個分組(注意：這個要求在某些模糊聚類算法中可以放寬)；對于給定的K，算法首先給出一個初始的分組方法，以后通過反復(fù)迭代的方法改變分組，使得每一次改進(jìn)之后的分組方案都較前一次好，而所謂好的標(biāo)準(zhǔn)就是：同一分組中的記錄越近越好，而不同分組中的記錄越遠(yuǎn)越好。使用這個基本思想的算法有：K-MEANS算法、K-MEDOIDS算法、CLARANS算法。(2)層次方法這種方法對給定的數(shù)據(jù)集進(jìn)行層次似的分解，直到某種條件

28、滿足為止。具體又可分為“自底向上”和“自頂向下”兩種方案。例如在“自底向上”方案中，初始時每一個數(shù)據(jù)記錄都組成一個單獨的組，在接下來的迭代中，它把那些相互鄰近的組合并成一個組，直到所有的記錄組成一個分組或者某個條件滿足為止。代表算法有：BIRCH算法、CURE算法、CHAMELEON算法等。(3)基于密度的方法基于密度的方法與其它方法的一個根本區(qū)別是：它不是基于各種各樣的距離，而是基于密度的。這樣就能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點。這個方法的指導(dǎo)思想就是：只要一個區(qū)域中的點的密度大過某個閾值，就把它加到與之相近的聚類中去。代表算法有：DBSCAN算法、OPTICS算法、DEN

29、CLUE算法等。(4)基于模型的方法基于模型的方法給每一個聚類假定一個模型，然后去尋找能夠很好的滿足這個模型的數(shù)據(jù)。這樣一個模型可能是數(shù)據(jù)點在空間中的密度分布函數(shù)或者其它。它的一個潛在假定就是：目標(biāo)數(shù)據(jù)集是由一系列的概率分布所決定的?；谀Ｐ偷姆椒ㄖ饕袃深悾航y(tǒng)計學(xué)方法和神經(jīng)網(wǎng)絡(luò)方法(SOM)。4.10 下表中列出了4個點的兩個最近鄰。使用SNN相似度定義，計算每對點之間的SNN相似度。點第一個近鄰第二個近鄰143234342431答：SNN即共享最近鄰個數(shù)為其相似度。點1和點2的SNN相似度：0（沒有共享最近鄰）點1和點3的SNN相似度：1（共享點4這個最近鄰）點1和點4的SNN相似度：1（

30、共享點3這個最近鄰）點2和點3的SNN相似度：1（共享點4這個最近鄰）點2和點4的SNN相似度：1（共享點3這個最近鄰）點3和點4的SNN相似度：0（沒有共享最近鄰）第五章 關(guān)聯(lián)分析1.FP-tree（基于FP-growth算法）2.Apriori算法的例子(最小支持度計數(shù)閾值=2)3.概述：在關(guān)聯(lián)分析中，包含0個或多個項的集合稱為項集，一個包含k個數(shù)據(jù)項的項集就稱為k-項集。若一個項集的支持度大于或等于某個閾值，則稱為頻繁項集。：（1）產(chǎn)生頻繁項集：發(fā)現(xiàn)滿足最小支持度閾值的所有項集，即頻繁項集。 （2）產(chǎn)生規(guī)則：從上一步發(fā)現(xiàn)的頻繁項集中提取大于置信度閾值的規(guī)則，即強(qiáng)規(guī)則。5.1 列舉關(guān)聯(lián)規(guī)則

31、在不同領(lǐng)域中應(yīng)用的實例。答：在醫(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ī)則的例子，并說明它們是否是有價值的。(a)高支持度和高置信度的規(guī)則；(b)高支持度和低置信度的規(guī)則；(c)低支持度和低置信度的規(guī)則；(d)低支持度和高置信度的規(guī)則。5.3 數(shù)據(jù)集如表5-14所示：表5-14 習(xí)題5.3數(shù)據(jù)集Customer IDTransaction IDItems Bought112233445500010

32、02400120031001500220029004000330038a, d, ea, b, c, ea, b, d, ea, c, d, eb, c, eb, d, ec, da, b, ca, d, ea, b, e(a) 把每一個事務(wù)作為一個購物籃，計算項集e, b, d和b, d, e的支持度。(b) 利用(a)中結(jié)果計算關(guān)聯(lián)規(guī)則b, de 和 eb, d的置信度。置信度是一個對稱的度量嗎？(c) 把每一個用戶購買的所有商品作為一個購物籃，計算項集e, b, d和b, d, e的支持度。(d) 利用(b)中結(jié)果計算關(guān)聯(lián)規(guī)則b, de 和 eb, d的置信度。置信度是一個對稱的度量嗎？

33、答：(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)，所以置信度不是一個對稱的度量。 (c) 如果把每一個用戶購買所有的所有商品作為一個購物籃，則 s(e) = 4/5 =0.8 ; s(b,d) = 5/5 = 1 ; s(b,d,e) = 4/5 = 0.8.(d

34、) 利用c中結(jié)果計算關(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置信度不是一個對稱的度量5.6 考慮如下的頻繁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,

35、5 2,3,4,5 (b)經(jīng)過剪枝后的所有候選4-項集： 1,2,3,4 1,2,3,55.7 一個數(shù)據(jù)庫有5個事務(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算法找出所有頻繁項集。比較兩種挖掘方法的效率。(b) 比較窮舉法和Apriori算法生成的候選項集的數(shù)量。(c) 利用(1)所找出的頻繁項集，生成所有的強(qiáng)關(guān)聯(lián)規(guī)則和對應(yīng)的支持度和置信度。答：(1) 頻繁1-項集：M,O,K,E,Y 頻繁2-項集：M,K， O,K， O,E，K,Y，K,E 頻繁3-項集：O,K,E (2)窮舉法：M=2k-1=211-1=2047 Apriori算法：23(3) O,K>E，支持度0.6，置