習題及參考答案

1、習題參考答案第1章緒論1.1 數(shù)據(jù)挖掘處理的對象有哪些？請從實際生活中舉出至少三種。答：數(shù)據(jù)挖掘處理的對象是某一專業(yè)領域中積累的數(shù)據(jù)，對象既可以來自社會科學,又可以來自自然科學產(chǎn)生的數(shù)據(jù),還可以是衛(wèi)星觀測得到的數(shù)據(jù)。數(shù)據(jù)形式和結構也各不相同,可以是傳統(tǒng)的關系數(shù)據(jù)庫,可以是面向?qū)ο蟮母呒墧?shù)據(jù)庫系統(tǒng),也可以是面向特殊應用的數(shù)據(jù)庫,如空間數(shù)據(jù)庫、時序數(shù)據(jù)庫、文本數(shù)據(jù)庫和多媒體數(shù)據(jù)庫等,還可以是Web數(shù)據(jù)信息。 實際生活的例子：電信行業(yè)中利用數(shù)據(jù)挖掘技術進行客戶行為分析，包含客戶通話記錄、通話時間、所開通的服務等，據(jù)此進行客戶群體劃分以及客戶流失性分析。天文領域中利用決策樹等數(shù)據(jù)挖掘方法對上百萬天體數(shù)

2、據(jù)進行分類與分析，幫助天文學家發(fā)現(xiàn)其他未知星體。制造業(yè)中應用數(shù)據(jù)挖掘技術進行零部件故障診斷、資源優(yōu)化、生產(chǎn)過程分析等。市場業(yè)中應用數(shù)據(jù)挖掘技術進行市場定位、消費者分析、輔助制定市場營銷策略等。1.2 給出一個例子，說明數(shù)據(jù)挖掘?qū)ι虅盏某晒κ侵陵P重要的。該商務需要什么樣的數(shù)據(jù)挖掘功能？它們能夠由數(shù)據(jù)查詢處理或簡單的統(tǒng)計分析來實現(xiàn)嗎？ 答：例如，數(shù)據(jù)挖掘在電子商務中的客戶關系管理起到了非常重要的作用。隨著各個電子商務網(wǎng)站的建立，企業(yè)紛紛地從“產(chǎn)品導向”轉(zhuǎn)向“客戶導向”，如何在保持現(xiàn)有的客戶同時吸引更多的客戶、如何在客戶群中發(fā)現(xiàn)潛在價值，一直都是電子商務企業(yè)重要任務。但是，傳統(tǒng)的數(shù)據(jù)分析處理，如數(shù)據(jù)

3、查詢處理或簡單的統(tǒng)計分析，只能在數(shù)據(jù)庫中進行一些簡單的數(shù)據(jù)查詢和更新以及一些簡單的數(shù)據(jù)計算操作，卻無法從現(xiàn)有的大量數(shù)據(jù)中挖掘潛在的價值。而數(shù)據(jù)挖掘技術卻能使用如聚類、關聯(lián)分析、決策樹和神經(jīng)網(wǎng)絡等多種方法，對數(shù)據(jù)庫中龐大的數(shù)據(jù)進行挖掘分析，然后可以進行客戶細分而提供個性化服務、可以利用挖掘到的歷史流失客戶的特征來防止客戶流失、可以進行產(chǎn)品捆綁推薦等，從而使電子商務更好地進行客戶關系管理，提高客戶的忠誠度和滿意度。1.3 假定你是Big-University 的軟件工程師，任務是設計一個數(shù)據(jù)挖掘系統(tǒng)，分析學校課程數(shù)據(jù)庫。該數(shù)據(jù)庫包括如下信息：每個學生的姓名、地址和狀態(tài)(例如，本科生或研究生)、所修

4、課程，以及他們的GPA。描述你要選取的結構，該結構的每個成分的作用是什么？ 答：任務目的是分析課程數(shù)據(jù)庫，那么首先需要有包含信息的關系型數(shù)據(jù)庫系統(tǒng)，以便查找、提取每個屬性的值；在取得數(shù)據(jù)后，需要有特征選擇模塊，通過特征選擇，找出要分析的屬性；接下來需要一個數(shù)據(jù)挖掘算法，或者數(shù)據(jù)挖掘軟件，它應該包含像分類、聚類、關聯(lián)分析這樣的分析模塊，對選擇出來的特征值進行分析處理；在得到結果后，可以用可視化軟件進行顯示。1.4 假定你作為一個數(shù)據(jù)挖掘顧問，受雇于一家因特網(wǎng)搜索引擎公司。通過特定的例子說明，數(shù)據(jù)挖掘可以為公司提供哪些幫助，如何使用聚類、分類、關聯(lián)規(guī)則挖掘和離群點檢測等技術為企業(yè)服務。答：(1)

5、使用聚類發(fā)現(xiàn)互聯(lián)網(wǎng)中的不同群體，用于網(wǎng)絡社區(qū)發(fā)現(xiàn)；(2) 使用分類對客戶進行等級劃分，從而實施不同的服務；(3) 使用關聯(lián)規(guī)則發(fā)現(xiàn)大型數(shù)據(jù)集中間存在的關系，用于推薦搜索。如大部分搜索了“廣外”的人都會繼續(xù)搜索“信息學院”，那么在搜索“廣外”后會提示是否進進一步搜索“信息學院”。(4) 使用離群點挖掘發(fā)現(xiàn)與大部分對象不同的對象，用于分析針對網(wǎng)絡的秘密收集信息的攻擊。1.5 定義下列數(shù)據(jù)挖掘功能：關聯(lián)、分類、聚類、演變分析、離群點檢測。使用你熟悉的生活中的數(shù)據(jù)，給出每種數(shù)據(jù)挖掘功能的例子。 答：關聯(lián)是指發(fā)現(xiàn)樣本間或樣本不同屬性間的關聯(lián)。例如，一個數(shù)據(jù)挖掘系統(tǒng)可能發(fā)現(xiàn)的關聯(lián)規(guī)則為：major(X,

6、“computing science”)owns(X, “personal computer”) support=12%, confidence=98% 其中，X是一個表示學生的變量。該規(guī)則指出主修計算機科學并且擁有一臺個人計算機的學生所占比例為12%，同時，主修計算機專業(yè)的學生有98%擁有個人計算機。分類是構造一系列能描述和區(qū)分數(shù)據(jù)類型或概念的模型(或功能)，分類被用作預測目標數(shù)據(jù)的類的標簽。例如，通過對過去銀行客戶流失與未流失客戶數(shù)據(jù)的分析，得到一個預測模型，預測新客戶是否可能會流失。聚類是將數(shù)據(jù)劃分為相似對象組的過程，使得同一組中對象相似度最大而不同組中對象相似度最小。例如，通過對某大型

7、超市客戶購物數(shù)據(jù)進行聚類，將客戶聚類細分為低值客戶、高值客戶以及普通客戶等。數(shù)據(jù)演變分析描述和模型化隨時間變化的對象的規(guī)律或趨勢，盡管這可能包括時間相關數(shù)據(jù)的特征化、區(qū)分、關聯(lián)和相關分析、分類、或預測，這種分析的明確特征包括時間序列數(shù)據(jù)分析、序列或周期模式匹配、和基于相似性的數(shù)據(jù)分析 。離群點檢測就是發(fā)現(xiàn)與眾不同的數(shù)據(jù)?？捎糜诎l(fā)現(xiàn)金融領域的欺詐檢測。1.6 根據(jù)你的觀察，描述一個可能的知識類型，它需要由數(shù)據(jù)挖掘方法發(fā)現(xiàn)，但本章未列出。它需要一種不同于本章列舉的數(shù)據(jù)挖掘技術嗎？ 答：建立一個局部的周期性作為一種新的知識類型，只要經(jīng)過一段時間的偏移量在時間序列中重復發(fā)生，那么在這個知識類型中的模式

8、是局部周期性的。需要一種新的數(shù)據(jù)挖掘技術解決這類問題。1.7 討論下列每項活動是否是數(shù)據(jù)挖掘任務：(1)根據(jù)性別劃分公司的顧客。(2)根據(jù)可贏利性劃分公司的顧客。(3)計算公司的總銷售額。(4)按學生的標識號對學生數(shù)據(jù)庫排序。(5)預測擲一對骰子的結果。(6)使用歷史記錄預測某公司未來的股票價格。(7)監(jiān)視病人心率的異常變化。(8)監(jiān)視地震活動的地震波。(9)提取聲波的頻率。答： (1) 不是，這屬于簡單的數(shù)據(jù)庫查詢。(2) 不是，這個簡單的會計計算；但是新客戶的利潤預測則屬于數(shù)據(jù)挖掘任務。(3) 不是，還是簡單的會計計算。(4) 不是，這是簡單的數(shù)據(jù)庫查詢。(5) 不是，由于每一面都是同等概

9、率，則屬于概率計算；如概率是不同等的，根據(jù)歷史數(shù)據(jù)預測結果則更類似于數(shù)據(jù)挖掘任務。(6) 是，需要建立模型來預測股票價格，屬于數(shù)據(jù)挖掘領域中的預測模型。可以使用回歸來建模，或使用時間序列分析。(7) 是，需要建立正常心率行為模型，并預警非正常心率行為。這屬于數(shù)據(jù)挖掘領域的異常檢測。若有正常和非正常心率行為樣本，則可以看作一個分類問題。(8) 是，需要建立與地震活動相關的不同波形的模型，并預警波形活動。屬于數(shù)據(jù)挖掘領域的分類。(9) 不是，屬于信號處理。第2章數(shù)據(jù)處理基礎2.1 將下列屬性分類成二元的、分類的或連續(xù)的，并將它們分類成定性的(標稱的或序數(shù)的)或定量的(區(qū)間的或比率的)。例子：年齡。

10、回答：分類的、定量的、比率的。(a)用AM和PM表示的時間。(b)根據(jù)曝光表測出的亮度。(c)根據(jù)人的判斷測出的亮度。(d)醫(yī)院中的病人數(shù)。(e)書的ISBN號。(f)用每立方厘米表示的物質(zhì)密度。答：(a)二元，定量，比率；(b)連續(xù)，定量 ，比率；(c)分類，定性，標稱；(d)連續(xù)，定量，比率；(e)分類，定性，標稱；(f)連續(xù)，定量，比率。2.2 你能想象一種情況，標識號對于預測是有用的嗎？答：學生的ID號可以預測該學生的畢業(yè)日期。2.3 在現(xiàn)實世界的數(shù)據(jù)中，元組在某些屬性上缺失值是常有的。請描述處理該問題的各種方法。 答：處理遺漏值問題的策略有如下幾種。(1) 刪除數(shù)據(jù)對象或?qū)傩浴Ｒ环N簡

11、單而有效的策略是刪除具有遺漏值的數(shù)據(jù)對象。然而，即使部分給定的數(shù)據(jù)對象也包含一些信息，并且，如果許多對象都有遺漏值，則很難甚至不可能進行可靠的分析。盡管如此，如果一個數(shù)據(jù)集只有少量的對象具有遺漏值，則忽略他們可能是合算的。一種相關的策略是刪除具有遺漏值的屬性。然而，做這件事要小心，因為被刪除的屬性可能對分析是至關重要的。(2) 估計遺漏值。有時，遺漏值可以可靠地估計。例如，在考慮以較平滑的方式變化的具有少量但大大分散的遺漏值的時間序列，遺漏值可以使用其他值來估計(插值)。作為另一個例子，考慮一個具有許多相似數(shù)據(jù)點的數(shù)據(jù)集。在這種情況下，與具有遺漏值的點鄰近的點的屬性值常?？梢杂脕砉烙嬤z漏的值。

12、如果屬性是連續(xù)的，則可以使用最近鄰的平均屬性值；如果屬性是分類的，則可以取最近鄰中最常出現(xiàn)的屬性值。(3) 在分析時忽略遺漏值。許多數(shù)據(jù)挖掘方法都可以修改，忽略遺漏值。例如。假定正在對數(shù)據(jù)對象聚類，需要計算數(shù)據(jù)對象間的相似性；如果對于某屬性，兩個對象之一或兩個對象都有遺漏值，則可以僅使用沒有遺漏值的屬性來計算相似性。當然，這種相似性只是緊鄰的，但是除非整個屬性數(shù)目很少，或者遺漏值的數(shù)量很大，否則這種誤差影響不大。同樣的，許多分類方法都可以修改，處理遺漏值。2.4 以下規(guī)范方法的值域是什么？(a) min-max規(guī)范化。(b) z-score 規(guī)范化。(c) 小數(shù)定標規(guī)范化。答：(a)new_m

13、in,new_max；(b)(-,+ )；(c)(-1.0，1.0)。2.5 假定用于分析的數(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,70。(a) 使用按箱平均值平滑對以上數(shù)據(jù)進行平滑，箱的深度為3。解釋你的步驟。評論對于給定的數(shù)據(jù)，該技術的效果。 (b) 對于數(shù)據(jù)平滑，還有哪些其它方法？ 答：(a)已知數(shù)據(jù)元組中age 的值如下(按遞增序)：13,15,16,16,19,20,20,21,22,22,25,25,2

14、5,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

15、)回歸：可以用一個函數(shù)(如回歸函數(shù))擬合數(shù)據(jù)來光滑數(shù)據(jù)；(2)聚類：可以通過聚類檢測離群點，將類似的值組織成群或簇。直觀地，落在簇集合之外的值視為離群點。2.6 使用習題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 的標準偏差為12.94 年。 (c) 使用小數(shù)定標規(guī)范化轉(zhuǎn)換age 值35。 (d) 指出對于給定的數(shù)據(jù)，你愿意使用哪種方法。陳述你的理由。 答：(a)已知最大值為70，最小值為13，則可將35規(guī)范化為：；(b)已知均值為30，標準差為1

16、2.94，則可將35規(guī)范化為：；(c)使用小數(shù)定標規(guī)范化可將35規(guī)范化為：；(d)對于給定的數(shù)據(jù)，你愿意使用min-max 規(guī)范化。理由是計算簡單。2.7 使用習題2.5 給出的age 數(shù)據(jù) (a) 畫一個寬度為10 的等寬的直方圖。 (b) 為以下每種抽樣技術勾畫例子：有放回簡單隨機抽樣，無放回簡單隨機抽樣，聚類抽樣，分層抽樣。使用大小為5的樣本和層“青年”,“中年”和“老年”。答：(a)如下為寬度為10 的等寬的直方圖：(b)已知樣本大小為5和層“青年”，“中年”和“老年”，(1)有放回簡單隨機抽樣：30,33,30,25,30(2)無放回簡單隨機抽樣：30,33,33,35,25(3)聚

17、類抽樣：16,25,33,35,46(4)分層抽樣：25,35,522.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(5)、28、30(3)。請分別用等寬的方法和等高的方法對上面的數(shù)據(jù)集進行劃分。答：(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之

18、間的價格為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)冗余：一個屬性是冗余的，即它能由另一個表導出，如果屬性或維的命名不一致，也可能導致冗余，可以用相關分析來檢測；(3)數(shù)據(jù)值沖突的檢測與處理：有些屬性因表示比例或編碼不同，會導致屬性不同。2.10 假定我們對一個比率屬性x使用平方根變換，得到一個新屬性x*。作為分析的一部分，你識別出區(qū)間(a, b)，在該區(qū)間內(nèi)，x*與另一個屬性y具有線性關系。(a)換算成x

19、, (a, b)的對應區(qū)間是什么？(b)給出y關聯(lián)x的方程。答：(a)(a2，b2)；(b)Y=kx0.5 +C (k, C是常數(shù))。2.11 討論使用抽樣減少需要顯示的數(shù)據(jù)對象個數(shù)的優(yōu)缺點。簡單隨機抽樣(無放回)是一種好的抽樣方法嗎？為什么是，為什么不是？答：抽樣減少需要顯示的數(shù)據(jù)對象個數(shù)的優(yōu)點是減少處理數(shù)據(jù)的費用和時間。缺點是不能利用總體的已知信息和代表總體數(shù)據(jù)的信息。簡單隨機抽樣(無放回)不是一種好的抽樣方法，不能充分地代表不太頻繁出現(xiàn)的對象類型和每個對象被選中的概率不一樣。2.12 給定m個對象的集合，這些對象劃分成K組，其中第i組的大小為mi。如果目標是得到容量為nm的樣本，下面兩種

20、抽樣方案有什么區(qū)別？(假定使用有放回抽樣)(a)從每組隨機地選擇nmi/m個元素。(b)從數(shù)據(jù)集中隨機地選擇n個元素，而不管對象屬于哪個組。答：(a)組保證了可以在每個組里面得到等比例的樣本，而(b)組在每個組里面抽取的樣本的個數(shù)是隨機的，不能保證每個組都能抽到樣本。2.13 一個地方公司的銷售主管與你聯(lián)系，他相信他已經(jīng)設計出了一種評估顧客滿意度的方法。他這樣解釋他的方案：“這太簡單了，我簡直不敢相信，以前竟然沒有人想到，我只是記錄顧客對每種產(chǎn)品的抱怨次數(shù)，我在數(shù)據(jù)挖掘的書中讀到計數(shù)具有比率屬性，因此，我的產(chǎn)品滿意度度量必定具有比率屬性。但是，當我根據(jù)我的顧客滿意度度量評估產(chǎn)品并拿給老板看時，

21、他說我忽略了顯而易見的東西，說我的度量毫無價值。我想，他簡直是瘋了，因為我們的暢銷產(chǎn)品滿意度最差，因為對它的抱怨最多。你能幫助我擺平他嗎？”(a)誰是對的，銷售主管還是他的老板？如果你的答案是他的老板，你做些什么來修正滿意度度量？(b)對于原來的產(chǎn)品滿意度度量的屬性類型，你能說些什么？答: (a) 老板是對的。更好的衡量方法應該如下：不滿意率(產(chǎn)品)=每種產(chǎn)品的抱怨次數(shù)/該產(chǎn)品的總銷售量(b) 原來衡量方法的屬性類型是沒有意義的。例如，兩件商品有相同的顧客滿意度可能會有不同的抱怨次數(shù)，反之亦然。2.14 考慮一個文檔-詞矩陣，其中是第i個詞(術語)出現(xiàn)在第j個文檔中的頻率，而m是文檔數(shù)?？紤]由

22、下式定義的變量變換：其中，是出現(xiàn)i個詞的文檔數(shù)，稱作詞的文檔頻率(document frequency)。該變換稱作逆文檔頻率變換(inverse document frequency)。(a)如果出現(xiàn)在一個文檔中，該變換的結果是什么？如果術語出現(xiàn)在每個文檔中呢？(b)該變換的目的可能是什么？答：(a) 如果該詞出現(xiàn)在每一個文檔中，它的詞權就會為0，但是如果這個詞僅僅出現(xiàn)在一個文檔中，它就有最大的詞權，例如，log m 。(b) 這個變換反映了以下一個現(xiàn)象：當一個詞出現(xiàn)在每一個文檔中，對于文檔與文檔之間，該詞沒有區(qū)分能力，但是那些只是某一兩篇文檔出現(xiàn)的詞，其區(qū)分文檔的能力就較強。2.15 對于

23、下面的向量x和y，計算指定的相似性或距離度量。(a)x=(1，1，1，1)，y=(2，2，2，2) 余弦相似度、相關系數(shù)、歐幾里得。(b) x=(0，1，0，1)，y=(1，0，1，0) 余弦相似度、相關系數(shù)、歐幾里得、Jaccard系數(shù)。(c) x=(2，-1,0，2，0，-3)，y=(-1，1，-1，0，0，-1) 余弦相似度、相關系數(shù)。答：(a) 余弦相似度、相關系數(shù)、歐幾里得分別是0.5，0，2；(b) 余弦相似度、相關系數(shù)、歐幾里得、Jaccard系數(shù)分別是0，1，2，0；(c) 余弦相似度、相關系數(shù)分別是0，0。2.16 簡單地描述如何計算由以下類型的變量描述的對象間的相異度： (

24、a) 不對稱的二元變量 (b) 分類變量 (c) 比例標度型(ratio-scaled)變量 (d) 數(shù)值型變量 答：(a) 使用Jaccard系數(shù)計算不對稱的二元變量的相異度；(b) 采用屬性值匹配的方法(屬性值匹配，相似度為1，否則為0)可以計算用分類變量描述的對象間的相異度；(c) 對比例標度變量進行對數(shù)變換，對變換得到的值采用與處理區(qū)間標度變量相同的方法來計算相異度；(d) 可采用歐幾里得距離公式或曼哈頓距離公式計算。2.17 給定兩個向量對象，分別表示為p1(22，1，42，10)，p2(20，0，36，8)： (a) 計算兩個對象之間的歐幾里得距離 (b) 計算兩個對象之間的曼哈頓

25、距離 (c) 計算兩個對象之間的切比雪夫距離(d) 計算兩個對象之間的閔可夫斯基距離，用x=3答：(a) 計算兩個對象之間的歐幾里得距離(b) 計算兩個對象之間的曼哈頓距離(c) 計算兩個對象之間的閔可夫斯基距離，其中參數(shù)r=32.18 以下表格包含了屬性name，gender，trait-1，trait-2，trait-3，及trait-4，這里的name 是對象的id，gender 是一個對稱的屬性，剩余的trait 屬性是不對稱的，描述了希望找到的筆友的個人特點。假設有一個服務是試圖發(fā)現(xiàn)合適的筆友。 namegendertrait-1trait-2trait-3trait-4KeavnM

26、NPPNCarolineFNPPNErikMPNNP對不對稱的屬性的值，值P 被設為1，值N 被設為0。 假設對象(潛在的筆友)間的距離是基于不對稱變量來計算的。 (a) 計算對象間的簡單匹配系數(shù)；(b) 計算對象間的Jaccard 系數(shù)； (c) 你認為哪兩個人將成為最佳筆友？哪兩個會是最不能相容的？ (d) 假設我們將對稱變量gender 包含在我們的分析中?；贘accard 系數(shù)，誰將是最和諧的一對？為什么？ 答：(a) 計算對象間的簡單匹配系數(shù)SMC (Keavn, Caroline) = (2+2)/( 0+0+2+2) = 1SMC(Keavn, Erik) = (0+0)/(

27、2+2+0+0) = 0SMC(Caroline,Erik) = (0+0)/( 2+2+0+0) = 0(b) 計算對象間的Jaccard 系數(shù)Jaccard (Keavn, Caroline) = 2/(2+0+0) = 1Jaccard (Keavn, Erik) = 0/(0+2+2) = 0Jaccard (Caroline,Erik) = 0/(0+2+2) = 0(c) 根據(jù)屬性的匹配程度，Keavn和Caroline將成為最佳筆友，Caroline和Erik會是最不能相容的。(d) 若將對稱變量gender 包含在分析中，設值M被設為1，值F被設為0，Jaccard (Keav

28、n, Caroline) = 2/(2+1+0) = 2/3Jaccard (Keavn, Erik) = 1/(1+2+2) = 1/5Jaccard (Caroline,Erik) = 0/(0+2+3) = 0因為Jaccard (Keavn, Caroline)最大，因此，Keavn和 Caroline是最和諧的一對。2.19 給定一個在區(qū)間0，1取值的相似性度量，描述兩種將該相似度變換成區(qū)間0，中的相異度的方法。答：取倒數(shù)減一：取對數(shù)：第3章分類與回歸3.1 簡述決策樹分類的主要步驟。答：決策樹生成的過程如下：(1)對數(shù)據(jù)源進行數(shù)據(jù)預處理, 得到訓練集和測試集；(2)對訓練集進行訓練

29、；(3)對初始決策樹進行樹剪枝；(4)由所得到的決策樹提取分類規(guī)則；(5)使用測試數(shù)據(jù)集進行預測，評估決策樹模型；3.2 給定決策樹，選項有：(1)將決策樹轉(zhuǎn)換成規(guī)則，然后對結果規(guī)則剪枝，或(2)對決策樹剪枝，然后將剪枝后的樹轉(zhuǎn)換成規(guī)則。相對于(2)，(1)的優(yōu)點是什么？答：相對于(2)，(1)的優(yōu)點是：由于第一種方法已經(jīng)將決策樹轉(zhuǎn)換成規(guī)則，通過規(guī)則，可以很快速的評估決策樹以及其子樹緊湊程度，不能提高規(guī)則的估計準確率的任何條件都可以減掉，從而泛化規(guī)則； 3.3 計算決策樹算法在最壞情況下的時間復雜度是重要的。給定數(shù)據(jù)集D，具有m個屬性和|D|個訓練記錄，證明決策樹生長的計算時間最多為。答：假設

30、訓練集擁有|D|實例以及m個屬性。我們需要對樹的尺寸做一個假設，假設樹的深度是由log |D| 決定，即O(log |D|)。考慮一個屬性在樹的所有節(jié)點上所要做的工作量。當然不必在每一個節(jié)點上考慮所有的實例。但在樹的每一層，必須考慮含有|D|個實例的整個數(shù)據(jù)集。由于樹有l(wèi)og |D|個不同的層，處理一個屬性需要的工作量是。在每個節(jié)點上所有屬性都要被考慮，因此總的工作量為。3.4 考慮表3-23所示二元分類問題的數(shù)據(jù)集。表3-23 習題3.4數(shù)據(jù)集AB類標號TF+TT+TT+TF-TT+FF-FF-FF-TT-TF-(1) 計算按照屬性A和B劃分時的信息增益。決策樹歸納算法將會選擇那個屬性？(2

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

32、照屬性A劃分時Gini指標:Gini增益按照屬性B劃分時Gini指標:Gini增益因此，決策樹歸納算法將會選擇屬性B。3.5 證明：將結點劃分為更小的后續(xù)結點之后，結點熵不會增加。證明：根據(jù)定義可知，熵值越大，類分布越均勻；熵值越小，類分布越不平衡。假設原有的結點屬于各個類的概率都相等，熵值為1，則分出來的后續(xù)結點在各個類上均勻分布，此時熵值為1，即熵值不變。假設原有的結點屬于個各類的概率不等，因而分出來的后續(xù)結點不均勻地分布在各個類上，則此時的分類比原有的分類更不均勻，故熵值減少。3.6 為什么樸素貝葉斯稱為“樸素”？簡述樸素貝葉斯分類的主要思想。答：樸素貝葉斯之所以稱之為樸素是因為，它假設

33、屬性之間是相互獨立的。樸素貝葉斯分類的主要思想為：利用貝葉斯定理，計算未知樣本屬于某個類標號值的概率，根據(jù)概率值的大小來決定未知樣本的分類結果。(通過某對象的先驗概率，利用貝葉斯公式計算出其后驗概率，即該對象屬于某一類的概率，選擇具有最大后驗概率的類作為該對象所屬的類。)3.7 考慮表3-24數(shù)據(jù)集，請完成以下問題：表3-24 習題3.7數(shù)據(jù)集記錄號ABC類1000+2001-3011-4011-5001+6101+7101-8101-9111+10101+(1) 估計條件概率，。(2) 根據(jù)(1)中的條件概率，使用樸素貝葉斯方法預測測試樣本(A=0，B=1，C=0)的類標號；(3) 使用La

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

35、/K=0/K則得到，此樣本的類標號是+。(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) 假設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=(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(

36、-)/K=P(A=0|-)P(B|-)P(C=0|-)P(-)/K=(5/9) (4/9) (2/9) 0.5/K=0.0274/K則得到，此樣本的類標號是-。(5) 當條件概率為0的時候，條件概率的預測用Laplace估計方法比較好，因為我們不想整個條件概率計算結果為0.3.8 考慮表3-25中的一維數(shù)據(jù)集。 表3-25 習題3.8數(shù)據(jù)集X0.53.04.54.64.95.25.35.57.09.5Y-+-+-根據(jù)1-最近鄰、3-最近鄰、5-最近鄰、9-最近鄰，對數(shù)據(jù)點x=5.0分類，使用多數(shù)表決。答： 1-最近鄰：+3-最近鄰：-5-最近鄰：+9-最近鄰：-3.9 表3-26的數(shù)據(jù)集包含兩

37、個屬性X與Y，兩個類標號“+”和“-”。每個屬性取三個不同值策略：0,1或2?！?”類的概念是Y=1，“-”類的概念是X=0 and X=2。表3-26 習題3.9數(shù)據(jù)集XY實例數(shù)+-00010010002001001110021101000201001200220100(1) 建立該數(shù)據(jù)集的決策樹。該決策樹能捕捉到“+”和“-”的概念嗎？(2) 決策樹的準確率、精度、召回率和F1各是多少？(注意，精度、召回率和F1量均是對“+”類定義)(3) 使用下面的代價函數(shù)建立新的決策樹，新決策樹能捕捉到“+”的概念么？(提示：只需改變原決策樹的結點。)答：(1)在數(shù)據(jù)集中有20個正樣本和500個負樣本

38、，因此在根節(jié)點處錯誤率為 如果按照屬性X劃分，則：X=0X=1X=2+01010-2000300 EX=0=0/310=0 EX=1=0/10=0 EX=2=10/310 如果按照屬性Y劃分，則：Y=0Y=1Y=2+0200-200100200 EY=0=0/200=0 EY=1=20/120 EY=2=0/200=0因此X被選為第一個分裂屬性，因為X=0和X=1都是純節(jié)點，所以使用Y屬性去分割不純節(jié)點X=2。Y=0節(jié)點包含100個負樣本，Y=1節(jié)點包含10個正樣本和100個負樣本，Y=2節(jié)點包含100個負樣本，所以子節(jié)點被標記為“”。整個結果為：類標記=(2)預測類+-實際類+1010-05

39、00accuracy:=0.9808，precision:=1.0 recall: =0.5 ， F-measure:=0.6666(3)由題可得代價矩陣為預測類+-實際類+0500/20=25-10決策樹在(1)之后還有3個葉節(jié)點，X=2Y=0，X=2Y=1，X=2Y=2。其中X=2Y=1是不純節(jié)點，誤分類該節(jié)點為“+”類的代價為：100+1001=100，誤分該節(jié)點為“”類的代價為：1025+1000=250。所以這些節(jié)點被標記為“+”類。分類結果為： 3.10 什么是提升？陳述它為何能提高決策樹歸納的準確性？答：提升是指給每個訓練元組賦予權重，迭代地學習k個分類器序列，學習得到分類器Mi

40、之后，更新權重，使得其后的分類器Mi+1“更關注”Mi誤分的訓練元組，最終提升的分類器M*組合每個個體分類器，其中每個分類器投票的權重是其準確率的函數(shù)。在提升的過程中，訓練元組的權重根據(jù)它們的分類情況調(diào)整，如果元組不正確地分類，則它的權重增加，如果元組正確分類，則它的權重減少。元組的權重反映對它們分類的困難程度，權重越高，越可能錯誤的分類。根據(jù)每個分類器的投票，如果一個分類器的誤差率越低，提升就賦予它越高的表決權重。在建立分類器的時候，讓具有更高表決權重的分類器對具有更高權重的元組進行分類，這樣，建立了一個互補的分類器系列。所以能夠提高分類的準確性。3.11 表3-27給出課程數(shù)據(jù)庫中學生的期

41、中和期末考試成績。表3-27 習題3.11數(shù)據(jù)集期中考試期末考試XY728450638177747894908675594983796577335288748190(1) 繪制數(shù)據(jù)的散點圖。X和Y看上去具有線性聯(lián)系嗎？(2) 使用最小二乘法，由學生課程中成績預測學生的期末成績的方程式。(3) 預測期中成績?yōu)?6分的學生的期末成績。答：(1)數(shù)據(jù)圖如下所示：X和Y具有線性聯(lián)系。(2)XYX*YX2預測Y172846048518473.9031250633150250061.1079381776237656179.1375474785772547675.0663594908460883686.69

42、83686756450739682.0455759492891348166.3423883796557688980.3007965775005422569.83191033521716108951.22071188746512774483.20871281907290656179.1375SUM8668886608865942Y = a + b*Xa = Y0 + b*X0b = (xiyi-nX0Y0)/(xi2-nX02)X0 = (xi)/nY0 = (yi)/n求得 a = 32.0279，b = 0.5816。(3)由(2)中表可得，預測成績?yōu)?6分的學生的期末成績?yōu)?2.0455。

43、3.12 通過對預測變量變換，有些非線性回歸模型可以轉(zhuǎn)換成線性模型。指出如何將非線性回歸方程轉(zhuǎn)換成可以用最小二乘法求解的線性回歸方程。答：令，對樣本數(shù)據(jù)做變換，利用(wi，Yi)(i=1，2，n)解出y = aw中的a，再代入即得到y(tǒng)對x的回歸方程。第4章聚類分析4.1 什么是聚類？簡單描述如下的聚類方法：劃分方法，層次方法，基于密度的方法，基于模型的方法。為每類方法給出例子。 答：聚類是將數(shù)據(jù)劃分為相似對象組的過程，使得同一組中對象相似度最大而不同組中對象相似度最小。主要有以下幾種類型方法：(1)劃分方法給定一個有N個元組或者記錄的數(shù)據(jù)集，分裂法將構造K個分組，每一個分組就代表一個聚類，KN

44、。而且這K個分組滿足下列條件：第一，每一個分組至少包含一條記錄；第二，每一條記錄屬于且僅屬于一個分組(注意：這個要求在某些模糊聚類算法中可以放寬)；對于給定的K，算法首先給出一個初始的分組方法，以后通過反復迭代的方法改變分組，使得每一次改進之后的分組方案都較前一次好，而所謂好的標準就是：同一分組中的記錄越近越好，而不同分組中的記錄越遠越好。使用這個基本思想的算法有：K-MEANS算法、K-MEDOIDS算法、CLARANS算法。(2)層次方法這種方法對給定的數(shù)據(jù)集進行層次似的分解，直到某種條件滿足為止。具體又可分為“自底向上”和“自頂向下”兩種方案。例如在“自底向上”方案中，初始時每一個數(shù)據(jù)記

45、錄都組成一個單獨的組，在接下來的迭代中，它把那些相互鄰近的組合并成一個組，直到所有的記錄組成一個分組或者某個條件滿足為止。代表算法有：BIRCH算法、CURE算法、CHAMELEON算法等。(3)基于密度的方法基于密度的方法與其它方法的一個根本區(qū)別是：它不是基于各種各樣的距離，而是基于密度的。這樣就能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點。這個方法的指導思想就是：只要一個區(qū)域中的點的密度大過某個閾值，就把它加到與之相近的聚類中去。代表算法有：DBSCAN算法、OPTICS算法、DENCLUE算法等。(4)基于模型的方法基于模型的方法給每一個聚類假定一個模型，然后去尋找能夠很好的滿足這

46、個模型的數(shù)據(jù)。這樣一個模型可能是數(shù)據(jù)點在空間中的密度分布函數(shù)或者其它。它的一個潛在假定就是：目標數(shù)據(jù)集是由一系列的概率分布所決定的。基于模型的方法主要有兩類：統(tǒng)計學方法和神經(jīng)網(wǎng)絡方法(SOM)。4.2 假設數(shù)據(jù)挖掘的任務是將如下的8個點(用(x,y)代表位置)聚類為三個簇。 A1(2,10),A2(2,5),A3(8,4),B1(5,8),B2(7,5),B3(6,4),C1(1,2),C2(4,9)。距離函數(shù)是Euclidean 函數(shù)。假設初始我們選擇A1,B1和C1為每個簇的中心，用k-means 算法來給出 (a) 在第一次循環(huán)執(zhí)行后的三個簇中心；(b) 最后的三個簇中心及簇包含的對象。

47、答：(a)如圖，(b)如圖，4.3 聚類被廣泛地認為是一種重要的數(shù)據(jù)挖掘方法，有著廣泛的應用。對如下的每種情況給出一個應用例子： (a) 采用聚類作為主要的數(shù)據(jù)挖掘方法的應用；(b) 采用聚類作為預處理工具，為其它數(shù)據(jù)挖掘任務作數(shù)據(jù)準備的應用。答：(a) 如電子商務網(wǎng)站中的客戶群劃分。根據(jù)客戶的個人信息、消費習慣、瀏覽行為等信息，計算客戶之間的相似度，然后采用合適的聚類算法對所有客戶進行類劃分；基于得到的客戶群信息，相關的店主可以制定相應的營銷策略，如交叉銷售，根據(jù)某個客戶群中的其中一個客戶的購買商品推薦給另外一個未曾購買此商品的客戶。(b) 如電子商務網(wǎng)站中的推薦系統(tǒng)。電子商務網(wǎng)站可以根據(jù)得

48、到的客戶群，采用關聯(lián)規(guī)則或者隱馬爾科夫模型對每個客戶群生成消費習慣規(guī)則，檢測客戶的消費模式，這些規(guī)則或模式可以用于商品推薦。其中客戶群可以通過聚類算法來預先處理獲取得到。4.4 假設你將在一個給定的區(qū)域分配一些自動取款機以滿足需求。住宅區(qū)或工作區(qū)可以被聚類以便每個簇被分配一個ATM。但是，這個聚類可能被一些因素所約束，包括可能影響ATM 可達性的橋梁，河流和公路的位置。其它的約束可能包括對形成一個區(qū)域的每個地域的ATM 數(shù)目的限制。給定這些約束，怎樣修改聚類算法來實現(xiàn)基于約束的聚類？答：約束的存在會使得原來被定義在同一個簇的對象之間的距離發(fā)生變化。這時可以考慮將這些約束因素融入到距離的計算公式

49、中，如在存在橋梁、河流和公路的區(qū)域中，可通過對象之間的連通性以及路徑來計算距離；而地域ATM數(shù)目的限制問題則可在聚類的初始化階段解決，如在K-MEANS的初始化時，可根據(jù)區(qū)域的個數(shù)來確定簇個數(shù)K的值，然后所選擇的初始化種子盡可能分布在距離各個ATM附近的地方。4.5 給出一個數(shù)據(jù)集的例子，它包含三個自然簇。對于該數(shù)據(jù)集，k-means(幾乎總是)能夠發(fā)現(xiàn)正確的簇，但二分k-means不能。答：有三個完全一樣的球型簇，三個簇的點的個數(shù)和分布密度以及位置均完全相同。其中兩個簇關于第三個簇完全對稱，則在k-means方法中可以很輕易找出這三個簇，但用二分k-means則會把處于對稱中心的那個簇分成兩

50、半。4.6 總SSE是每個屬性的SSE之和。如果對于所有的簇，某變量的SSE都很低，這意味什么？如果只對一個簇很低呢？如果對所有的簇都很高？如果僅對一個簇高呢？如何使用每個變量的SSE信息改進聚類？答： (a) 如果對于所有的簇，某屬性的SSE都很低，那么該屬性值變化不大，本質(zhì)上等于常量，對數(shù)據(jù)的分組沒什么用處。(b) 如果某屬性的SSE只對一個簇很低，那么該屬性有助于該簇的定義。(c) 如果對于所有的簇，某屬性的SSE都很高，那么意味著該屬性是噪聲屬性。(d) 如果某屬性的SSE僅對一個簇很高，那么該屬性與定義該簇的屬性提供的信息不一致。在少數(shù)情況下，由該屬性定義的簇不同于由其他屬性定義的簇

51、，但是在某些情況下，這也意味著該屬性不利于簇的定義。(e) 消除簇之間具有小分辨力的屬性，比如對于所有簇都是低或高SSE的屬性，因為他們對聚類沒有幫助。對于所有簇的SSE都高且相對其他屬性來說SSE也很高的屬性特別麻煩，因為這些屬性在SSE的總和計算中引入了很多的噪聲。4.7 使用基于中心、鄰近性和密度的方法，識別圖4-19中的簇。對于每種情況指出簇個數(shù)，并簡要給出你的理由。注意，明暗度或點數(shù)指明密度。如果有幫助的話，假定基于中心即K均值，基于鄰近性即單鏈，而基于密度為DBSCAN。圖4-19 題4.7圖答：(a) 基于中心的方法有2個簇。矩形區(qū)域被分成兩半，同時2個簇里都包含了噪聲數(shù)據(jù)；基于

52、鄰近性的方法有1個簇。因為兩個圓圈區(qū)域受噪聲數(shù)據(jù)影響而形成一個簇；基于密度的方法有2個簇，每個圓圈區(qū)域代表一個簇，而噪聲數(shù)據(jù)會被忽略。(b) 基于中心的方法有1個簇，該簇包含圖中的一個圓環(huán)和一個圓盤；基于鄰近性的方法有2個簇，外部圓環(huán)代表一個簇，內(nèi)層圓盤代表一個簇；基于密度的方法有2個簇，外部圓環(huán)代表一個簇，內(nèi)層圓盤代表一個簇。(c) 基于中心的方法有3個簇，每個三角形代表一個簇；基于鄰近性的方法有1個簇，三個三角形區(qū)域會聯(lián)合起來因為彼此相互接觸；基于密度的方法有3個簇，每個三角形區(qū)域代表一個簇。即使三個三角形相互接觸，但是所接觸的區(qū)域的密度比三角形內(nèi)的密度小。(d) 基于中心的方法有2個簇。

53、兩組線被分到兩個簇里；基于鄰近性的方法有5個簇。相互纏繞的線被分到一個簇中；基于密度的方法有2個簇。這兩組線定義了被低密度區(qū)域所分割的兩個高密度的區(qū)域。4.8 傳統(tǒng)的凝聚層次聚類過程每步合并兩個簇。這樣的方法能夠正確地捕獲數(shù)據(jù)點集的(嵌套的)簇結構嗎？如果不能，解釋如何對結果進行后處理，以得到簇結構更正確的視圖。答:傳統(tǒng)的凝聚層次聚類過程關鍵是每步合并兩個最相似的簇，直至只剩下一個簇才停止聚類。該聚類方法并不能產(chǎn)生嵌套的簇結構。但我們可以采用樹結構的方法來捕捉形成的層次結構，每次合并都記錄父子簇之間的關系，最后形成一個清晰的樹狀層次簇結構。4.9 我們可以將一個數(shù)據(jù)集表示成對象節(jié)點的集合和屬性

54、節(jié)點的集合，其中每個對象與每個屬性之間有一條邊，該邊的權值是對象在該屬性上的值。對于稀疏數(shù)據(jù)，如果權值為0，則忽略該邊。雙劃分聚類(Bipartite)試圖將該圖劃分成不相交的簇，其中每個簇由一個對象節(jié)點集和一個屬性節(jié)點集組成。目標是最大化簇中對象節(jié)點和屬性節(jié)點之間的邊的權值，并且最小化不同簇的對象節(jié)點和屬性節(jié)點之間的邊的權值。這種聚類稱作協(xié)同聚類(co-clustering)，因為對象和屬性之間同時聚類。 (a) 雙劃分聚類(協(xié)同聚類)與對象和屬性集分別聚類有何不同？ (b) 是否存在某些情況，這些方法產(chǎn)生相同的結果？ (c) 與一般聚類相比，協(xié)同聚類的優(yōu)點和缺點是什么？答:(a) 對于普通聚類，只有一組約束條件被運用，要么與對象相關，要么與屬性相關。對于協(xié)同聚類，兩組約束條件同時被運用。因此，單獨地劃分