數(shù)據(jù)挖掘作業(yè)

1、1、給 出 KDD 的 定 義 和 處 理 過 程KDD的定義是：從大量數(shù)據(jù)中提取出可信的、新穎的、有用的且可以被人理解 的模式的高級(jí)處理過程。因此，KDD是一個(gè)高級(jí)的處理過程，它從數(shù)據(jù)集中識(shí)別出 以模式形式表示的知識(shí)。這里的“模式”可以看成知識(shí)的雛形，經(jīng)過驗(yàn)證、完善后 形成知識(shí)：高級(jí)的處理過程”是指一個(gè)多步驟的處理過程，多步驟之間相互影響反復(fù) 調(diào)整，形成一種螺旋式上升的過程。KDD的全過程有五個(gè)步驟：1、數(shù)據(jù)選擇：確定發(fā)現(xiàn)任務(wù)的操作對(duì)象，即目標(biāo)數(shù) 據(jù)，它是根據(jù)用戶的需要從原始數(shù)據(jù)庫中抽取的一組數(shù)據(jù)；2、數(shù)據(jù)預(yù)處理：一般可能包括消除噪聲、推到技術(shù)卻只數(shù)據(jù)、消除重復(fù)記錄、完成數(shù)據(jù)類型轉(zhuǎn)換等；3、

2、數(shù)據(jù)轉(zhuǎn)換：其主要目的是消減數(shù)據(jù)維數(shù)或降維，即從初始特征中找出真正有用的特征 以減少數(shù)據(jù)開采時(shí)要考慮的特征或變量個(gè)數(shù)；4、數(shù)據(jù)挖掘：這一階段包括確定挖掘任務(wù)/目的、選擇挖掘方法、實(shí)施數(shù)據(jù)挖掘；5、模式解釋/評(píng)價(jià)：數(shù)據(jù)挖掘階段發(fā)現(xiàn) 出來的模式，經(jīng)過用戶或機(jī)器的評(píng)價(jià)，可能存在冗余或無關(guān)的模式，需要剔除；也 有可能模式不滿足用戶的要求，需要退回到整個(gè)發(fā)現(xiàn)階段之前，重新進(jìn)行KDD過程。2、闡述數(shù)據(jù)挖掘產(chǎn)生的背景和意義。?數(shù)據(jù)挖掘產(chǎn)生的背景：隨著信息科技的進(jìn)步以及電子化時(shí)代的到來，人們以更 快捷、更容易、更廉價(jià)的方式獲取和存儲(chǔ)數(shù)據(jù)，使得數(shù)據(jù)及信息量以指數(shù)方式增長。 據(jù)粗略估計(jì)，一個(gè)中等規(guī)模企業(yè)每天要產(chǎn)生1

3、00MB以上的商業(yè)數(shù)據(jù)。而電信、銀行、 大型零售業(yè)每天產(chǎn)生的數(shù)據(jù)量以 TB來計(jì)算。人們搜集的數(shù)據(jù)越來越多，劇增的數(shù)據(jù) 背后隱藏著許多重要的信息，人們希望對(duì)其進(jìn)行更高層次的分析，以便更好的利用 這些數(shù)據(jù)。先前的數(shù)據(jù)庫系統(tǒng)可以高效的實(shí)現(xiàn)數(shù)據(jù)的錄入、查詢、統(tǒng)計(jì)等功能，但 無法發(fā)現(xiàn)數(shù)據(jù)中存在的關(guān)系與規(guī)則，無法根據(jù)現(xiàn)有的數(shù)據(jù)來預(yù)測未來的發(fā)展趨勢。 缺乏挖掘數(shù)據(jù)背后隱藏的知識(shí)的手段。導(dǎo)致了“數(shù)據(jù)爆炸但知識(shí)貧乏”的現(xiàn)象。于 是人們開始提出“要學(xué)會(huì)選擇、提取、拋棄信息”，并且開始考慮：如何才能不被信 息淹沒？如何從中及時(shí)發(fā)現(xiàn)有用的知識(shí)、提高信息利用率？如何從浩瀚如煙海的資 料中選擇性的搜集他們認(rèn)為有用的信息？

4、這給我們帶來了另一些頭頭疼的問題：第 一是信息過量，難以消化；第二是信息真假難以辨別；第三是信息安全難以保證； 第四是信息形式不一致，難以統(tǒng)一處理 ？面對(duì)這一挑戰(zhàn)，面對(duì)數(shù)量很大而有意義的信息很難得到的狀況面對(duì)大量繁雜而分散的數(shù)據(jù)資源，隨著計(jì)算機(jī)數(shù)據(jù)倉庫技術(shù)的不斷成熟，從數(shù)據(jù)中發(fā)現(xiàn)知識(shí)(Knowledge?Discovery?in?Databas)及其核心技術(shù)數(shù)據(jù)挖掘(Data?Mining)便應(yīng)運(yùn)而生，并得以蓬勃發(fā)展，越來越顯示出其強(qiáng)大的生命力。數(shù)據(jù)挖掘的意義：數(shù)據(jù)挖掘之所以被稱為未來信息處理的骨干技術(shù)之一，主要 在于它正以一種全新的概念改變著人類利用數(shù)據(jù)的方式。在20世紀(jì)，數(shù)據(jù)庫技術(shù)取得了重

5、大的成果并且得到了廣泛的應(yīng)用。但是，數(shù)據(jù)庫技術(shù)作為一種基本的信息儲(chǔ) 存和管理方式，仍然是以聯(lián)機(jī)事務(wù)處理為核心應(yīng)用，缺少對(duì)決策、分析、預(yù)測等高 級(jí)功能的支持機(jī)制。眾所周知，隨著硬盤存儲(chǔ)容量及的激增以及磁盤陣列的普及， 數(shù)據(jù)庫容量增長迅速，數(shù)據(jù)倉庫以及 Web等新型數(shù)據(jù)源出現(xiàn)，聯(lián)機(jī)分析處理、決策 支持以及分類、聚類等復(fù)雜應(yīng)用成為必然。面對(duì)這樣的挑戰(zhàn)，數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn) 技術(shù)應(yīng)運(yùn)而生，并顯現(xiàn)出強(qiáng)大的生命力。數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)使數(shù)據(jù)處理技術(shù)進(jìn)入 了一個(gè)更加高級(jí)的階段。它不僅能對(duì)過去的數(shù)據(jù)進(jìn)行查詢，而且能夠找出過去數(shù)據(jù) 之間的潛在聯(lián)系，進(jìn)行更高層次的分析，以便更好地作出決策、預(yù)測未來的發(fā)展趨 勢等等。通

6、過數(shù)據(jù)挖掘，有價(jià)值的知識(shí)、規(guī)則或更高層次的信息就能夠從數(shù)據(jù)庫的 相關(guān)數(shù)據(jù)集合中抽取出來，從而使大型數(shù)據(jù)庫作為一個(gè)豐富、可靠的資源為知識(shí)的 提取服務(wù)。3、給出一種關(guān)聯(lián)規(guī)則的算法描述，并舉例說明。Apriori算法描述：Apriori算法由Agrawal等人于1993年提出，是最有影響的挖 掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法，它通過使用遞推的方法生成所有頻繁項(xiàng)目集?；?本思想是將關(guān)聯(lián)規(guī)則挖掘算法的設(shè)計(jì)分解為兩步：(1)找到所有頻繁項(xiàng)集，含有？k?個(gè) 項(xiàng)的頻繁項(xiàng)集稱為？k-項(xiàng)集。Apriori使用一種稱作逐層搜索的迭代方法，k-項(xiàng)集用于 探索(k+1)項(xiàng)集。首先，出頻繁？1顧集的集合。該集合記作L1。L1

7、用于找頻繁？2-項(xiàng) 集的集合L2,而L2用于找L3,如下去，直到不能找到頻繁k-項(xiàng)集。找出每個(gè)Lk都 需要一次數(shù)據(jù)庫掃描。為提高頻繁項(xiàng)集層產(chǎn)生的效率，算法使用Apriori性質(zhì)用于壓縮搜索空間。(2)使用第一步中找到的頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則。從算法的基本思想可 知，Apriori算法的核心和關(guān)鍵在第一步。而第一步的關(guān)鍵是如何將Apriori性質(zhì)用于算法，利用Lk?-?1找Lk。這也是一個(gè)由連接和剪枝組成的兩步過程：(1)連接步： 為找Lk，通過Lk?-1與自己連接產(chǎn)生候選k-項(xiàng)集的集合。該候選項(xiàng)集的集合記作 Ch 設(shè)11和12是Lk?-?1中的項(xiàng)集。記號(hào) 叩表示li的第j項(xiàng)(例如，l1k-2表示

8、11的倒數(shù) 第3項(xiàng))。為方便計(jì)，假定事務(wù)或項(xiàng)集中的項(xiàng)按字典次序排序。執(zhí)行連接Lk?-?1?Lk?-?1其中，Lk?-?1的元素是可連接的，如果它們前(k-2)項(xiàng)相同；即Lk?-?1 的元素11和12是可連接的，如果(111?=?121)?人？(112?=?122)?人？A ?(l1?k-2?=?l2?k-2)?人?(l1?k-1?v?l2?k-1)條件(I1k-1?v?l2k-1)是簡單地保證 不產(chǎn)生重復(fù)。連接l1和l2產(chǎn)生的結(jié)果項(xiàng)集是I11?l12.?l1?k-1?l2k-1。 (2)剪枝 步：Ck是Lk的超集；即，它的成員可以是，也可以不是頻繁的，但所有的頻繁k-項(xiàng)集都包含在Ck中。掃描數(shù)

9、據(jù)庫，確定Ck中每個(gè)候選的計(jì)數(shù)，從而確定 Lk (即, 根據(jù)定義，計(jì)數(shù)值不小于最小支持度計(jì)數(shù)的所有候選是頻繁的，從而屬于Lk)。然而，Ck可能很大，這樣所涉及的計(jì)算量就很大。為壓縮Ck,可以用以下辦法使用Apriori性質(zhì)：任何非頻繁的(k-1)-項(xiàng)集都不可能是頻繁k-項(xiàng)集的子集。因此，如果一個(gè)候選 k-項(xiàng)集的(k-1)-子集不在Lk?-?1中，則該候選也不可能是頻繁的，從而可以由Ck中刪除。Apriori算法舉例：如有如下數(shù)據(jù)TIDList ofitemD ' sT10011,12,15T200I2,I4T300I2,I3T40011,12,14T500I1,I3T600I2,I3T

10、700I1,I3T80011,12,13,15T90011,12,13每一行表示一條交易，共有9行，既9筆交易，左邊表示交易ID，右邊表示商 品名稱。最小支持度是22%,那么每件商品至少要出現(xiàn)9*22%=2次才算頻繁。第一 次掃描數(shù)據(jù)庫，使得在每條交易中，按商品名稱遞增排序。第二次掃描數(shù)據(jù)，找頻 繁項(xiàng)集為1的元素有：集是2的元素，方法是兩兩任意組合，第三次掃描數(shù)據(jù)得到它們出現(xiàn)的次數(shù):項(xiàng)集支持度計(jì)數(shù)11, 12411, 13411, 14111, 15212, 13412, 14212, 15213, 14013, 15114, 150此時(shí)就有規(guī)律性了，在頻繁項(xiàng)集為 K的元素上找頻繁項(xiàng)集為K+1

11、的元素的方法 是：在頻繁項(xiàng)集為K的項(xiàng)目（每行記錄）中，假如共有 N行，兩兩組合，滿足兩兩 中前K-1個(gè)元素相同，只后一個(gè)元素要求前一條記錄的商品名稱小于后一條記錄的商 品名稱，這樣是為了避免重復(fù)組合，求它們的并集得到長度為K+1的準(zhǔn)頻繁項(xiàng)集，那么最多共有Apriori算法種可能的組合，有：12, 13, 15 12, 14, 15想想如果N很大的話，Apriori算法是一個(gè)多么龐大的數(shù)字，這時(shí)就要用到Apriori 的核心了：如果K+1個(gè)元素構(gòu)成頻繁項(xiàng)集，那么它的任意K個(gè)元素的子集也是頻繁項(xiàng)集。然后將每組K+1個(gè)元素的所有長度為K的子集，有Apriori算法中組合，在頻 繁項(xiàng)集為K的項(xiàng)集中匹配

12、，沒有找到則刪除，用第一條記錄11,12,13它的長度為2的頻繁項(xiàng)集有：Apriori算法分別是：11,12,11,13,12,13種情況幸好這三種情況在頻繁 項(xiàng)集為2的項(xiàng)集中都找到了。通過這步過濾，得到的依舊是準(zhǔn)頻繁項(xiàng)集，它們是:3的頻繁項(xiàng)集是:項(xiàng)集支持度計(jì)數(shù)11, 12, 13211, 12, 152因?yàn)?1,12,14只出現(xiàn)了 1次，小于最小支持度2,刪除。就這個(gè)例子而言，它的最大頻繁項(xiàng)集只有3,就是11,12,13和11,12,15。4、給出一種聚類算法描述，并舉例說明k-mea ns算法是一種屬于劃分方法的聚類算法，通常采用歐氏距離作為2個(gè)樣本相似程度的評(píng)價(jià)指標(biāo)，其基本思想是：隨機(jī)選

13、取數(shù)據(jù)集中的k個(gè)點(diǎn)作為初始聚類中心，根據(jù)數(shù)據(jù)集中的各個(gè)樣本到 k個(gè)中心的距離將其歸到距離最小的類中，然后 計(jì)算所有歸到各個(gè)類中的樣本的平均值，更新每個(gè)類中心，直到平方誤差準(zhǔn)則函數(shù) 穩(wěn)定在最小值。算法步驟：1為每個(gè)聚類確定一個(gè)初始聚類中心，這樣就有K?個(gè)初始聚類中心。？ ?2將樣本集中的樣本按照最小距離原則分配到最鄰近聚類？?3使用每個(gè)聚類中的樣本均值作為新的聚類中心。？4.重復(fù)步驟2.3步直到聚類中心不再變化。k-means算法舉例：數(shù)據(jù)對(duì)象集合S見下表，作為一個(gè)聚類分析的二維樣本，要 求的簇的數(shù)量k=2。oxy10220031.50450552選擇0,2 ,。2 0,0為初始的簇中心，即M/

14、O/ 0,2 ,M2=O2二0,0 對(duì)剩余的每個(gè)對(duì)象，根據(jù)其與各個(gè)簇中心的距離，將它賦給最近的簇。對(duì) 。3 :d(M!,O3 )= J(01.5 卄(20$ =2.5 d ( M 2Q3 )= J( 0-1.5 )2 +( 0一 0 )2 = 1.5顯然d M2,O3 <d Mi,O3 ，故將O3分配給C2對(duì)于。4:d (Mi,°4 ) = J(0_5 j +(2_0 ( =7294(皿2,04 )= J(0_5)2+(0_0)2 = 5因?yàn)閐M2,O4 <d MiQ ，所以將04分配給C2對(duì)于05:) = J(05$ +(22$=5 d(M2,O5)=J(0-5)2+(

15、0-2)2 =履因?yàn)閐 Mi,05 <d M2,O5 ，所以將05分配給Ci更新，得到新簇g OjOj和C2bQQl計(jì)算平方誤差準(zhǔn)則，單個(gè)方差為2總體平均方差是0 2 +臣三丘和E很25了2725牙52=225(3)計(jì)算新的簇的中心。Mi二0 5 2, 2 2 2二2.5,2重復(fù)(2)和(3),得到O分配給C; Q分配給Q, O分配給C2，O分配給Q,Q分配給C。更新，得到新簇CgO和C2=O2,O3,Oj中心為 Mi 二 2.5,2, M2 二 2.17,0。單個(gè)方差分別為匚2,2一22 "I總體平均誤差是):：(2 -2) 25 -5)“2 -2)卜12.5由上可以看出，第

16、一次迭代后，總體平均誤差值52.2525.65，顯著減小。由于在兩次迭代中，簇中心不變，所以停止迭代過程，算法停止。5、給出一種分類的算法描述，并舉例說明。決策樹算法是數(shù)據(jù)挖掘領(lǐng)域的核心分類算法之一，其中ID3算法是最為經(jīng)典的決 策樹算法。ID3算法理論清晰、使用簡單、學(xué)習(xí)能力較強(qiáng)，且構(gòu)造的決策樹平均深度 較小,分類速度較快，特別適合處理大規(guī)模的學(xué)習(xí)問題，目前已得到廣泛應(yīng)用。在ID3決策樹歸納方法中，通常是使用信息增益方法來幫助確定生成每個(gè)節(jié)點(diǎn) 時(shí)所應(yīng)采用的合適屬性。這樣就可以選擇具有最高信息增益(熵減少的程度最大) 的屬性最為當(dāng)前節(jié)點(diǎn)的測試屬性，以便對(duì)之后劃分的訓(xùn)練樣本子集進(jìn)行分類所需要 的

17、信息最小，也就是說，禾U用該屬性進(jìn)行當(dāng)前(節(jié)點(diǎn)所含)樣本集合劃分，將會(huì)使 得所產(chǎn)生的樣本子集中的“不同類別的混合程度”降為最低。因此，采用這樣一種 信息論方法將有效減少對(duì)象分來所需要的次數(shù)，從而確保所產(chǎn)生的決策樹最為簡單設(shè)E = F1 X F2 x-x Fn是n維有窮向量空間，其中Fj是有窮離散符號(hào)集，E 中的元素e = <%/, ,Vn>叫做例子,其中Vj J j = 1 ,2 ,n。設(shè)PE和NE是E的F兩個(gè)例子集,分別叫正例集和反例集。假設(shè)向量空間E中的正例集PE和反例集NE的大小分別為p和n ,ID3基于下列 兩個(gè)假設(shè)：(1)在向量空間E上的一棵正確決策樹，對(duì)任意例子的分類概

18、率同E中的 正、反例的概率一致；(2) 棵決策樹能對(duì)一例子做出正確類別判斷所需的信息量為 ：PIog2Iog2-I (p,n) = P n P n P n如果以屬性A作為決策樹的根,A具有v個(gè)值(乂，/,Vn),它將E分為v 個(gè)子集(匕，巳，,匕)，假設(shè)E中含有Pi個(gè)正例和口個(gè)反例,子集E的信息熵為 I(Pi, n ),以屬性A為根分類后的信息熵為：因此,以A為根的信息增益是 Gain (A) = I (p,n) - E(A)。ID3選擇使Gain (A) 最大(即E(A)最小)的屬性作為根結(jié)點(diǎn)。對(duì)的不同的取值對(duì)應(yīng)的E的v個(gè)子集 E遞歸調(diào)用上述過程,生成才的子結(jié)點(diǎn)，B1,B2,，R。ID3的基

19、本原理是基于兩類分類問題，但很容易擴(kuò)展到多類。設(shè)樣本集S共有C 類樣本,每類樣本數(shù)為pi ,( i = 1 ,2 ,3 ,c)。若以屬性A作為決策樹的根,A具有V個(gè)值乂，仏，,Vn ,它將E分成V個(gè)子集巳，E2,巳，假設(shè)E中含有 j類樣本的個(gè)數(shù)為Pj,j = 1,2,c那么,子集Ej的信息量是1( E)。以A為根分類的信息熵為：選擇屬性'使E( A)最小，信息增益也將增大。理想的決策樹分成3種:(1)葉節(jié)點(diǎn)數(shù)最小，(2)葉節(jié)點(diǎn)深度最?。?3)葉節(jié)點(diǎn)數(shù) 量最少且葉子結(jié)點(diǎn)深度最小。決策樹的好壞，不僅影響分類的效率，而且還影響分類 的準(zhǔn)確率。人們?yōu)榱藢で筝^優(yōu)的解，不得不尋求各種啟發(fā)式的方法。

20、有的采用基于屬性相關(guān)性的啟發(fā)式函數(shù)；有的對(duì)生成的決策樹進(jìn)行剪枝處理；有的則擴(kuò)充決策樹，形 成決策圖。如今普遍采用的是優(yōu)化算法,基本思想：首先用ID3選擇屬性F1,建立樹T1,左、 右子樹的屬性分別為F2,F3,再以F2,F3為根，重建樹T2, T3;較T1,T2,T3的結(jié)點(diǎn)個(gè) 數(shù)，選擇結(jié)點(diǎn)最少的樹。對(duì)于選擇定樹的兒子結(jié)點(diǎn)采用同樣的方法遞歸建樹。盡管作 者用一個(gè)實(shí)驗(yàn)證明能建立理想的決策樹，但算法有較大的弱點(diǎn)：時(shí)間開銷太大，因?yàn)?每選擇一個(gè)新的屬性，算法都需要建立3棵決策樹,從中選優(yōu)。ID3算法舉例：性格父母教育程度性別類別內(nèi)向良女生好：外向良男生好外向中女生差內(nèi)向差女生差外向中男生好內(nèi)向良男生好

21、外向差女生好外向差男生差外向良女生好內(nèi)向中女生差內(nèi)向中男生差內(nèi)向差男生差此例假定要按某校學(xué)生學(xué)習(xí)成績好壞這個(gè)概念對(duì)一個(gè)集合進(jìn)行分類，該集合中用來描述學(xué)生的屬性有性格、父母教育程度和性別。性格的取值為外向、內(nèi)向。父 母教育程度取值為良好、中等和差。性別的取值為男生、女生。例子集中共有12名學(xué)生，如表所示。在類別一欄，將正例即“學(xué)習(xí)成績好”的學(xué)生用“好”標(biāo)出，反例即“學(xué)生成績差”的學(xué)生用“差”標(biāo)出這些例子一開始全部包含在根結(jié)點(diǎn)中，為了找出當(dāng)前的最佳劃分屬性，先須根據(jù) 信息論中的公式計(jì)算訓(xùn)練實(shí)例集 Es的熵值。貝肪艮節(jié)點(diǎn)的熵值為：Entropy (Es)=612log 26log 212下面分別計(jì)算

22、例子集中各個(gè)屬性的信息贏取值。對(duì)屬性“性格”來說 ，分外向和 內(nèi)向兩個(gè)分支。當(dāng)v = “外向”時(shí)，有4名“外向”小學(xué)生是“學(xué)習(xí)成績好”的，有2 名“外向”小學(xué)生是“學(xué)習(xí)成績差”的。因此，當(dāng)v = “內(nèi)向”時(shí)，有2名“內(nèi)向”小學(xué)生是“學(xué)習(xí)成績好”的，有4名“內(nèi)向” 小學(xué)生是“學(xué)習(xí)成績差”的。因此所以根據(jù)“性格”屬性來進(jìn)行例子集分類的信息贏取值為1 11-（*0.9183+ *0.9183）=0.0817Gai n（ Es）=E ntropy（Es）-E ntropy（Esv）=22同理,對(duì)“父母教育程度”來說：Gain（Es,父母教育程度）=0.4591 ;對(duì)“性別”來說:Gain（ Es,性別）=0。因?yàn)镚ain （ Es，性別） Gain （ Es , 性格） Gain （