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

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

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

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

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

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

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

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

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

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

10、餐， 40% 的學(xué)生即打籃球吃這類早餐。假設(shè)支持度閾值s=0.4,置信度閾值c=60%。基于上面數(shù)據(jù)和假設(shè)我們可挖掘出強關(guān)聯(lián)規(guī)那么打籃球-吃早餐,因為其打籃球和吃早餐的支持度都大于支持度閾值，都是頻繁項，而規(guī)那么的置信度 c=40%/60%=66.6%也大于置信度閾值。然而，以上的關(guān)聯(lián)規(guī)那么很容易產(chǎn)生誤解，因為吃早餐的比例為 75%，大于 66%也就是說，打籃球與吃早餐實際上是負(fù)關(guān)聯(lián)的二、分析題總分值 20 分，每題 10 分1、請分析關(guān)聯(lián)規(guī)那么挖掘方法中，工程集格空間理論、開展及其在數(shù)據(jù)挖掘中的 應(yīng)用價值。工程集格空間理論Agrawal 等人建立了用于事務(wù)數(shù)據(jù)庫挖掘的工程集格空間理論 199

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

12、Web Content Mining:對站點的 Web頁面的各類 信息進行集成、概化、分類等，挖掘某類信息所蘊含的知識模式。Web 訪問信息挖掘 Web Usage Mining： Web 訪問信息挖掘是對 用戶訪問 Web 時在效勞器方留下的訪問記錄進行挖掘。通過分析 日志記錄中的規(guī)律，可以識別用戶的忠實度、喜好、滿意度，可以 發(fā)現(xiàn)潛在用戶，增強站點的效勞競爭力。Web結(jié)構(gòu)挖掘Web Structure Mining: Web結(jié)構(gòu)挖掘是對 Web頁 面之間的鏈接結(jié)構(gòu)進行挖掘。在整個 Web 空間里，有用的知識不 僅包含在 Web 頁面的內(nèi)容之中，而且也包含在頁面的鏈接結(jié)構(gòu)之 中。對于給定的

13、Web 頁面集合，通過結(jié)構(gòu)挖掘可以發(fā)現(xiàn)頁面之間 的關(guān)聯(lián)信息，頁面之間的包含、引用或者附屬關(guān)系等。 從大量的信息中發(fā)現(xiàn)用戶感興趣的信息 ：因特網(wǎng)上蘊藏著大量的 信息，通過簡單的瀏覽或關(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)站信息的個性化是將來的開展趨勢。 通 過 Web 挖掘

14、，可以到達(dá)對用戶訪問行為、頻度、內(nèi)容等的分析， 可以得到關(guān)于群體用戶訪問行為和方式的普遍知識， 用以改進 Web 效勞方的設(shè)計，提供個性化的效勞。三、證明題(總分值 16 分)1證明頻繁集的所有非空子集必須也是頻繁的。證明 1反證法。根據(jù)定義，如果項集I滿足最小支持度閾值 min_ sup，那么I不是頻繁的，即p(l) min_ sup。如果項a添加到I ,那么結(jié)果項集間(即IA)不可能比I更頻繁出現(xiàn)。因此，I A也不是頻繁的，即P ( I A) < min_sup。矛盾。證明2設(shè)X是一個工程集，事務(wù)數(shù)據(jù)庫 T中支持X的元組數(shù)為S。對X的任 一非空子集為丫，設(shè)T中支持丫的元組數(shù)為si。根

15、據(jù)工程集支持?jǐn)?shù)的定義，很容易知道支持X的元組一定支持丫，所以si > s，即 support (丫)> support (X)。按假設(shè)：工程集 X是頻繁工程集，即support(X)> min support，所以 support (丫) > support (X) > min support，因此 丫 是頻繁工程集。2Apriori 的一種變形將事務(wù)數(shù)據(jù)庫 D 中的事務(wù)劃分為 假設(shè)干個不重疊的局部。 證明在 D 中是頻繁的任何項集至少在 D 中的一個局部中是頻繁的。證明：給定頻繁項集I和I的子集s，證明規(guī)那么“ s (l s)的置信度不可能大于“ s (l s)

16、 的置信度。其中， s 是 s 的子集。根據(jù)定義，規(guī)那么 A B的置信度為：conf n(A B)/ n(A) n( A)表示項集a出現(xiàn)的次數(shù) 規(guī) 那么 s (I s )的置信度為：conf n(s (I s) / n(s ) n (I)/n(s) 規(guī)那么s (I s)的置信度同理可得：co nfn (I)/n(s)，又因為s是s的子集，n (s) n(s)，所以規(guī)那么“ s(I s) 的置信度不可能大于“ s (I s) 的置信度四、算法分析題(總分值 14 分)1. 描述決策樹算法的主要思想。建造一個決策樹，有五個主要步驟：根據(jù)的分類，從數(shù)據(jù) D 中找到例子 S。確定最正確謂詞 p 用來分

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