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

1、給出KDD的定義和處理過程

KDD的定義是：從大量數(shù)據(jù)中提取出可信的、新穎的、有用的且可以被人理

解的模式的高級處理過程。因此，KDD是一個高級的處理過程，它從數(shù)據(jù)集中識

別出以模式形式表示的知識。這里的“模式”可以看成知識的雛形，經(jīng)過驗證、

完善后形成知識："高級的處理過程”是指一個多步驟的處理過程，多步驟之間相

互影響反復調(diào)整，形成一種螺旋式上升的過程。

KDD的全過程有五個步驟：1、數(shù)據(jù)選擇：確定發(fā)現(xiàn)任務(wù)的操作對象，即目

標數(shù)據(jù)，它是根據(jù)用戶的需要從原始數(shù)據(jù)庫中抽取的一組數(shù)據(jù)；2、數(shù)據(jù)預處理：

一般可能包括消除噪聲、推到技術(shù)卻只數(shù)據(jù)、消除重復記錄、完成數(shù)據(jù)類型轉(zhuǎn)換

等；3、數(shù)據(jù)轉(zhuǎn)換：其主要目的是消減數(shù)據(jù)維數(shù)或降維，即從初始特征中找出真

正有用的特征以減少數(shù)據(jù)開采時要考慮的特征或變量個數(shù)；4、數(shù)據(jù)挖掘：這一

階段包括確定挖掘任務(wù)/目的、選擇挖掘方法、實施數(shù)據(jù)挖掘；5、模式解釋/評

價：數(shù)據(jù)挖掘階段發(fā)現(xiàn)出來的模式，經(jīng)過用戶或機器的評價，可能存在冗余或無

關(guān)的模式，需要剔除；也有可能模式不滿足用戶的要求，需要退回到整個發(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ù)。

而電信、銀行、大型零售業(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ān)系與規(guī)則，無法根據(jù)現(xiàn)有的數(shù)據(jù)

來預測未來的發(fā)展趨勢。缺乏挖掘數(shù)據(jù)背后隱藏的知識的手段。導致了“數(shù)據(jù)爆

炸但知識貧乏”的現(xiàn)象。于是人們開始提出“要學會選擇、提取、拋棄信息”，

并且開始考慮：如何才能不被信息淹沒？如何從中及時發(fā)現(xiàn)有用的知識、提高信

息利用率？如何從浩瀚如煙海的資料中選擇性的搜集他們認為有用的信息？這

給我們帶來了另一些頭頭疼的問題：第一是信息過量，難以消化；第二是信息真

假難以辨別；第三是信息安全難以保證；第四是信息形式不一致，難以統(tǒng)一處理?

面對這一挑戰(zhàn)，面對數(shù)量很大而有意義的信息很難得到的狀況面對大量繁雜

而分散的數(shù)據(jù)資源，隨著計算機數(shù)據(jù)倉庫技術(shù)的不斷成熟，從數(shù)據(jù)中發(fā)現(xiàn)知識

(Knowledge?Discovery?in?Database)及其核心技術(shù)--數(shù)據(jù)挖掘(Data?Mining)

便應運而生，并得以蓬勃發(fā)展，越來越顯示出其強大的生命力。

數(shù)據(jù)挖掘的意義：數(shù)據(jù)挖掘之所以被稱為未來信息處理的骨干技術(shù)之一，主

要在于它正以一種全新的概念改變著人類利用數(shù)據(jù)的方式。在20世紀，數(shù)據(jù)庫

技術(shù)取得了重大的成果并且得到了廣泛的應用。但是，數(shù)據(jù)庫技術(shù)作為一種基本

的信息儲存和管理方式,仍然是以聯(lián)機事務(wù)處理為核心應用，缺少對決策、分析、

預測等高級功能的支持機制。眾所周知，隨著硬盤存儲容量及的激增以及磁盤陣

列的普及，數(shù)據(jù)庫容量增長迅速，數(shù)據(jù)倉庫以及Web等新型數(shù)據(jù)源出現(xiàn)，聯(lián)機

分析處理、決策支持以及分類、聚類等復雜應用成為必然。面對這樣的挑戰(zhàn)，數(shù)

據(jù)挖掘和知識發(fā)現(xiàn)技術(shù)應運而生，并顯現(xiàn)出強大的生命力。數(shù)據(jù)挖掘和知識發(fā)現(xiàn)

使數(shù)據(jù)處理技術(shù)進入了一個更加高級的階段。它不僅能對過去的數(shù)據(jù)進行查詢，

而且能夠找出過去數(shù)據(jù)之間的潛在聯(lián)系，進行更高層次的分析，以便更好地作出

決策、預測未來的發(fā)展趨勢等等。通過數(shù)據(jù)挖掘，有價值的知識、規(guī)則或更高層

次的信息就能夠從數(shù)據(jù)庫的相關(guān)數(shù)據(jù)集合中抽取出來，從而使大型數(shù)據(jù)庫作為一

個豐富、可靠的資源為知識的提取服務(wù)。

3、給出一種關(guān)聯(lián)規(guī)則的算法描述，并舉例說明。

Apriori算法描述：Apriori算法由Agrawal等人于1993年提出,是最有影響

的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法，它通過使用遞推的方法生成所有頻繁項目

集?；舅枷胧菍㈥P(guān)聯(lián)規(guī)則挖掘算法的設(shè)計分解為兩步：⑴找到所有頻繁項集，

含有?k?個項的頻繁項集稱為?k-項集。Apriori使用一種稱作逐層搜索的迭代方法,

k-項集用于探索(k+1)-項集。首先，出頻繁?1-項集的集合。該集合記作LI。L1用

于找頻繁?2-項集的集合L2,而L2用于找L3,如下去，直到不能找到頻繁k-項集。

找出每個Lk都需要一次數(shù)據(jù)庫掃描。為提高頻繁項集層產(chǎn)生的效率，算法使用

Apriori性質(zhì)用于壓縮搜索空間。⑵使用第一步中找到的頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則。

從算法的基本思想可知，Apriori算法的核心和關(guān)鍵在第一步。而第一步的關(guān)鍵是

如何將Apriori性質(zhì)用于算法，利用Lk?-?1找Lk。這也是一個由連接和剪枝組成

的兩步過程：(1)連接步：為找Lk,通過Lk?-1與自己連接產(chǎn)生候選k-項集的集

合。該候選項集的集合記作Cko設(shè)II和12是Lk?-?1中的項集。記號li[j]表示li

的第上項(例如，表示II的倒數(shù)第3項)。為方便計，假定事務(wù)或項集中的

項按字典次序排序。執(zhí)行連接Lk?-??l?Lk?-??l；其中，Lk?-?1的元素是可連接的，

如果它們前(k-2)項相同；即Lk?-?1的元素II和12是可連接的，如果(11[1]?=?12冏?

A?(ll[2]?=?l2[2])?A?...?A?(ll?[k-2]?=?l2?[k-2])?A?(ll?[k-l]?<?l2?[k-l])o條件

12k1])是簡單地保證不產(chǎn)生重復。連接II和12產(chǎn)生的結(jié)果項集是

Il[l]?ll[2]...?ll?[k-l]?l2[k-l]o(2)剪枝步：Ck是Lk的超集；即，它的成員可以

是，也可以不是頻繁的，但所有的頻繁k-項集都包含在Ck中。掃描數(shù)據(jù)庫，確

定Ck中每個候選的計數(shù)，從而確定Lk(即，根據(jù)定義，計數(shù)值不小于最小支持

度計數(shù)的所有候選是頻繁的，從而屬于Lk)。然而，Ck可能很大，這樣所涉及的

計算量就很大。為壓縮Ck,可以用以下辦法使用Apriori性質(zhì)：任何非頻繁的(k-1)-

項集都不可能是頻繁k-項集的子集。因此，如果一個候選k-項集的(k-l)-子集不

在Lk?-?1中，則該候選也不可能是頻繁的，從而可以由Ck中刪除。

Apriori算法舉例：如有如下數(shù)據(jù)

TIDListof

item_ID's

T10011,12,15

T20012,14

T30012,13

T40011,12,14

T50011,13

T60012,13

T70011,13

T80011,12,13,15

T90011,12,13

每一行表示一條交易，共有9行，既9筆交易，左邊表示交易ID,右邊表

示商品名稱。最小支持度是22%,那么每件商品至少要出現(xiàn)9*22%=2次才算頻

繁。第一次掃描數(shù)據(jù)庫，使得在每條交易中，按商品名稱遞增排序。第二次掃描

此時就有規(guī)律性了，在頻繁項集為K的元素上找頻繁項集為K+1的元素的方

法是：在頻繁項集為K的項目（每行記錄）中，假如共有N行，兩兩組合，滿

足兩兩中前K-1個元素相同，只后一個元素要求前一條記錄的商品名稱小于后一

條記錄的商品名稱，這樣是為了避免重復組合，求它們的并集得到長度為K+1

的準頻繁項集，那么最多共有Apriori算法種可能的組合，有：

項集

想想如果N很大的話，Apriori算法是一個多么龐大的數(shù)字，這時就要用到

Apriori的核心了：如果K+1個元素構(gòu)成頻繁項集，那么它的任意K個元素的子集

也是頻繁項集。然后將每組K+1個元素的所有長度為K的子集，有Apriori算法

中組合，在頻繁項集為K的項集中匹配，沒有找到則刪除，用第一條記錄｛11,12,13｝

它的長度為2的頻繁項集有：Apriori算法分別是：｛11,0,｛II,13｝,｛12,13｝種情況，幸好

這三種情況在頻繁項集為2的項集中都找到了。通過這步過濾，得到的依舊是準

因為｛11,12,14｝只出現(xiàn)了1次，小于最小支持度2,刪除。就這個例子而言,

它的最大頻繁項集只有3,就是｛II,12,13｝和｛II,12,15｝。

4、給出一種聚類算法描述，并舉例說明。

k-means算法是一種屬于劃分方法的聚類算法，通常采用歐氏距離作為2

個樣本相似程度的評價指標，其基本思想是：隨機選取數(shù)據(jù)集中的k個點作為

初始聚類中心，根據(jù)數(shù)據(jù)集中的各個樣本到k個中心的距離將其歸到距離最小

的類中，然后計算所有歸到各個類中的樣本的平均值，更新每個類中心，直到平

方誤差準則函數(shù)穩(wěn)定在最小值。

算法步驟：1.為每個聚類確定一個初始聚類中心，這樣就有K?個初始聚類中

心。？?2.將樣本集中的樣本按照最小距離原則分配到最鄰近聚類???3.使用每個聚

類中的樣本均值作為新的聚類中心。？4.重復步驟2.3步直到聚類中心不再變化。

k-means算法舉例：數(shù)據(jù)對象集合S見下表，作為一個聚類分析的二維樣本,

要求的簇的數(shù)量k=2o

OXy

102

200

31.50

45（）

552

⑴選擇q（o,2）,。2（0,0）為初始的簇中心，即M=Q=（O,2），%=Q=（o,o）

（2）對剩余的每個對象，根據(jù)其與各個簇中心的距離，將它賦給最近的簇。

對R：d（M，Q）=J（0-L5）2+（2-Op=2.5”（此。3）=［（0-1.5）2+（0-=L5

顯然d（%，q）"（M，q）,故將。3分配給G

對于。4：J（）=^/（0-5）2+（2-0）2=729^（^2，）=7（0_5）2+（0-0）2=5

因為4Mz,QjwaMOj，所以將。4分配給c2_______________

對于Q：d（M，Q）=，（。-5）2+（2-2）2=54（也，。5）=10-5）2+（0-2）2=揚

因為d（M，q）wd（"2，Q）,所以將。5分配給G

更新，得到新簇G=｛q,Q｝和。2=｛。2，。3，。4｝

計算平方誤差準則，單個方差為

2

（3）計算新的簇的中心。M,=（（0+5）/2,（2+2）/2）=（2.5,2）

重復（2）和（3）,得到。分配給G；0?分配給C2,。3分配給C2,0“分配給

C2,分配給3。更新，得到新簇。|=｛牝。,｝和。2=｛02，°3，04｝。

中心為M=（252）,M2=（2.17,0）0

單個方差分別為

總鈿刖誤續(xù)國（2一2）［+［（2.5—5『+（2一2月=12.5

由上可以看出，第一次迭代后，總體平均誤差值52.25~25.65,顯著減小。

由于在兩次迭代中，簇中心不變，所以停止迭代過程，算法停止。

5、給出一種分類的算法描述，并舉例說明。

決策樹算法是數(shù)據(jù)挖掘領(lǐng)域的核心分類算法之一,其中ID3算法是最為經(jīng)典

的決策樹算法。ID3算法理論清晰、使用簡單、學習能力較強，且構(gòu)造的決策樹

平均深度較小,分類速度較快,特別適合處理大規(guī)模的學習問題，目前已得到廣泛

應用。

在ID3決策樹歸納方法中，通常是使用信息增益方法來幫助確定生成每個節(jié)

點時所應采用的合適屬性。這樣就可以選擇具有最高信息增益（端減少的程度最

大）的屬性最為當前節(jié)點的測試屬性，以便對之后劃分的訓練樣本子集進行分類

所需要的信息最小，也就是說，利用該屬性進行當前（節(jié)點所含）樣本集合劃分，

將會使得所產(chǎn)生的樣本子集中的“不同類別的混合程度”降為最低。因此，采用

這樣一種信息論方法將有效減少對象分來所需要的次數(shù)，從而確保所產(chǎn)生的決策

樹最為簡單。

F

?E=F1XF2X…XFn是n維有窮向量空間，其中,是有窮離散符號集,

,―一VVV,V.p

E中的兀素e=<1,2,…，">叫做例子,其中JG,j=l,2,…，n。設(shè)

PE和NE是E的F兩個例子集，分別叫正例集和反例集。

假設(shè)向量空間E中的正例集PE和反例集NE的大小分別為p和n,ID3基于

下列兩個假設(shè)：（1）在向量空間E上的一棵正確決策樹，對任意例子的分類概率

同E中的正、反例的概率一致；（2）一棵決策樹能對一例子做出正確類別判斷所

需的信息量為：

log2-^--log2—

I（p,n）=〃+〃P+〃P+n

如果以屬性A作為決策樹的根，A具有v個值（匕，…，匕），它將E分為

v個子集（耳，紇），假設(shè)中含有Pi個正例和4個反例,子集耳的信息

焙為I（Pi,〃，），以屬性A為根分類后的信息端為：

因此，以A為根的信息增益是Gain(A)=I(p,n)-E(A)?ID3選擇使

Gain(A)最大(即E(A)最小)的屬性4作為根結(jié)點。對4的不同的取值對應的

E的v個子集4遞歸調(diào)用上述過程，生成4的子結(jié)點，4，員，…，必。

ID3的基本原理是基于兩類分類問題，但很容易擴展到多類。設(shè)樣本集S共

有C類樣本，每類樣本數(shù)為pi,(i=1,2,3,…c)。若以屬性A作為決策

樹的根，A具有V個值匕，…，匕，它將E分成V個子集［&,

假設(shè)片中含有j類樣本的個數(shù)為P",j=1,2,…,c那么，子集號的信息量是

E

K*)o

以A為根分類的信息蠟為：

選擇屬性4使￡(A)最小,信息增益也將增大。

理想的決策樹分成3種：(1)葉節(jié)點數(shù)最小，(2)葉節(jié)點深度最?。?3)葉節(jié)

點數(shù)量最少且葉子結(jié)點深度最小。決策樹的好壞，不僅影響分類的效率,而且還影

響分類的準確率。人們?yōu)榱藢で筝^優(yōu)的解，不得不尋求各種啟發(fā)式的方法。有的

采用基于屬性相關(guān)性的啟發(fā)式函數(shù);有的對生成的決策樹進行剪枝處理;有的則

擴充決策樹,形成決策圖。

如今普遍采用的是優(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)向差男生差

此例假定要按某校學生學習成績好壞這個概念對一個集合進行分類,該集合

中用來描述學生的屬性有性格、父母教育程度和性別。性格的取值為外向、內(nèi)向。

父母教育程度取值為良好、中等和差。性別的取值為男生、女生。例子集中共有

12名學生，如表所示。在類別一欄，將正例即“學習成績好”的學生用“好”標

出，反例即“學生成績差”的學生用"差”標出。

這些例子一開始全部包含在根結(jié)點中，為了找出當前的最佳劃分屬性,先須

根據(jù)信息論中的公式計算訓練實例集Es的燧值。則根節(jié)點的蠟值為：

Entropy{Es)=-/log2—^―-提log2—^―

126+6126+6=1

下面分別計算例子集中各個屬性的信息贏取值。對屬性“性格”來說，分外

向和內(nèi)向兩個分支。當丫="外向”時，有4名“外向”小學生是“學習成績好”

的，有2名“外向”小學生是“學習成績差”的。因此，

當v="內(nèi)向”時，有2名“內(nèi)向”小學生是“學習成績好”的，有4名“內(nèi)

向”小學生是“學習成績差”的。因此，

所以根據(jù)“性格”屬性來進行例子集分類的信息贏取值為：

1-(-*0.9183+4*0.9183)=0.0817

Gain(Es)=Entropy(Es)-Entropy(Esv)=22

同理，對“父母教育程度”來說:Gain(Es,父母教育程度)=0.4591;

對“性別”來說:Gain(Es,性別)=0。

因為Gain（Es，性別）＜Gain（Es,性格）＜Gain（Es,父母教育程

度）可以看出以“父母教育程度”這個屬性進行例子集分類的信息贏取值最大,

于是“父母教育程度”就被選為用于劃分的屬性,得到如下圖所示的決策樹。

現(xiàn)在必須根據(jù)所提供的信息進一步分析“父母教育程度”為“中”或“差”

的小學生的“學習成績好壞”，因此必須對“中”和“差”兩個分支的實例組成

的例子集（共8個例子）重復上述計算過程。這里簡化計算過程,算出:Gain（Es,

性格）=0.3113和Gain（Es,性別）=0.2045。

因為Gain（Es，性別）＜Gain（Es，性格），所以用屬性“性格”作第二

步劃分，于是得到如下圖所示的決策樹。

父母教育程度

差

一

向良

女

內(nèi)

向良

男

外