數(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ù)簡化與轉(zhuǎn)換工作；再通過數(shù)據(jù)挖掘的技術(shù)程序成為模式、做回歸分析或找出分類模型； 最后經(jīng)過解釋和

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

3、age簡稱ARMA）模型進(jìn)行分析預(yù)測。3）、其他方法：可用于時(shí)間序列預(yù)測的方法很多，其中比較成功的是神經(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ù)測模型，用于時(shí)間序列的預(yù)測。3. 數(shù)據(jù)挖掘的分類方法有哪些，請(qǐng)?jiān)敿?xì)闡述之分類方法歸結(jié)為四種類型：1）、基于距離的分類方法：距離的計(jì)算方法有多種，最常用的是通過計(jì) 算每個(gè)類的中心來完成，在實(shí)際的計(jì)算中往往用距離來表征， 距離越近, 相似性越大，距離越遠(yuǎn)，相似性越小。2）、決策樹分類方法：決策樹（Decision

4、Tree）的每個(gè)內(nèi)部結(jié)點(diǎn)表示在一個(gè) 屬性上的測試，每個(gè)分枝代表一個(gè)測試輸出，而每個(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）, 即給定觀測數(shù)據(jù)樣本X，假定H成立的概率。4）、規(guī)則歸納方法：規(guī)則歸納有四種策略：減法、加法，先加后減、先減后加策略。a）減法策略：以具體例子為出發(fā)點(diǎn)，對(duì)例子進(jìn)行推廣或泛化，推廣即減 除條件（屬性值）或減除合取項(xiàng)（為了方便，我們不考慮增加析取項(xiàng) 的推廣），使推廣后的例子或規(guī)則不覆蓋任何反例。b）加法策略：起始假設(shè)規(guī)則的條件部

5、分為空（永真規(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è)劃分，每一個(gè)劃分就代表一個(gè)簇，k_ n。也就是說，它將數(shù) 據(jù)劃分為k個(gè)簇，而且這k個(gè)

6、劃分滿足下列條件：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è)簇 中，然后逐漸細(xì)分為越來越小的簇，直到達(dá)到了某個(gè)終結(jié)條件。層次凝聚的代表是AGNES算法。層次分裂的代表是

7、DIANA算法。2）密度聚類方法：密度聚類方法的指導(dǎo)思想是，只要一個(gè)區(qū)域中的點(diǎn)的密 度大于某個(gè)域值，就把它加到與之相近的聚類中去。代表算法有：DBSCAN、OPTICS、DENCLUE 算法等。3）其它聚類方法：STING（Statistaical In formation Grid_based method）是一種基于網(wǎng)格的多分辨率聚類技術(shù)，它將空間區(qū)域劃分為矩形單元。STING算法采用了一種多分辨率的方法來進(jìn)行聚類分析，該聚類算法的質(zhì)量取 決于網(wǎng)格結(jié)構(gòu)最低層的粒度。如果粒度比較細(xì)，處理的代價(jià)會(huì)顯著增加；但如果粒度較粗，則聚類質(zhì)量會(huì)受到影響。5 請(qǐng)闡述數(shù)據(jù)挖掘的基本過程及步驟一、業(yè)務(wù)理解：業(yè)

8、務(wù)理解包括確定商業(yè)對(duì)象、了解現(xiàn)狀、建立數(shù)據(jù)挖掘目標(biāo)和制定計(jì)劃書。應(yīng)該是對(duì)數(shù)據(jù)挖掘的目標(biāo)有一個(gè)清晰的認(rèn)識(shí)，知道利潤所在，其中包括數(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)行，新增模型的應(yīng)用再次提供了在業(yè)務(wù)理解基礎(chǔ)上看清楚數(shù)據(jù)模式的 機(jī)會(huì)。四、建立模型：數(shù)據(jù)模型建立是應(yīng)用數(shù)據(jù)挖掘軟件不不同的

9、情景下獲得結(jié)果的過程。五、模型評(píng)估：數(shù)據(jù)解釋階段是至關(guān)重要的， 要對(duì)建立的模型是否能夠達(dá)到問題解決的目的 進(jìn)行研究，即包括模型是否能夠達(dá)到研究的目標(biāo)；模型是否能夠用合適的方法顯示。也可以應(yīng)用于知識(shí)發(fā)現(xiàn)（識(shí)別未預(yù)六、模型發(fā)布：數(shù)據(jù)挖掘既可以應(yīng)用于核實(shí)先前的假設(shè), 期的有用的關(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é)生吃這類早餐，40% 的學(xué)生即打籃球吃這類早餐。假設(shè)支持度閾值 s=0.4,置信度閾值c=60%。基于 上面數(shù)據(jù)和假設(shè)我們可挖掘出強(qiáng)關(guān)

10、聯(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)目集格空間理論（1993,Appriori 屬性）。定理（Appriori屬性1）.如果項(xiàng)目集X是頻繁項(xiàng)目集，那么它的所有 非空子集都是

11、頻繁項(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挖掘依靠它所挖掘的信息來源可以分為：Web內(nèi)容挖掘（Web Content Mining）:對(duì)站點(diǎn)的 Web頁面的各類 信息進(jìn)行集成、概化、分類等，挖掘某類信息所蘊(yùn)含的知識(shí)模式。W

12、eb訪問信息挖掘（Web Usage Mining）: Web訪問信息挖掘是對(duì) 用戶訪問Web時(shí)在服務(wù)器方留下的訪問記錄進(jìn)行挖掘。通過分析 日志記錄中的規(guī)律，可以識(shí)別用戶的忠實(shí)度、喜好、滿意度，可以 發(fā)現(xiàn)潛在用戶，增強(qiáng)站點(diǎn)的服務(wù)競爭力。Web結(jié)構(gòu)挖掘（Web Structure Mining）: Web結(jié)構(gòu)挖掘是對(duì) Web頁面之間的鏈接結(jié)構(gòu)進(jìn)行挖掘。在整個(gè)Web空間里，有用的知識(shí)不僅包含在 Web頁面的內(nèi)容之中，而且也包含在頁面的鏈接結(jié)構(gòu)之 中。對(duì)于給定的 Web頁面集合，通過結(jié)構(gòu)挖掘可以發(fā)現(xiàn)頁面之間 的關(guān)聯(lián)信息，頁面之間的包含、引用或者從屬關(guān)系等。從大量的信息中發(fā)現(xiàn)用戶感興趣的信息：因特網(wǎng)上

13、蘊(yù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è)性化是將來的發(fā)展趨勢。 通 過Web挖掘，可以達(dá)到對(duì)用戶訪問行為、頻度、內(nèi)容等的分析， 可以得到關(guān)于群體用戶訪問行為和方式的普遍知識(shí)，用以改進(jìn)Web服務(wù)方的設(shè)計(jì)，提供個(gè)性化的服務(wù)。三、證明題(滿分16

14、分)1 證明頻繁集的所有非空子集必須也是頻繁的。證明1反證法。根據(jù)定義，如果項(xiàng)集|滿足最小支持度閾值 min_ sup，則I不是頻繁的，即p(l) c min_ sup。如果項(xiàng)a添加到I ,則結(jié)果項(xiàng)集間(即I 一 A)不可能比I更頻繁出現(xiàn)。因此，I 一 A也不是頻繁的，即P ( IA) s， 即 support (丫) support (X) o按假設(shè)：項(xiàng)目集 X是頻繁項(xiàng)目集，即support(X) min support，所以 support (丫) support (X) min support，因此 丫 是頻繁項(xiàng)目集。2. Apriori的一種變形將事務(wù)數(shù)據(jù)庫D中的事務(wù)劃分為若干個(gè)不重疊

15、的部分。 證明在D中是頻繁的任何項(xiàng)集至少在 D中的一個(gè)部分中是頻繁的。證明：給定頻繁項(xiàng)集I和I的子集s，證明規(guī)則“ S = (I _ S)”的置信度不可能大于“ s= (I _ s) ” 的置信度。其中，s 是 S的子集。根據(jù)定義，規(guī)則 A= B的置信度為：conf =n(A B)/ n(A) n( A)表示項(xiàng)集a出現(xiàn)的次數(shù) 規(guī) 則 s= (ls)的置信度為：conf =n(s (Is)/n(s ) n(l)/ n(s )規(guī)則s= (I -s)的置信度同理可得：conf二n (I)/n(s)，又因?yàn)閟 是 s的子集，n (s) . n(s)，所以規(guī)則“ s二(I - s) ”的置信度不可能大于

16、“(I -s) ”的置信度四、算法分析題(滿分14分)1. 描述決策樹算法的主要思想。建造一個(gè)決策樹，有五個(gè)主要步驟：根據(jù)已知的分類，從數(shù)據(jù) D中找到例子S。確定最佳謂詞p用來分類。一般首先在較粗的層次中尋找相關(guān)謂 詞，然后再在較為細(xì)化的層次。找到最佳的緩沖區(qū)大小和形狀。對(duì)于取樣中的每個(gè)實(shí)體，它周圍的 區(qū)域被稱為緩沖區(qū)。目標(biāo)是選擇一個(gè)能產(chǎn)生對(duì)測試集中的類型進(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用

17、來分類；(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)行分類.由于事先需要有標(biāo)簽的分類訓(xùn)練集，所以這是有監(jiān)