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

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

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

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

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

5、了重大的成果并且得到了廣泛的應(yīng)用。但是，數(shù)據(jù)庫(kù)技術(shù)作為一種基本的信息儲(chǔ)存和管理方式，仍然是以聯(lián)機(jī)事務(wù)處理為核心應(yīng)用，缺少對(duì)決策、分析、預(yù)測(cè)等高級(jí)功能的支持機(jī)制。眾所周知，隨著硬盤存儲(chǔ)容量及的激增以及磁盤陣列的普及，數(shù)據(jù)庫(kù)容量增長(zhǎng)迅速，數(shù)據(jù)倉(cāng)庫(kù)以及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ì)過(guò)去的數(shù)據(jù)進(jìn)行查詢，而且能夠找出過(guò)去數(shù)據(jù)之間的潛在聯(lián)系，進(jìn)行更高層次的分析，以便更好地作出決策、預(yù)測(cè)未來(lái)的發(fā)展趨勢(shì)等等。通過(guò)數(shù)據(jù)挖掘，有

6、價(jià)值的知識(shí)、規(guī)則或更高層次的信息就能夠從數(shù)據(jù)庫(kù)的相關(guān)數(shù)據(jù)集合中抽取出來(lái)，從而使大型數(shù)據(jù)庫(kù)作為一個(gè)豐富、可靠的資源為知識(shí)的提取服務(wù)。3、 給出一種關(guān)聯(lián)規(guī)則的算法描述，并舉例說(shuō)明。Apriori算法描述：Apriori算法由Agrawal等人于1993年提出，是最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法，它通過(guò)使用遞推的方法生成所有頻繁項(xiàng)目集?；舅枷胧菍㈥P(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-項(xiàng)集的集合。

7、該集合記作L1。L1用于找頻繁 2-項(xiàng)集的集合L2，而L2用于找L3，如下去，直到不能找到頻繁k-項(xiàng)集。找出每個(gè)Lk都需要一次數(shù)據(jù)庫(kù)掃描。為提高頻繁項(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è)由連接和剪枝組成的兩步過(guò)程：（1）連接步：為找Lk，通過(guò)Lk -1與自己連接產(chǎn)生候選k-項(xiàng)集的集合。該候選項(xiàng)集的集合記作Ck。設(shè)l1和l2是Lk -

8、 1中的項(xiàng)集。記號(hào)lij表示li的第j項(xiàng)（例如，l1k-2表示l1的倒數(shù)第3項(xiàng)）。為方便計(jì)，假定事務(wù)或項(xiàng)集中的項(xiàng)按字典次序排序。執(zhí)行連接Lk -  1 Lk -  1；其中，Lk - 1的元素是可連接的，如果它們前(k-2)項(xiàng)相同；即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)是簡(jiǎn)單地保證不產(chǎn)生重復(fù)。連接l1和l2產(chǎn)生的結(jié)果項(xiàng)集是l11 l12. l1 k-1 l2k-1。（2）剪枝步：Ck是Lk的超集；即，它的成員可以是，也可以不是頻繁的，但所有的頻繁k-項(xiàng)集都包含在Ck中。掃描數(shù)據(jù)庫(kù)，確定Ck中每個(gè)候選的計(jì)數(shù)，從而確定Lk（即，根據(jù)定義，計(jì)數(shù)值不小于最小支持度計(jì)數(shù)的所有候選是頻繁的，從而屬于Lk）。然而，Ck可能很大，這樣所涉及的

10、計(jì)算量就很大。為壓縮Ck，可以用以下辦法使用Apriori性質(zhì)：任何非頻繁的(k-1)-項(xiàng)集都不可能是頻繁k-項(xiàng)集的子集。因此，如果一個(gè)候選k-項(xiàng)集的(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ù)庫(kù)，使得在每條交易中，按商品名稱遞增排序。第二次掃描數(shù)據(jù)，找頻繁項(xiàng)集為1的元素有：項(xiàng)集支持度計(jì)數(shù)I16I27I36I42I52左邊表示商品名稱，右邊表示出現(xiàn)的次數(shù)，都大于閾值2。在此基礎(chǔ)上找頻繁項(xiàng)集是2的元素，方法是兩兩任意組合，第三次掃描數(shù)據(jù)得到它們出現(xiàn)的次數(shù)： 項(xiàng)集支持度計(jì)數(shù)I1，I24I1，I34I1，I41I1，I52I2，I34I2，I42I2，I52I3，I40I3，I51I4，I50此時(shí)就有規(guī)律性了，在頻繁項(xiàng)集為K的元素上找頻繁項(xiàng)集為K+1的元素的方法是：在頻繁項(xiàng)集為K的項(xiàng)目（每行記錄）中，假如共有N

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

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

14、方法的聚類算法，通常采用歐氏距離作為 2 個(gè)樣本相似程度的評(píng)價(jià)指標(biāo)，其基本思想是：隨機(jī)選取數(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算法舉例

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

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

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

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

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

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

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