《數(shù)據(jù)挖掘》試題與答案

1、一、解答題（滿分30 分，每小題 5 分）1. 怎樣理解數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)的關(guān)系？請(qǐng)?jiān)敿?xì)闡述之首先從數(shù)據(jù)源中抽取感興趣的數(shù)據(jù)，并把它組織成適合挖掘的 數(shù)據(jù)組織形式；然后，調(diào)用相應(yīng)的算法生成所需的知識(shí)； 最后對(duì)生成的知識(shí)模式進(jìn)行評(píng)估，并把有價(jià)值的知識(shí)集成到企業(yè)的智能系統(tǒng)中。知識(shí)發(fā)現(xiàn) 是一個(gè)指出數(shù)據(jù)中有效、嶄新、潛在的、有價(jià)值的、一個(gè)不可忽視的流程，其最終目標(biāo)是掌握數(shù)據(jù)的模式。流程步驟：先理解要應(yīng)用的領(lǐng)域、 熟悉相關(guān)知識(shí)，接著建立目標(biāo)數(shù)據(jù)集，并專注所選擇的數(shù)據(jù)子集； 再作數(shù)據(jù)預(yù)處理，剔除錯(cuò)誤或不一致的數(shù)據(jù)； 然后進(jìn)行數(shù)據(jù)簡(jiǎn)化與轉(zhuǎn)換工作；再通過數(shù)據(jù)挖掘的技術(shù)程序成為模式、做回歸分析或找出分類模型；最

2、后經(jīng)過解釋和評(píng)價(jià)成為有用的信息。2. 時(shí)間序列數(shù)據(jù)挖掘的方法有哪些，請(qǐng)?jiān)敿?xì)闡述之時(shí)間序列數(shù)據(jù)挖掘的方法有：1）、確定性時(shí)間序列預(yù)測(cè)方法 : 對(duì)于平穩(wěn)變化特征的時(shí)間序列來說， 假設(shè)未來行為與現(xiàn)在的行為有關(guān)， 利用屬性現(xiàn)在的值預(yù)測(cè)將來的值是可行的。 例如，要預(yù)測(cè)下周某種商品的銷售額， 可以用最近一段時(shí)間的實(shí)際銷售量來建立預(yù)測(cè)模型。2）、 隨機(jī)時(shí)間序列預(yù)測(cè)方法 :通過建立隨機(jī)模型，對(duì)隨機(jī)時(shí)間序列進(jìn)行分析，可以預(yù)測(cè)未來值。若時(shí)間序列是平穩(wěn)的，可以用自回歸(Auto Regressive，簡(jiǎn)稱AR) 模型、移動(dòng)回歸模型(MovingAverage，簡(jiǎn)稱MA) 或自回歸移動(dòng)平均(AutoRegressiv

3、e Moving Average，簡(jiǎn)稱 ARMA) 模型進(jìn)行分析預(yù)測(cè)。3）、其他方法 : 可用于時(shí)間序列預(yù)測(cè)的方法很多， 其中比較成功的是神經(jīng)網(wǎng)絡(luò)。由于大量的時(shí)間序列是非平穩(wěn)的， 因此特征參數(shù)和數(shù)據(jù)分布隨著時(shí)間的推移而變化。假如通過對(duì)某段歷史數(shù)據(jù)的訓(xùn)練， 通過數(shù)學(xué)統(tǒng)計(jì)模型估計(jì)神經(jīng)網(wǎng)絡(luò)的各層權(quán)重參數(shù)初值，就可能建立神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)模型，用于時(shí)間序列的預(yù)測(cè)。3. 數(shù)據(jù)挖掘的分類方法有哪些，請(qǐng)?jiān)敿?xì)闡述之分類方法歸結(jié)為四種類型：1）、基于距離的分類方法 : 距離的計(jì)算方法有多種， 最常用的是通過計(jì)算每個(gè)類的中心來完成， 在實(shí)際的計(jì)算中往往用距離來表征， 距離越近，相似性越大，距離越遠(yuǎn)，相似性越小。2）、決

4、策樹分類方法 :決策樹（ Decision Tree）的每個(gè)內(nèi)部結(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試，每個(gè)分枝代表一個(gè)測(cè)試輸出，而每個(gè)樹葉結(jié)點(diǎn)代表類或類分布。樹的最頂層結(jié)點(diǎn)是根結(jié)點(diǎn)。3）、貝葉斯分類方法 : 設(shè) X 是類標(biāo)號(hào)未知的數(shù)據(jù)樣本。設(shè) H 為某種假定，如數(shù)據(jù)樣本 X 屬于某特定的類 C。對(duì)于分類問題，我們希望確定 P(H|X)，即給定觀測(cè)數(shù)據(jù)樣本 X ，假定 H 成立的概率。4）、規(guī)則歸納方法 : 規(guī)則歸納有四種策略：減法、加法，先加后減、先減后加策略。a) 減法策略：以具體例子為出發(fā)點(diǎn)， 對(duì)例子進(jìn)行推廣或泛化， 推廣即減除條件（屬性值）或減除合取項(xiàng)（為了方便，我們不考慮增加析取項(xiàng)的推廣），使推

5、廣后的例子或規(guī)則不覆蓋任何反例。b) 加法策略：起始假設(shè)規(guī)則的條件部分為空（永真規(guī)則） ，如果該規(guī)則覆蓋了反例，則不停地向規(guī)則增加條件或合取項(xiàng)， 直到該規(guī)則不再覆蓋反例。c) 先加后減策略： 由于屬性間存在相關(guān)性， 因此可能某個(gè)條件的加入會(huì)導(dǎo)致前面加入的條件沒什么作用，因此需要減除前面的條件。d) 先減后加策略：道理同先加后減，也是為了處理屬性間的相關(guān)性。典型的規(guī)則歸納算法有AQ 、CN2 和 FOIL 等。4. 數(shù)據(jù)挖掘的聚類方法有哪些，請(qǐng)?jiān)敿?xì)闡述之?dāng)?shù)據(jù)挖掘的聚類方法 :1）、劃分方法（ Partitioning Methods）:給定一個(gè)有 n 個(gè)對(duì)象的數(shù)據(jù)集，劃分聚類技術(shù)將構(gòu)造數(shù)據(jù)k 個(gè)

6、劃分，每一個(gè)劃分就代表一個(gè)簇，kn。也就是說，它將數(shù)據(jù)劃分為 k 個(gè)簇，而且這 k 個(gè)劃分滿足下列條件：a) 每一個(gè)簇至少包含一個(gè)對(duì)象。b) 每一個(gè)對(duì)象屬于且僅屬于一個(gè)簇。對(duì)于給定的 k，算法首先給出一個(gè)初始的劃分方法，以后通過反復(fù)迭代的方法改變劃分，使得每一次改進(jìn)之后的劃分方案都較前一次更好。1）、層次聚類 : 層次聚類方法對(duì)給定的數(shù)據(jù)集進(jìn)行層次的分解，直到某種條件滿足為止。具體又可分為：a) 凝聚的層次聚類：一種自底向上的策略，首先將每個(gè)對(duì)象作為一個(gè)簇，然后合并這些原子簇為越來越大的簇，直到某個(gè)終結(jié)條件被滿足。b) 分裂的層次聚類： 采用自頂向下的策略， 它首先將所有對(duì)象置于一個(gè)簇中，然后

7、逐漸細(xì)分為越來越小的簇，直到達(dá)到了某個(gè)終結(jié)條件。層次凝聚的代表是AGNES 算法。層次分裂的代表是DIANA 算法。2）密度聚類方法 : 密度聚類方法的指導(dǎo)思想是，只要一個(gè)區(qū)域中的點(diǎn)的密度大于某個(gè)域值，就把它加到與之相近的聚類中去。代表算法有： DBSCAN 、OPTICS、DENCLUE 算法等。3）其它聚類方法 :STING(Statistaical Information Grid_based method)是一種基于網(wǎng)格的多分辨率聚類技術(shù)，它將空間區(qū)域劃分為矩形單元。STING算法采用了一種多分辨率的方法來進(jìn)行聚類分析，該聚類算法的質(zhì)量取決于網(wǎng)格結(jié)構(gòu)最低層的粒度。如果粒度比較細(xì)，處理的

8、代價(jià)會(huì)顯著增加；但如果粒度較粗，則聚類質(zhì)量會(huì)受到影響。5請(qǐng)闡述數(shù)據(jù)挖掘的基本過程及步驟一、業(yè)務(wù)理解：業(yè)務(wù)理解包括確定商業(yè)對(duì)象、了解現(xiàn)狀、建立數(shù)據(jù)挖掘目標(biāo)和制定計(jì)劃書。應(yīng)該是對(duì)數(shù)據(jù)挖掘的目標(biāo)有一個(gè)清晰的認(rèn)識(shí)， 知道利潤(rùn)所在， 其中包括數(shù)據(jù)收集、 數(shù)據(jù)分析和數(shù)據(jù)報(bào)告等步驟。二、數(shù)據(jù)理解： 一旦商業(yè)對(duì)象和計(jì)劃書確定完備， 數(shù)據(jù)理解就考慮將所需要的數(shù)據(jù)。這一過程包括原始數(shù)據(jù)收集、數(shù)據(jù)描述、數(shù)據(jù)探索和數(shù)據(jù)質(zhì)量核查等。三、數(shù)據(jù)準(zhǔn)備：確定可用的數(shù)據(jù)資源以后，需要對(duì)此進(jìn)行篩選、清理、調(diào)整為所需要的形式。數(shù)據(jù)整理和數(shù)據(jù)轉(zhuǎn)換等數(shù)據(jù)建模的準(zhǔn)備工作需要在這一階段完成。 更深層次的數(shù)據(jù)探索也可以在這一階段進(jìn)行， 新增模

9、型的應(yīng)用再次提供了在業(yè)務(wù)理解基礎(chǔ)上看清楚數(shù)據(jù)模式的機(jī)會(huì)。四、建立模型：數(shù)據(jù)模型建立是應(yīng)用數(shù)據(jù)挖掘軟件不不同的情景下獲得結(jié)果的過程。五、模型評(píng)估： 數(shù)據(jù)解釋階段是至關(guān)重要的， 要對(duì)建立的模型是否能夠達(dá)到問題解決的目的進(jìn)行研究，即包括模型是否能夠達(dá)到研究的目標(biāo)；模型是否能夠用合適的方法顯示。六、模型發(fā)布： 數(shù)據(jù)挖掘既可以應(yīng)用于核實(shí)先前的假設(shè)，也可以應(yīng)用于知識(shí)發(fā)現(xiàn)（識(shí)別未預(yù)期的有用的關(guān)系） 。6. 為什么說強(qiáng)關(guān)聯(lián)規(guī)則不一定都是有效的，請(qǐng)舉例說明之。并不是所有的強(qiáng)關(guān)聯(lián)規(guī)則都是有效的。例如，一個(gè)谷類早餐的零售商對(duì) 5000 名學(xué)生的調(diào)查的案例。 數(shù)據(jù)表明： 60%的學(xué)生打籃球， 75%的學(xué)生吃這類早餐，

10、 40%的學(xué)生即打籃球吃這類早餐。假設(shè)支持度閾值s=0.4，置信度閾值 c=60%?；谏厦鏀?shù)據(jù)和假設(shè)我們可挖掘出強(qiáng)關(guān)聯(lián)規(guī)則“(打籃球 ) (吃早餐 )”，因?yàn)槠?(打籃球 )和(吃早餐)的支持度都大于支持度閾值，都是頻繁項(xiàng)，而規(guī)則的置信度c=40%/60%=66.6%也大于置信度閾值。然而，以上的關(guān)聯(lián)規(guī)則很容易產(chǎn)生誤解，因?yàn)槌栽绮偷谋壤秊?5%，大于 66%。也就是說，打籃球與吃早餐實(shí)際上是負(fù)關(guān)聯(lián)的。二、分析題（滿分20 分，每小題 10 分）1、請(qǐng)分析關(guān)聯(lián)規(guī)則挖掘方法中，項(xiàng)目集格空間理論、發(fā)展及其在數(shù)據(jù)挖掘中的應(yīng)用價(jià)值。項(xiàng)目集格空間理論Agrawal 等人建立了用于事務(wù)數(shù)據(jù)庫挖掘的項(xiàng)目集格

11、空間理論（1993,Appriori 屬性）。定理（ Appriori 屬性 1）. 如果項(xiàng)目集 X 是頻繁項(xiàng)目集，那么它的所有非空子集都是頻繁項(xiàng)目集。定理（ Appriori 屬性 2）.如果項(xiàng)目集 X 是非頻繁項(xiàng)目集，那么它的所有超集都是非頻繁項(xiàng)目集。項(xiàng)目集格空間理論發(fā)展隨著數(shù)據(jù)庫容量的增大， 重復(fù)訪問數(shù)據(jù)庫 （外存）將導(dǎo)致性能低下。 因此，探索新的理論和算法來減少數(shù)據(jù)庫的掃描次數(shù)和侯選集空間占用， 已經(jīng)成為近年來關(guān)聯(lián)規(guī)則挖掘研究的熱點(diǎn)之一。兩個(gè)典型的方法： Close 算法、 FP-tree算法2、請(qǐng)分析 Web 挖掘技術(shù)所采用的方法及其在數(shù)據(jù)挖掘中的應(yīng)用價(jià)值。Web 挖掘依靠它所挖掘的

12、信息來源可以分為：Web 內(nèi)容挖掘（ Web Content Mining ）：對(duì)站點(diǎn)的 Web 頁面的各類信息進(jìn)行集成、概化、分類等，挖掘某類信息所蘊(yùn)含的知識(shí)模式。Web 訪問信息挖掘（ Web Usage Mining）：Web 訪問信息挖掘是對(duì)用戶訪問 Web 時(shí)在服務(wù)器方留下的訪問記錄進(jìn)行挖掘。通過分析日志記錄中的規(guī)律，可以識(shí)別用戶的忠實(shí)度、喜好、滿意度，可以發(fā)現(xiàn)潛在用戶，增強(qiáng)站點(diǎn)的服務(wù)競(jìng)爭(zhēng)力。Web 結(jié)構(gòu)挖掘（ Web Structure Mining）：Web 結(jié)構(gòu)挖掘是對(duì)Web 頁面之間的鏈接結(jié)構(gòu)進(jìn)行挖掘。在整個(gè) Web 空間里，有用的知識(shí)不僅包含在 Web 頁面的內(nèi)容之中，而且

13、也包含在頁面的鏈接結(jié)構(gòu)之中。對(duì)于給定的 Web 頁面集合，通過結(jié)構(gòu)挖掘可以發(fā)現(xiàn)頁面之間的關(guān)聯(lián)信息，頁面之間的包含、引用或者從屬關(guān)系等。從大量的信息中發(fā)現(xiàn)用戶感興趣的信息 ：因特網(wǎng)上蘊(yùn)藏著大量的信息，通過簡(jiǎn)單的瀏覽或關(guān)鍵詞匹配的搜索引擎得到的是孤立而凌亂的 “表面信息 ”，Web 挖掘可以發(fā)現(xiàn)潛在的、豐富的關(guān)聯(lián)信息。將 Web 上的豐富信息轉(zhuǎn)變成有用的知識(shí)： Web 挖掘是面向 Web 數(shù)據(jù)進(jìn)行分析和知識(shí)提取的。 因特網(wǎng)中頁面內(nèi)部、 頁面間、頁面鏈接、頁面訪問等都包含大量對(duì)用戶可用的信息， 而這些信息的深層次含義是很難被用戶直接使用的，必須經(jīng)過濃縮和提煉。對(duì)用戶進(jìn)行信息個(gè)性化： 網(wǎng)站信息的個(gè)性化

14、是將來的發(fā)展趨勢(shì)。通過 Web 挖掘，可以達(dá)到對(duì)用戶訪問行為、頻度、內(nèi)容等的分析，可以得到關(guān)于群體用戶訪問行為和方式的普遍知識(shí)， 用以改進(jìn) Web服務(wù)方的設(shè)計(jì)，提供個(gè)性化的服務(wù)。三、證明題（滿分16 分）1證明頻繁集的所有非空子集必須也是頻繁的。證明 1反證法。根據(jù)定義，如果項(xiàng)集 I 滿足最小支持度閾值min_ sup ，則 I 不是頻繁的，即 p( I )min_ sup 。如果項(xiàng) A 添加到 I , 則結(jié)果項(xiàng)集間（即IA ）不可能比 I 更頻繁出現(xiàn)。因此，IA 也不是頻繁的，即P（ IA ） min_sup 。矛盾。證明 2 設(shè) X 是一個(gè)項(xiàng)目集，事務(wù)數(shù)據(jù)庫 T 中支持 X 的元組數(shù)為 s

15、。對(duì) X 的任一非空子集為 Y ，設(shè) T 中支持 Y 的元組數(shù)為 s1。根據(jù)項(xiàng)目集支持?jǐn)?shù)的定義， 很容易知道支持X 的元組一定支持 Y ，所以 s1 s，即 support（Y ） support（X ）。按假設(shè)：項(xiàng)目集X 是頻繁項(xiàng)目集，即support(X) minsupport，所以 support（Y ） support（X ） minsupport，因此 Y 是頻繁項(xiàng)目集。2Apriori 的一種變形將事務(wù)數(shù)據(jù)庫D證明在 D 中是頻繁的任何項(xiàng)集至少在證明：給定頻繁項(xiàng)集 l 和 l 的子集 s ，證明規(guī)則“ s中的事務(wù)劃分為 若干個(gè)不重疊的部分。D 中的一個(gè)部分中是頻繁的。(ls ) ”

16、的置信度不可能大于 “ s(ls) ”的置信度。其中，s是 s 的子集。根據(jù)定義，規(guī)則AB 的置信度為： conf則 s(ls ) 的置信度為： confn(s規(guī)則 s(ls) 的置信度同理可得：conf以規(guī)則“ s(ls ) ”的置信度不可能大于“n( AB) / n( A)n( A) 表示項(xiàng)集(ls ) / n(s )n(l ) / n(s )n(l ) / n(s) ，又因?yàn)?s 是 s 的子集，s(ls) ”的置信度A 出現(xiàn)的次數(shù)n( s )n( s)規(guī)，所四、算法分析題（滿分14 分）1. 描述決策樹算法的主要思想。建造一個(gè)決策樹，有五個(gè)主要步驟：根據(jù)已知的分類，從數(shù)據(jù)D 中找到例子

17、 S。確定最佳謂詞 p 用來分類。一般首先在較粗的層次中尋找相關(guān)謂詞，然后再在較為細(xì)化的層次。找到最佳的緩沖區(qū)大小和形狀。 對(duì)于取樣中的每個(gè)實(shí)體， 它周圍的區(qū)域被稱為緩沖區(qū)。目標(biāo)是選擇一個(gè)能產(chǎn)生對(duì)測(cè)試集中的類型進(jìn)行最不同的緩沖區(qū)。使用 p 和 C，對(duì)每個(gè)緩沖區(qū)歸納謂詞。使用泛化的謂詞和ID3 建造二叉樹 T?？臻g決策樹算法輸入：空間數(shù)據(jù)庫D；概念層次 C；預(yù)定的類別。輸出：二叉決策樹T。（ 1）根據(jù)預(yù)定的類別，從數(shù)據(jù) D 中找到例子 S；（ 2）確定最佳謂詞 p 用來分類；（ 3）找到最佳的緩沖區(qū)大小和形狀；（ 4）使用 p 和 C，對(duì)每個(gè)緩沖區(qū)歸納謂詞；（ 5）使用泛化的謂詞和 ID3 建造二叉樹 T.2. 指出算法的不足之處，應(yīng)該從哪些方面增強(qiáng)算法的功能和性能。對(duì)任何數(shù)量的訓(xùn)練集，總是能找到相應(yīng)的多個(gè)線性判別函數(shù)把它分類，但是這樣生成的樹的深度可能太大因?yàn)椋?雖然使用了最好的特征進(jìn)行分類，但還是可能存在一些特征對(duì)分類很有用， 盡管不是像最好的特征那樣有用，卻沒有用到一個(gè)直覺是：有些特征對(duì)某些類別有效，但是對(duì)另外一些則無效，甚至可能有副作用，如果能把這些特征選擇出來，一次就能最大限度地把多個(gè)類別分開MBDT正是基于這個(gè)直覺MBDT 通過在每個(gè)子集上選擇最能有效分類的那些特征使用馬氏距離進(jìn)行分類如果某個(gè)子集無法有效分類(通過閾值判斷) ，就選擇最好的一個(gè)進(jìn)行分