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

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

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

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

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

5、分為空（永真規(guī)則），如果該規(guī)則 覆蓋了反例，則不停地向規(guī)則增加條件或合取項， 直到該規(guī)則不再覆 蓋反例。c）先加后減策略：由于屬性間存在相關(guān)性，因此可能某個條件的加入會 導致前面加入的條件沒什么作用，因此需要減除前面的條件。d）先減后加策略：道理同先加后減，也是為了處理屬性間的相關(guān)性。 典型的規(guī)則歸納算法有 AQ、CN2和FOIL等。4. 數(shù)據(jù)挖掘的聚類方法有哪些，請詳細闡述之數(shù)據(jù)挖掘的聚類方法：1）、劃分方法（Partitioning Methods）:給定一個有n個對象的數(shù)據(jù)集，劃分聚類 技術(shù)將構(gòu)造數(shù)據(jù)k個劃分，每一個劃分就代表一個簇，k_ n。也就是說，它將數(shù) 據(jù)劃分為k個簇，而且這k個

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

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

8、務(wù)理解包括確定商業(yè)對象、了解現(xiàn)狀、建立數(shù)據(jù)挖掘目標和制定計劃書。應該是對數(shù)據(jù)挖掘的目標有一個清晰的認識，知道利潤所在，其中包括數(shù)據(jù)收集、 數(shù)據(jù)分析和數(shù)據(jù)報告等步驟。二、 數(shù)據(jù)理解：一旦商業(yè)對象和計劃書確定完備，數(shù)據(jù)理解就考慮將所需要的數(shù)據(jù)。這一過 程包括原始數(shù)據(jù)收集、數(shù)據(jù)描述、數(shù)據(jù)探索和數(shù)據(jù)質(zhì)量核查等。三、數(shù)據(jù)準備：確定可用的數(shù)據(jù)資源以后，需要對此進行篩選、清理、調(diào)整為所需要的形式。數(shù)據(jù)整理和數(shù)據(jù)轉(zhuǎn)換等數(shù)據(jù)建模的準備工作需要在這一階段完成。更深層次的數(shù)據(jù)探索也可以在這一階段進行，新增模型的應用再次提供了在業(yè)務(wù)理解基礎(chǔ)上看清楚數(shù)據(jù)模式的 機會。四、建立模型：數(shù)據(jù)模型建立是應用數(shù)據(jù)挖掘軟件不不同的

9、情景下獲得結(jié)果的過程。五、模型評估：數(shù)據(jù)解釋階段是至關(guān)重要的， 要對建立的模型是否能夠達到問題解決的目的 進行研究，即包括模型是否能夠達到研究的目標；模型是否能夠用合適的方法顯示。也可以應用于知識發(fā)現(xiàn)（識別未預六、模型發(fā)布：數(shù)據(jù)挖掘既可以應用于核實先前的假設(shè), 期的有用的關(guān)系）6.為什么說強關(guān)聯(lián)規(guī)則不一定都是有效的，請舉例說明之。并不是所有的強關(guān)聯(lián)規(guī)則都是有效的。例如，一個谷類早餐的零售商對 5000名 學生的調(diào)查的案例。數(shù)據(jù)表明：60%的學生打籃球，75%的學生吃這類早餐，40% 的學生即打籃球吃這類早餐。假設(shè)支持度閾值 s=0.4,置信度閾值c=60%?；?上面數(shù)據(jù)和假設(shè)我們可挖掘出強關(guān)

10、聯(lián)規(guī)則 （打籃球）-（吃早餐）”，因為其（打籃球） 和（吃早餐）的支持度都大于支持度閾值，都是頻繁項，而規(guī)則的置信度 c=40%/60%=66.6%也大于置信度閾值。然而，以上的關(guān)聯(lián)規(guī)則很容易產(chǎn)生誤解，因為吃早餐的比例為75%,大于66%。也就是說，打籃球與吃早餐實際上是負關(guān)聯(lián)的。二、分析題（滿分20分，每小題10分）1、請分析關(guān)聯(lián)規(guī)則挖掘方法中，項目集格空間理論、發(fā)展及其在數(shù)據(jù)挖掘中的 應用價值。項目集格空間理論Agrawal等人建立了用于事務(wù)數(shù)據(jù)庫挖掘的項目集格空間理論（1993,Appriori 屬性）。定理（Appriori屬性1）.如果項目集X是頻繁項目集，那么它的所有 非空子集都是

11、頻繁項目集。定理（Appriori屬性2）.如果項目集X是非頻繁項目集，那么它的所有 超集都是非頻繁項目集。項目集格空間理論發(fā)展隨著數(shù)據(jù)庫容量的增大，重復訪問數(shù)據(jù)庫（外存）將導致性能低下。因此， 探索新的理論和算法來減少數(shù)據(jù)庫的掃描次數(shù)和侯選集空間占用， 已經(jīng)成 為近年來關(guān)聯(lián)規(guī)則挖掘研究的熱點之一。兩個典型的方法：Close算法、FP-tree算法2、請分析Web挖掘技術(shù)所采用的方法及其在數(shù)據(jù)挖掘中的應用價值。Web挖掘依靠它所挖掘的信息來源可以分為：Web內(nèi)容挖掘（Web Content Mining）:對站點的 Web頁面的各類 信息進行集成、概化、分類等，挖掘某類信息所蘊含的知識模式。W

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

13、蘊藏著大量的信息，通過簡單的瀏覽或關(guān)鍵詞匹配的搜索引擎得到的是孤立而凌 亂的 表面信息” ，Web挖掘可以發(fā)現(xiàn)潛在的、豐富的關(guān)聯(lián)信息。將Web上的豐富信息轉(zhuǎn)變成有用的知識： Web挖掘是面向Web數(shù) 據(jù)進行分析和知識提取的。因特網(wǎng)中頁面內(nèi)部、頁面間、頁面鏈接、 頁面訪問等都包含大量對用戶可用的信息，而這些信息的深層次含義是很難被用戶直接使用的，必須經(jīng)過濃縮和提煉。對用戶進行信息個性化：網(wǎng)站信息的個性化是將來的發(fā)展趨勢。 通 過Web挖掘，可以達到對用戶訪問行為、頻度、內(nèi)容等的分析， 可以得到關(guān)于群體用戶訪問行為和方式的普遍知識，用以改進Web服務(wù)方的設(shè)計，提供個性化的服務(wù)。三、證明題(滿分16

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

15、的部分。 證明在D中是頻繁的任何項集至少在 D中的一個部分中是頻繁的。證明：給定頻繁項集I和I的子集s，證明規(guī)則“ S = (I _ S)”的置信度不可能大于“ s= (I _ s) ” 的置信度。其中，s 是 S的子集。根據(jù)定義，規(guī)則 A= B的置信度為：conf =n(A B)/ n(A) n( A)表示項集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)，又因為s 是 s的子集，n (s) . n(s)，所以規(guī)則“ s二(I - s) ”的置信度不可能大于

16、“(I -s) ”的置信度四、算法分析題(滿分14分)1. 描述決策樹算法的主要思想。建造一個決策樹，有五個主要步驟：根據(jù)已知的分類，從數(shù)據(jù) D中找到例子S。確定最佳謂詞p用來分類。一般首先在較粗的層次中尋找相關(guān)謂 詞，然后再在較為細化的層次。找到最佳的緩沖區(qū)大小和形狀。對于取樣中的每個實體，它周圍的 區(qū)域被稱為緩沖區(qū)。目標是選擇一個能產(chǎn)生對測試集中的類型進行 最不同的緩沖區(qū)。使用p和C,對每個緩沖區(qū)歸納謂詞。使用泛化的謂詞和ID3建造二叉樹T?？臻g決策樹算法輸入：空間數(shù)據(jù)庫D;概念層次C;預定的類別。輸出：二叉決策樹T。(1) 根據(jù)預定的類別，從數(shù)據(jù) D中找到例子S；(2) 確定最佳謂詞p用

17、來分類；(3) 找到最佳的緩沖區(qū)大小和形狀；(4) 使用p和C,對每個緩沖區(qū)歸納謂詞；(5) 使用泛化的謂詞和ID3建造二叉樹T.2. 指出算法的不足之處，應該從哪些方面增強算法的功能和性能。對任何數(shù)量的訓練集，總是能找到相應的多個線性判別函數(shù)把它分類，但是這樣生成的樹的深度可能太大.因為，雖然使用了最好的特征進行分類，但還是可能存在一些特征對分類很有用，盡管不是像最好的特征那樣有用，卻沒有用到一個直覺是：有些特征對某些類別有效，但是對另外一些則無效，甚至可能有副作用，如果能把這些特征選擇出來，一次就能最大限度地把多個類別分開.MBDT正是基于這個直覺.MBDT通過在每個子集上選擇最能有效分類的那些特征使用馬氏距離進行分類如果某個子集無法有效分類（通過閾值判斷），就選擇最好的一個進行分類.由于事先需要有標簽的分類訓練集，所以這是有監(jiān)