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

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

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

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

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

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

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

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

8、 1中的項集。記號lij表示li的第j項（例如，l1k-2表示l1的倒數(shù)第3項）。為方便計，假定事務或項集中的項按字典次序排序。執(zhí)行連接Lk -  1 Lk -  1；其中，Lk - 1的元素是可連接的，如果它們前(k-2)項相同；即Lk - 1的元素l1和l2是可連接的，如果(l11 = l21)  (l12 = l22)  .  (l1 k-2 =

9、60;l2 k-2)  (l1 k-1 < l2 k-1)。條件(l1k-1 < l2k-1)是簡單地保證不產(chǎn)生重復。連接l1和l2產(chǎn)生的結(jié)果項集是l11 l12. l1 k-1 l2k-1。（2）剪枝步：Ck是Lk的超集；即，它的成員可以是，也可以不是頻繁的，但所有的頻繁k-項集都包含在Ck中。掃描數(shù)據(jù)庫，確定Ck中每個候選的計數(shù)，從而確定Lk（即，根據(jù)定義，計數(shù)值不小于最小支持度計數(shù)的所有候選是頻繁的，從而屬于Lk）。然而，Ck可能很大，這樣所涉及的

10、計算量就很大。為壓縮Ck，可以用以下辦法使用Apriori性質(zhì)：任何非頻繁的(k-1)-項集都不可能是頻繁k-項集的子集。因此，如果一個候選k-項集的(k-1)-子集不在Lk - 1中，則該候選也不可能是頻繁的，從而可以由Ck中刪除。Apriori算法舉例：如有如下數(shù)據(jù)TIDList of item_IDsT100I1,I2,I5T200I2,I4T300I2,I3T400I1,I2,I4T500I1,I3T600I2,I3T700I1,I3T800I1,I2,I3,I5T900I1,I2,I3每一行表示一條交易，共有9行，既9筆交易，左邊表示交易ID，右邊表示商品名稱。最

11、小支持度是22%，那么每件商品至少要出現(xiàn)9*22%=2次才算頻繁。第一次掃描數(shù)據(jù)庫，使得在每條交易中，按商品名稱遞增排序。第二次掃描數(shù)據(jù)，找頻繁項集為1的元素有：項集支持度計數(shù)I16I27I36I42I52左邊表示商品名稱，右邊表示出現(xiàn)的次數(shù)，都大于閾值2。在此基礎上找頻繁項集是2的元素，方法是兩兩任意組合，第三次掃描數(shù)據(jù)得到它們出現(xiàn)的次數(shù)： 項集支持度計數(shù)I1，I24I1，I34I1，I41I1，I52I2，I34I2，I42I2，I52I3，I40I3，I51I4，I50此時就有規(guī)律性了，在頻繁項集為K的元素上找頻繁項集為K+1的元素的方法是：在頻繁項集為K的項目（每行記錄）中，假如共有N

12、行，兩兩組合，滿足兩兩中前K-1個元素相同，只后一個元素要求前一條記錄的商品名稱小于后一條記錄的商品名稱，這樣是為了避免重復組合，求它們的并集得到長度為K+1的準頻繁項集，那么最多共有Apriori算法種可能的組合，有： 項集I1，I2，I3I1，I2，I5I1，I2，I4I1，I3，I5I2，I3，I4I2，I3，I5I2，I4，I5想想如果N很大的話，Apriori算法是一個多么龐大的數(shù)字，這時就要用到Apriori的核心了：如果K+1個元素構成頻繁項集，那么它的任意K個元素的子集也是頻繁項集。然后將每組K+1個元素的所有長度為K的子集，有Apriori算法中組合，在頻繁項集為K的項集中匹

13、配，沒有找到則刪除，用第一條記錄I1,I2,I3它的長度為2的頻繁項集有：Apriori算法分別是：I1,I2,I1,I3,I2,I3種情況,幸好這三種情況在頻繁項集為2的項集中都找到了。通過這步過濾，得到的依舊是準頻繁項集，它們是：項集I1，I2，I3I1，I2，I5I1，I2，I4此時第四次掃描數(shù)據(jù)庫，得到真正長度為3的頻繁項集是：項集支持度計數(shù)I1，I2，I32I1，I2，I52因為I1,I2,I4只出現(xiàn)了1次，小于最小支持度2，刪除。就這個例子而言，它的最大頻繁項集只有3，就是I1,I2,I3和I1,I2,I5。4、 給出一種聚類算法描述，并舉例說明。k-means 算法是一種屬于劃分

14、方法的聚類算法，通常采用歐氏距離作為 2 個樣本相似程度的評價指標，其基本思想是：隨機選取數(shù)據(jù)集中的 k 個點作為初始聚類中心，根據(jù)數(shù)據(jù)集中的各個樣本到k 個中心的距離將其歸到距離最小的類中，然后計算所有歸到各個類中的樣本的平均值，更新每個類中心，直到平方誤差準則函數(shù)穩(wěn)定在最小值。算法步驟：1.為每個聚類確定一個初始聚類中心，這樣就有K 個初始聚類中心。  2.將樣本集中的樣本按照最小距離原則分配到最鄰近聚類   3.使用每個聚類中的樣本均值作為新的聚類中心。 4.重復步驟2.3步直到聚類中心不再變化。k-means算法舉例

15、：數(shù)據(jù)對象集合S見下表，作為一個聚類分析的二維樣本，要求的簇的數(shù)量k=2。oxy10220031.50450552(1)選擇 ， 為初始的簇中心，即 ，(2)對剩余的每個對象，根據(jù)其與各個簇中心的距離，將它賦給最近的簇。 對 ：顯然 ，故將 分配給對于 ： 因為 ，所以將 分配給對于 ：因為 ，所以將 分配給 更新，得到新簇 和 計算平方誤差準則，單個方差為 總體平均方差是：（3）計算新的簇的中心。 重復（2）和（3），得到O1分配給C1；O2分配給C2，O3分配給C2 ，O4分配給C2，O5分配給C1。更新，得到新簇 和 。 中心為 ， 。 單個方差分別為總體平均誤差是：由上可以看出，第一次

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

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

18、的分類概率同E 中的正、反例的概率一致;(2)一棵決策樹能對一例子做出正確類別判斷所需的信息量為:I（p,n）=如果以屬性A作為決策樹的根, A具有v個值(,) ,它將E分為v個子集(, ) ,假設中含有Pi個正例和個反例,子集的信息熵為I(Pi,) ,以屬性A為根分類后的信息熵為：因此,以A 為根的信息增益是Gain (A) = I (p,n) - E(A) 。ID3 選擇使Gain (A) 最大(即E(A) 最小)的屬性作為根結(jié)點。對的不同的取值對應的E 的v個子集遞歸調(diào)用上述過程,生成的子結(jié)點,， 。ID3 的基本原理是基于兩類分類問題,但很容易擴展到多類。設樣本集S 共有C類樣本,每類

19、樣本數(shù)為pi ,( i = 1 ,2 ,3 , c) 。若以屬性A 作為決策樹的根, A 具有V 個值, ,它將E 分成V 個子集, ,假設中含有j類樣本的個數(shù)為,j = 1,2,c那么,子集的信息量是I()。以A 為根分類的信息熵為:選擇屬性使E( A) 最小,信息增益也將增大。理想的決策樹分成3種: (1)葉節(jié)點數(shù)最小, (2)葉節(jié)點深度最小; (3)葉節(jié)點數(shù)量最少且葉子結(jié)點深度最小。決策樹的好壞,不僅影響分類的效率,而且還影響分類的準確率。人們?yōu)榱藢で筝^優(yōu)的解,不得不尋求各種啟發(fā)式的方法。有的采用基于屬性相關性的啟發(fā)式函數(shù);有的對生成的決策樹進行剪枝處理;有的則擴充決策樹,形成決策圖。如

20、今普遍采用的是優(yōu)化算法,基本思想:首先用ID3選擇屬性F1,建立樹T1,左、右子樹的屬性分別為F2,F3,再以F2,F3為根,重建樹T2，T3;較T1,T2,T3的結(jié)點個數(shù),選擇結(jié)點最少的樹。對于選擇定樹的兒子結(jié)點采用同樣的方法遞歸建樹。盡管作者用一個實驗證明能建立理想的決策樹,但算法有較大的弱點:時間開銷太大,因為每選擇一個新的屬性,算法都需要建立3 棵決策樹,從中選優(yōu)。ID3算法舉例：性格父母教育程度性別類別內(nèi)向外向外向內(nèi)向外向內(nèi)向外向外向外向內(nèi)向內(nèi)向內(nèi)向良良中差中良差差良中中差女生男生女生女生男生男生女生男生女生女生男生男生好好差差好好好差好差差差此例假定要按某校學生學習成績好壞這個概念

21、對一個集合進行分類,該集合中用來描述學生的屬性有性格、父母教育程度和性別。性格的取值為外向、內(nèi)向。父母教育程度取值為良好、中等和差。性別的取值為男生、女生。例子集中共有12 名學生,如表所示。在類別一欄,將正例即“學習成績好”的學生用“好”標出,反例即“學生成績差”的學生用“差”標出。這些例子一開始全部包含在根結(jié)點中,為了找出當前的最佳劃分屬性,先須根據(jù)信息論中的公式計算訓練實例集Es的熵值。則根節(jié)點的熵值為: = 1下面分別計算例子集中各個屬性的信息贏取值。對屬性“性格”來說,分外向和內(nèi)向兩個分支。當v =“外向”時,有4 名“外向”小學生是“學習成績好”的,有2 名“外向”小學生是“學習成績差”的。因此, 當v =“內(nèi)向”時,有2 名“內(nèi)向”小學生是“學習成績好”的,有4 名“內(nèi)向”小學生是“學習成績差”的。因此,所以根據(jù)“性格”屬性來進行例子集分類的信息贏取值為:Gain(Es)=Entropy(Es)-Entropy(Esv)=同理,對“父母教育程度”來說:Gain(Es, 父母教育程度)=0.4591 ;對“性別”來說:Gain( Es,性別) =