數(shù)據(jù)倉庫與數(shù)據(jù)挖掘ppt習(xí)題

數(shù)據(jù)倉庫與數(shù)據(jù)挖掘主講教師：王浩暢E-mail:wanghch_angel@SchoolofComputer&InformationTechnologyofNEPU第2章數(shù)據(jù)預(yù)處理練習(xí)1假定用于分析的數(shù)據(jù)包含屬性age.數(shù)據(jù)元組age值(以遞增序)是：13,15,16,16,19,20,20,21,22,22,25,25,25,25,30,33,33,35,35,35,35,36,40,45,46,52,70.(a)該數(shù)據(jù)的均值是什么?中位數(shù)是什么?(b)該數(shù)據(jù)的眾數(shù)是什么？討論數(shù)據(jù)的峰(c)數(shù)據(jù)的中列數(shù)是什么？解答(a)均值：中位數(shù)：有序集中間值或者中間兩個(gè)值平均。奇數(shù)個(gè)，中間值：25(b)：表示數(shù)據(jù)集中出現(xiàn)頻率最高的值兩個(gè)值出現(xiàn)了相同的最高頻率，25和35，都出現(xiàn)了4次，也就是雙峰(c)中列數(shù)：最大值和最小值的平均（13+70）/2=41.5練習(xí)2假定用于分析的數(shù)據(jù)包含屬性age.數(shù)據(jù)元組age值(以遞增序)是：13,15,16,16,19,20,20,21,22,22,25,25,25,25,30,33,33,35,35,35,35,36,40,45,46,52,70.(d)找出數(shù)據(jù)的第一個(gè)四分位數(shù)Q1和第三個(gè)四分位數(shù)Q3(e)給出數(shù)據(jù)的五數(shù)概括解答(d)第一個(gè)四分位數(shù)Q1：20第三個(gè)四分位數(shù)Q3：35中位數(shù)：有序集中間值或者中間兩個(gè)值平均。奇數(shù)個(gè)，中間值：25(e)五數(shù)概括:13,20,25,35,70練習(xí)3假定用于分析的數(shù)據(jù)包含屬性age.數(shù)據(jù)元組age值(以遞增序)是：13,15,16,16,19,20,20,21,22,22,25,25,25,25,30,33,33,35,35,35,35,36,40,45,46,52,70.(f)畫出數(shù)據(jù)的盒圖解答2035257013年齡(f)52噪聲數(shù)據(jù)(3)數(shù)據(jù)平滑的分箱方法price的排序后數(shù)據(jù)（單位：美元）：4，8，15，21，21，24，25，28，34劃分為（等深的）箱：箱1：4，8，15箱2：21，21，24箱3：25，28，34用箱平均值平滑：箱1：9，9，9箱2：22，22，22箱3：29，29，29用箱邊界平滑：箱1：4，4，15箱2：21，21，24箱3：25，25，34練習(xí)假定用于分析的數(shù)據(jù)包含屬性age.數(shù)據(jù)元組age值(以遞增序)是：13,15,16,16,19,20,20,21,22,22,25,25,25,25,30,33,33,35,35,35,35,36,40,45,46,52,70.使用分箱均值光滑對(duì)以上數(shù)據(jù)進(jìn)行光滑，箱的深度為3.解釋你的步驟解答Step1:排序數(shù)據(jù).Step2:將有序值劃分到大小為3的等頻箱中Step3:計(jì)算每個(gè)箱中數(shù)據(jù)的算術(shù)平均值.Step4:.將每個(gè)箱中的每個(gè)值用此箱的算術(shù)平均值替換

Bin1:44/3,44/3,44/3Bin2:55/3,55/3,55/3Bin3:21,21,21Bin4:24,24,24…規(guī)范化最小－最大規(guī)范化：對(duì)原始數(shù)據(jù)進(jìn)行線性變換。假定minA

和

maxA

分別為屬性A的最小和最大值。將A的值v映射到區(qū)間[new_minA,new_maxA]中的v’最小-最大規(guī)范化通過計(jì)算例：

假定屬性income的最小與最大值分別為12000美元和98000美元。我們想把income映射到區(qū)間[0.0,0.1]。根據(jù)最小最大規(guī)范化，income值73600美元將變換為：數(shù)據(jù)變換(2)z-score規(guī)范化：屬性A的值基于A的平均值和標(biāo)準(zhǔn)差規(guī)范化。最大最小值未知，或者離群點(diǎn)影響較大的時(shí)候適用例：假定屬性income的均值和標(biāo)準(zhǔn)差分別為54000美元和16000美元。使用z-score規(guī)范化，值73600美元轉(zhuǎn)換為數(shù)據(jù)變換(3)小數(shù)定標(biāo)規(guī)范化：通過移動(dòng)屬性A的小數(shù)點(diǎn)位置進(jìn)行規(guī)范化。小數(shù)點(diǎn)的移動(dòng)位數(shù)依賴于A的最大絕對(duì)值。例：假定A的取值由-986～917。A的最大絕對(duì)值為986。使用小數(shù)定標(biāo)規(guī)范化，用1000（即j=3）除每個(gè)值，這樣，－986規(guī)范化為－0.986，而917被規(guī)范化為0.917。數(shù)據(jù)變換(4)其中，j是使Max(||)<1的最小整數(shù)練習(xí)用如下兩種方法規(guī)范化如下數(shù)據(jù)組200;300;400;600;1000(a)min-max規(guī)范化令min=0，max=1(b)z-score規(guī)范化解答(a)min-max規(guī)范化令min=0，max=1(b)z-score規(guī)范化例

下面的數(shù)據(jù)是AllElectronics

通常銷售的商品的單價(jià)表（按$取整）。已對(duì)數(shù)據(jù)進(jìn)行了排序：1,1,5,5,5,5,5,5,8,8,10,10,10,10,12,12,12,12,14,14,14,15,15,15,15,15,15,18,18,18,18,18,18,18,18,20,20,20,20,20,20,20,21,21,21,21,25,25,25,25,25,25,28,28,30,30,30為進(jìn)一步壓縮數(shù)據(jù)，讓每個(gè)桶代表price的一個(gè)不同值。通過自然劃分分段將數(shù)值區(qū)域劃分為相對(duì)一致的、易于閱讀的、看上去更直觀或自然的區(qū)間。聚類分析產(chǎn)生概念分層可能會(huì)將一個(gè)工資區(qū)間劃分為：[51263.98,60872.34]通常數(shù)據(jù)分析人員希望看到劃分的形式為[50000，60000]自然劃分的3-4-5規(guī)則常被用來將數(shù)值數(shù)據(jù)劃分為相對(duì)一致，“更自然”的區(qū)間自然劃分的3-4-5規(guī)則規(guī)則的劃分步驟：如果一個(gè)區(qū)間最高有效位上包含3，6，7或9個(gè)不同的值，就將該區(qū)間劃分為3個(gè)等寬子區(qū)間；(72,3,2)如果一個(gè)區(qū)間最高有效位上包含2，4，或8個(gè)不同的值，就將該區(qū)間劃分為4個(gè)等寬子區(qū)間；如果一個(gè)區(qū)間最高有效位上包含1，5，或10個(gè)不同的值，就將該區(qū)間劃分為5個(gè)等寬子區(qū)間；將該規(guī)則遞歸的應(yīng)用于每個(gè)子區(qū)間，產(chǎn)生給定數(shù)值屬性的概念分層；對(duì)于數(shù)據(jù)集中出現(xiàn)的最大值和最小值的極端分布，為了避免上述方法出現(xiàn)的結(jié)果扭曲，可以在頂層分段時(shí)，選用一個(gè)大部分的概率空間。e.g.5%-95%3-4-5規(guī)則——例子假定AllElectronics

所有分部1999年的利潤覆蓋了一個(gè)很寬的區(qū)間，由-$351,976.00到$4,700,896.50。用戶希望自動(dòng)地產(chǎn)生利潤的概念分層。為了改進(jìn)可讀性，我們使用記號(hào)(l...r]表示區(qū)間(l,r]。例如，(-$1,000,000...$0]表示由-$1,000,000（開的）到$0（閉的）的區(qū)間。1．根據(jù)以上信息，最小和最大值分別為MIN=-$351,976.00和MAX=$4,700,896.50。對(duì)于分段的頂層或第一層，要考慮的最低（第5個(gè)百分位數(shù)）和最高（第95個(gè)百分位數(shù)）值是：LOW=-$159,876，HIGH=$1,838,761。2．給定LOW和HIGH，最高有效位在百萬美元數(shù)字位（即，msd=1,000,000）。LOW向下對(duì)百萬美元數(shù)字位取整，得到LOW’=-$1,000,000；HIGH向上對(duì)百萬美元數(shù)字位取整，得到HIGH’=+$2,000,000。3-4-5規(guī)則——例子3．由于該區(qū)間在最高有效位上跨越了三個(gè)值，即，(2,000,000–(1,000,000))/1,000,000=3，根據(jù)3-4-5規(guī)則，該區(qū)間被劃分成三個(gè)等寬的區(qū)間：(-$1,000,000...$0],($0...$1,000,000]和($1,000,000...$2,000,000]。這代表分層結(jié)構(gòu)的最頂層。4.現(xiàn)在，我們考察MIN和MAX，看它們“適合”在第一層分劃的什么地方。由于第一個(gè)區(qū)間(-$1,000,000...$0]覆蓋了MIN值（即，LOW′<MIN），我們可以調(diào)整該區(qū)間的左邊界，使區(qū)間更小一點(diǎn)。MIN的最高有效位字在十萬數(shù)字位。MIN向下對(duì)十萬數(shù)字位取整，得到MIN’=-$400,000。因此，第一個(gè)區(qū)間被重新定義為(-$400,000...$0]。由于最后一個(gè)區(qū)間($1,000,000...$2,000,000]不包含MAX值，即MAX>HIGH′，我們需要?jiǎng)?chuàng)建一個(gè)新的區(qū)間來覆蓋它。對(duì)MAX向上對(duì)最高有效位取整，新的區(qū)間為($2,000,000…$5,000,000]。因此，分層結(jié)構(gòu)的最頂層包含4個(gè)區(qū)間：(-$400,000...$0]，($0...$1,000,000]，($1,000,000...$2,000,000]和($2,000,000...$5,000,000]。3-4-5規(guī)則——例子5.遞歸地，每一個(gè)區(qū)間可以根據(jù)3-4-5規(guī)則進(jìn)一步劃分，形成分層結(jié)構(gòu)的下一個(gè)較低層：?第一個(gè)區(qū)間(-$400,000...$0]劃分成4個(gè)子區(qū)間：(-$400,000...-$300,000],(-$300,000...-$200,000],(-$200,000...-$100,000]和(-$100,000...$0]。?第二個(gè)區(qū)間($0...$1,000,000]劃分成5個(gè)子區(qū)間：($0...$200,000],($200,000...$400,000],($400,000...$600,000],($600,000...$800,000]和($800,000...$1,000,000]。?第三個(gè)區(qū)間($1,000,000...$2,000,000]劃分成5個(gè)子區(qū)間：($1,000,000...$1,200,000],($1,200,000...$1,400,000],($1,400,000...$1,600,000],($1,600,000...$1,800,000]和($1,800,000…$2,000,000]。?最后一個(gè)區(qū)間($2,000,000...$5,000,000]劃分成3個(gè)子區(qū)間:($2,000,000...$3,000,000],($3,000,000...$4,000,000]和($4,000,000...$5,000,000]。類似地，如果必要的話，3-4-5規(guī)則可以在較低的層上繼續(xù)迭代3-4-5規(guī)則——例子(-$400-$5,000)(-$400-0)(-$400--$300)(-$300--$200)(-$200--$100)(-$100-0)(0-$1,000)(0-$200)($200-$400)($400-$600)($600-$800)($800-$1,000)($2,000-$5,000)($2,000-$3,000)($3,000-$4,000)($4,000-$5,000)($1,000-$2,000)($1,000-$1,200)($1,200-$1,400)($1,400-$1,600)($1,600-$1,800)($1,800-$2,000)

msd=1,000 Low=-$1,000 High=$2,000第二步第四步第一步-$351 -$159 profit $1,838 $4,700 MinLow(i.e,5%-tile) High(i.e,95%-0tile)Maxcount(-$1,000-$2,000)(-$1,000-0)(0-$1,000)第三步($1,000-$2,000)第3章數(shù)據(jù)倉庫和數(shù)據(jù)挖掘的OLAP技術(shù)習(xí)題假定數(shù)據(jù)倉庫包含三個(gè)維：time,doctor和patient；兩個(gè)度量：count和charge；其中，charge是醫(yī)生對(duì)一位病人的一次來訪的收費(fèi)。(a)列舉三種流行的數(shù)據(jù)倉庫建模模式。(b)使用星型模式，畫出上面數(shù)據(jù)倉庫的模式圖。解答(a)星型模式、雪花模式、或事實(shí)星座模式(b)習(xí)題假定數(shù)據(jù)倉庫包含三個(gè)維：time,doctor和patient；兩個(gè)度量：count和charge；其中，charge是醫(yī)生對(duì)一位病人的一次來訪的收費(fèi)。(c)由基本方體[day,doctor,patient]開始，為列出2004年每位醫(yī)生的收費(fèi)總數(shù)，應(yīng)當(dāng)執(zhí)行哪些OLAP操作？解答上卷（Roll-up）操作，時(shí)間維的概念分層向上攀升，從day攀升到y(tǒng)ear.切片（Slice）操作，fortime=2004.上卷（Roll-up）操作：維規(guī)約，對(duì)patient維進(jìn)行規(guī)約。patientfromindividualpatienttoall.第4章挖掘頻繁模式、關(guān)聯(lián)和相關(guān)由事務(wù)數(shù)據(jù)庫挖掘單維布爾關(guān)聯(lián)規(guī)則最簡單的關(guān)聯(lián)規(guī)則挖掘，即單維、單層、布爾關(guān)聯(lián)規(guī)則的挖掘。最小支持度50%最小置信度50%對(duì)規(guī)則A

D，其支持度=60%置信度Transaction-idItemsbought10A,B,D20A,C,D30A,D,E40B,E,F50B,C,D,E,FD

A(60%,75%)Apriori算法步驟Apriori算法由連接和剪枝兩個(gè)步驟組成。連接：為了找Lk，通過Lk-1與自己連接產(chǎn)生候選k-項(xiàng)集的集合，該候選k項(xiàng)集記為Ck。Lk-1中的兩個(gè)元素L1和L2可以執(zhí)行連接操作的條件是Ck是Lk的超集，即它的成員可能不是頻繁的，但是所有頻繁的k-項(xiàng)集都在Ck中（為什么？）。因此可以通過掃描數(shù)據(jù)庫，通過計(jì)算每個(gè)k-項(xiàng)集的支持度來得到Lk

。為了減少計(jì)算量，可以使用Apriori性質(zhì)，即如果一個(gè)k-項(xiàng)集的(k-1)-子集不在Lk-1中，則該候選不可能是頻繁的，可以直接從Ck刪除。Apriori算法——示例DatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{D}1{E}3Itemsetsup{A}2{B}3{C}3{E}3Itemset{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}Itemsetsup{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2Itemset{B,C,E}Itemsetsup{B,C,E}2最小支持計(jì)數(shù)：2使用Apiori性質(zhì)由L2產(chǎn)生C31．連接：C3=L2

L2={{A,C},{B,C},{B,E}{C,E}}{{A,C},{B,C},{B,E}{C,E}}={{A,B,C},{A,C,E},{B,C,E}}2．使用Apriori性質(zhì)剪枝：頻繁項(xiàng)集的所有子集必須是頻繁的，對(duì)候選項(xiàng)C3，我們可以刪除其子集為非頻繁的選項(xiàng)：{A,B,C}的2項(xiàng)子集是{A,B},{A,C},{B,C}，其中{A,B}不是L2的元素，所以刪除這個(gè)選項(xiàng)；{A,C,E}的2項(xiàng)子集是{A,C},{A,E},{C,E}，其中{A,E}

不是L2的元素，所以刪除這個(gè)選項(xiàng)；{B,C,E}的2項(xiàng)子集是{B,C},{B,E},{C,E}，它的所有2－項(xiàng)子集都是L2的元素，因此保留這個(gè)選項(xiàng)。3．這樣，剪枝后得到C3={{B,C,E}}從FP-tree的項(xiàng)頭表開始,由頻率低的節(jié)點(diǎn)開始按照每個(gè)頻繁項(xiàng)的連接遍歷FP-tree列出能夠到達(dá)此項(xiàng)的所有前綴路徑，得到條件模式基條件模式基item cond.patternbasec f:3a fc:3b fca:1,f:1,c:1m fca:2,fcab:1p fcam:2,cb:1{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1項(xiàng)頭表Itemfrequencyheadf 4c 4a 3b 3m 3p 3步驟1:從FP-tree到條件模式基對(duì)每個(gè)模式基計(jì)算基中每個(gè)項(xiàng)累積計(jì)數(shù)用模式基中的頻繁項(xiàng)建立條件FP-treem-條件模式庫:fca:2,fcab:1{}f:3c:3a:3m-conditionalFP-treeAllfrequentpatternsconcerningmm,fm,cm,am,fcm,fam,cam,fcam{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1頭表Itemfrequencyheadf 4c 4a 3b 3m 3p 3步驟2:建立條件FP-treeEmptyEmptyf{(f:3)}|c{(f:3)}c{(f:3,c:3)}|a{(fc:3)}aEmpty{(fca:1),(f:1),(c:1)}b{(f:3,c:3,a:3)}|m{(fca:2),(fcab:1)}m{(c:3)}|p{(fcam:2),(cb:1)}p條件FP-tree條件模式基項(xiàng)通過建立條件模式庫得到頻繁集對(duì)強(qiáng)關(guān)聯(lián)規(guī)則的批評(píng)（1）例1：(Aggarwal&Yu,PODS98)在5000個(gè)學(xué)生中3000個(gè)打籃球3750個(gè)喝麥片粥2000個(gè)學(xué)生既打籃球又喝麥片粥然而，打籃球=>喝麥片粥[40%,66.7%]是錯(cuò)誤的，因?yàn)槿繉W(xué)生中喝麥片粥的比率是75%，比打籃球?qū)W生的66.7%要高打籃球=>不喝麥片粥[20%,33.3%]這個(gè)規(guī)則遠(yuǎn)比上面那個(gè)要精確，盡管支持度和置信度都要低的多31January202339由關(guān)聯(lián)分析到相關(guān)分析打籃球=>喝麥片粥打籃球=>不喝麥片粥對(duì)強(qiáng)關(guān)聯(lián)規(guī)則的批評(píng)（2）例1：上述數(shù)據(jù)可以得出buys(X,“computergames”)=>buys(X,“videos”)[40%,60%]但其實(shí)全部人中購買錄像帶的人數(shù)是75%，比60%多；事實(shí)上錄像帶和游戲是負(fù)相關(guān)的。由此可見A=>B的置信度有欺騙性，它只是給出A,B條件概率的估計(jì)，而不度量A,B間蘊(yùn)涵的實(shí)際強(qiáng)度。由關(guān)聯(lián)分析到相關(guān)分析我們需要一種度量事件間的相關(guān)性或者是依賴性的指標(biāo)當(dāng)項(xiàng)集A的出現(xiàn)獨(dú)立于項(xiàng)集B的出現(xiàn)時(shí)，P(A∪B)=P(A)P(B)，即lift＝1，表明A與B無關(guān)，lift>1表明A與B正相關(guān)，lift<1表明A與B負(fù)相關(guān)將相關(guān)性指標(biāo)用于前面的例子，可以得出錄像帶和游戲?qū)⒌南嚓P(guān)性為：P({game,video})/(P({game})×P({video}))

=0.4/(0.75×0.6)=0.89結(jié)論：錄像帶和游戲之間存在負(fù)相關(guān)第6章分類和預(yù)測(cè)31January202343信息增益(2)設(shè)屬性A具有v個(gè)不同值{a1,a2,…,av}?？梢杂脤傩訟將S劃分為v個(gè)子集{S1,...,Sv}；其中，Sj

包含S中這樣一些樣本，它們?cè)贏上具有值aj。如果A選作測(cè)試屬性（即，最好的劃分屬性），則這些子集對(duì)應(yīng)于由包含集合S的結(jié)點(diǎn)生長出來的分枝。設(shè)Sij

是子集Sj

中類Ci

的樣本數(shù)。根據(jù)A劃分子集的熵或期望信息由下式給出：A上該劃分的獲得的信息增益定義為具有最高信息增益的屬性,是給定集合中具有高度區(qū)分度的屬性.所以可以通過計(jì)算集合S中樣本的每個(gè)屬性的信息增益,來得到一個(gè)屬性的相關(guān)性的排序ageincomestudentcredit_ratingbuys_computer<=30highnofairno<=30highnoexcellentno31…40highnofairyes>40mediumnofairyes>40lowyesfairyes>40lowyesexcellentno31…40lowyesexcellentyes<=30mediumnofairno<=30lowyesfairyes>40mediumyesfairyes<=30mediumyesexcellentyes31…40mediumnoexcellentyes31…40highyesfairyes>40mediumnoexcellentno判定歸納樹算法示例通過信息增益的屬性選擇Class:buys_computer=“yes”Class:buys_computer=“no”I(s1,s2)=I(9,5)=0.940Computetheentropyforage:HenceSimilarly判定歸納樹算法示例(1)計(jì)算基于熵的度量——信息增益，作為樣本劃分的根據(jù)Gain(age)=0.246Gain(income)=0.029Gain(student)=0.151Gain(credit_rating)=0.048然后，對(duì)測(cè)試屬性每個(gè)已知的值，創(chuàng)建一個(gè)分支，并以此劃分樣本，得到第一次劃分判定歸納樹算法示例(2)判定歸納樹算法示例(3)age?student?creditrating?noyesfairexcellent<=30>40nonoyesyesyes30..40由決策樹提取分類規(guī)則可以提取決策樹表示的知識(shí)，并以IF-THEN形式的分類規(guī)則表示對(duì)從根到樹葉的每條路徑創(chuàng)建一個(gè)規(guī)則沿著給定路徑上的每個(gè)屬性-值對(duì)形成規(guī)則前件（"IF"部分）的一個(gè)合取項(xiàng)葉節(jié)點(diǎn)包含類預(yù)測(cè)，形成規(guī)則后件（"THEN"部分）IF-THEN規(guī)則易于理解，尤其樹很大時(shí)示例：IFage=“<=30”ANDstudent=“no”THENbuys_computer=“no”IFage=“<=30”ANDstudent=“yes”THENbuys_computer=“yes”IFage=“31…40”THENbuys_computer=“yes”IFage=“>40”ANDcredit_rating=“excellent”THENbuys_computer=“yes”IFage=“>40”ANDcredit_rating=“fair”THENbuys_computer=“no”舉例說明目標(biāo)概念PlayTennis的訓(xùn)練樣例

DayOutlookTemperatureHumidityWindPlayTennisD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainMildHighWeakYesD5RainCoolNormalWeakYesD6RainCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainMildHighStrongNo統(tǒng)計(jì)個(gè)數(shù)表1類別為cj及在cj條件下Ai取ai的樣例數(shù)OutlookTemperatureHumidityWindPlayTennisSunnyOvercastRainHotMildCoolHighNormalWeakStrong2432433663Yes93022214123No5估計(jì)先驗(yàn)概率和條件概率表2先驗(yàn)概率P(cj)和條件概率P(ai|cj)OutlookTemperatureHumidityWindPlayTennisSunnyOvercastRainHotMildCoolHighNormalWeakStrong0.2220.4440.3330.2220.4440.3330.3330.6670.6670.333Yes0.6430.600.40.40.40.20.80.20.40.6No0.357樣例判別現(xiàn)在假設(shè)有一個(gè)樣例x

x={Sunny,Hot,High,Weak}等于yes的概率P(Yes|x)=p(Yes)*p(Sunny|Yes)*p(Hot|Yes)*p(High|Yes)*p(Weak|Yes)* =0.643*0.222*0.222*0.333*0.667=0.007039等于No的概率P(No|x)=p(No)*p(Sunny|No)*p(Hot|No)*p(High|No)*p(Weak|No)* =0.357*0.6*0.4*0.8*0.4=0.027418max(P(Yes|x),P(No|x))=P(No|x),所以我們把x分類為No31January202354樸素貝葉斯分類實(shí)例2Class:C1:buys_computer=‘yes’C2:buys_computer=‘no’DatasampleX=(age<=30,Income=medium,Student=yesCredit_rating=Fair)估計(jì)先驗(yàn)概率P(cj)和條件概率P(ai|cj)

ageP(<=30|buys_computer=yes)=2/9P(<=30|buys_computer=no)=3/5P(31…40|buys_computer=yes)=4/9P(31…40|buys_computer=no)=0P(>40|buys_computer=yes)=3/9P(>40|buys_computer=no)=2/5incomeP(high|buys_computer=yes)=2/9P(high|buys_computer=no)=2/5P(medium|buys_computer=yes)=4/9P(medium|buys_computer=no)=2/5P(low|buys_computer=yes)=3/9P(low|buys_computer=no)=1/5studentP(yes|buys_computer=yes)=6/9P(yes|buys_computer=no)=1/5P(no|buys_computer=yes)=3/9P(no|buys_computer=no)=4/5credit_rating

P(excellent|buys_computer=yes)=3/9P(excellent|buys_computer=no)=3/5P(fair|buys_computer=yes)=6/9P(fair|buys_computer=no)=2/5P(buys_computer=yes)=9/14P(buys_computer=no)=5/14樸素貝葉斯分類實(shí)例2ComputeP(X/Ci)foreachclass

P(age=“<30”|buys_computer=“yes”)=2/9=0.222

P(age=“<30”|buys_computer=“no”)=3/5=0.6

P(income=“medium”|buys_computer=“yes”)=4/9=0.444

P(income=“medium”|buys_computer=“no”)=2/5=0.4

P(student=“yes”|buys_computer=“yes)=6/9=0.667

P(student=“yes”|buys_computer=“no”)=1/5=0.2

P(credit_rating=“fair”|buys_computer=“yes”)=6/9=0.667

P(credit_rating=“fair”|buys_computer=“no”)=2/5=0.4X=(age<=30,income=medium,student=yes,credit_rating=fair)

P(X|Ci):

P(X|buys_computer=“yes”)=0.222x0.444x0.667x0.667=0.044

P(X|buys_computer=“no”)=0.6x0.4x0.2x0.4=0.019P(X|Ci)*P(Ci):P(X|buys_computer=“yes”)*P(buys_computer=“yes”)=0.028

P(X|buys_computer=“no”)*P(buys_computer=“no”)=0.007Xbelongstoclass“buys_computer=yes” 31January202356打網(wǎng)球?qū)嵗?估計(jì)P(xi|C)outlookP(sunny|p)=2/9P(sunny|n)=3/5P(overcast|p)=4/9P(overcast|n)=0P(rain|p)=3/9P(rain|n)=2/5temperatureP(hot|p)=2/9P(hot|n)=2/5P(mild|p)=4/9P(mild|n)=2/5P(cool|p)=3/9P(cool|n)=1/5humidityP(high|p)=3/9P(high|n)=4/5P(normal|p)=6/9P(normal|n)=2/5windyP(strong|p)=3/9P(strong|n)=3/5P(Weak|p)=6/9P(Weak|n)=2/5P(p)=9/14P(n)=5/14打網(wǎng)球?qū)嵗?分類XX=<rain,hot,high,weak>P(X|p)·P(p)=

P(rain|p)·P(hot|p)·P(high|p)·P(weak|p)·P(p)=3/9·2/9·3/9·6/9·9/14=0.010582P(X|n)·P(n)=

P(rain|n)·P(hot|n)·P(high|n)·P(weak|n)·P(n)=2/5·2/5·4/5·2/5·5/14=0.018286樣本X分類為n(don’tplay)第7章聚類分析對(duì)象間的相似度和相異度(2)例：用x1=(1,2)和x2=（3,5）表示兩個(gè)對(duì)象。求兩點(diǎn)之間的歐幾里得距離和曼哈頓距離。歐幾里得距離曼哈頓距離二元變量(2)對(duì)稱的VS.不對(duì)稱的二元變量對(duì)稱的二元變量指變量的兩個(gè)狀態(tài)具有同等價(jià)值，相同權(quán)重；e.g.性別基于對(duì)稱的二元變量的相似度稱為恒定的相似度，可以使用簡單匹配系數(shù)評(píng)估它們的相異度：不對(duì)稱的二元變量中，變量的兩個(gè)狀態(tài)的重要性是不同的；e.g.HIV陽性VSHIV陰性給定兩個(gè)不對(duì)稱的二元變量，兩個(gè)都取值1的情況被認(rèn)為比兩個(gè)都取值0的情況更有意義。兩個(gè)都取值0的數(shù)目被認(rèn)為是不重要的，因此被忽略?；诓粚?duì)稱的二元變量的相似度稱為非恒定的相似度，可以使用Jaccard系數(shù)評(píng)估二元變量的相異度——示例例

二元變量之間的相異度（病人記錄表）Name是對(duì)象標(biāo)識(shí)gender是對(duì)稱的二元變量其余屬性都是非對(duì)稱的二元變量如過Y和P（positive陽性）為1，N為0，則：

分類變量(2)求下面分類變量的相異度矩陣

，p=1,當(dāng)對(duì)象i和j匹配時(shí)，d(i,j)=0,當(dāng)對(duì)象不同時(shí)，

d(i,j)=1。=序數(shù)型變量(2)求下面序數(shù)型變量的相異度矩陣Test-2有三個(gè)狀態(tài)，分別是一般，好，優(yōu)秀，也就是=3第一步：把Test-2的每個(gè)值替換為它的秩，四個(gè)對(duì)象分別賦值為3,1,2,3第二步：將秩映射到【0.0,1.0】區(qū)間第三步，采用區(qū)間標(biāo)度變量的相異度計(jì)算

方法計(jì)算f的相異度，如使用歐幾里得距離比例標(biāo)度變量(2)求下面比例標(biāo)度變量的相異度矩陣第一步對(duì)屬性Test-3取對(duì)數(shù)，分別為2.65，1.34，2.21和3.08第二步利于區(qū)間標(biāo)度變量計(jì)算方法，如使用歐幾里得距離公式，對(duì)到如下相異度矩陣K-Means聚類:例2

(1)假設(shè)有四種藥品，每種藥品有兩個(gè)屬性如下表表示。我們的目標(biāo)是將這四種藥品聚為兩個(gè)類，即K=2Objectattribute1(X):weightindexattribute2(Y):pHMedicineA11MedicineB21MedicineC43MedicineD54K-Means聚類:例2

(2)每種藥品的兩個(gè)屬性表示為坐標(biāo)上的一個(gè)點(diǎn)(X,Y)，如下圖所示K-Means聚類:例2(3)1、初始中心點(diǎn)的選擇：假設(shè)選擇medicineA和medicineB作為初始的兩個(gè)的簇的中心點(diǎn)。表示為c1=(1,1)和c2=(2,1)。2、計(jì)算每個(gè)對(duì)象到中心點(diǎn)的距離：使用歐幾里得公式，我們得到距離矩陣K-Means聚類:例2(4)3、對(duì)象聚類：將數(shù)據(jù)對(duì)象賦給最近距離的簇集.即medicineA歸為group1，medicineB歸為group2，medicineC歸為group2，medicineD歸為group2.4.迭代,重新確定中心點(diǎn):我們重新計(jì)算中心點(diǎn)，Group1只有一個(gè)對(duì)象medicineA，中心點(diǎn)仍為c1=(1,1)，Group2現(xiàn)有3個(gè)對(duì)象，中心點(diǎn)位3個(gè)對(duì)象的坐標(biāo)的平均值。K-Means聚類:例2(5)5、計(jì)算每個(gè)對(duì)象到新的中心點(diǎn)的距離：和第2步類似，使用歐幾里得公式，我們得到距離矩陣如下6、對(duì)象聚類：將數(shù)據(jù)對(duì)象賦給最近距離的簇集.和第3步類似。將medicineB移到Group1中，其他不變7、再確定中心點(diǎn)，計(jì)算新的分簇的中心點(diǎn)，Group1和Group2各有兩個(gè)對(duì)象，中心點(diǎn)計(jì)算如下式所示：

K-Means聚類:例2(6)8、重復(fù)第2步，計(jì)算每個(gè)對(duì)象到新的中心點(diǎn)的距離，得到一個(gè)新的距離矩陣9、重復(fù)第3步,對(duì)象重新聚類：將數(shù)據(jù)對(duì)象賦給最近距離的簇集.K-Means聚類:例2(7)最后一次的聚類結(jié)果表明聚類結(jié)果不再改變，達(dá)到穩(wěn)定，我們得到了最后的聚類結(jié)果，如下表所示ObjectFeature1(X):weightindexFeature2(Y):pHGroup(result)MedicineA111MedicineB211MedicineC432MedicineD54273假如空間中的五個(gè)點(diǎn)｛A、Ｂ、Ｃ、Ｄ、Ｅ｝如圖1所示，各點(diǎn)之間的距離關(guān)系如表1所示，根據(jù)所給的數(shù)據(jù)對(duì)其運(yùn)行PAM算法實(shí)現(xiàn)劃分聚類（設(shè)k=2）。樣本點(diǎn)間距離如下表所示:

樣本點(diǎn)起始中心點(diǎn)為A,B

PAM算法基本思想(續(xù))樣本點(diǎn)ABCDEA01223B10243C22015D24103E3353074PAM算法基本思想(續(xù))第一步建立階段：假如從5個(gè)對(duì)象中隨機(jī)抽取的2個(gè)中心點(diǎn)為{A，B},則樣本被劃分為{A、C、D}和{B、E}，如圖所示。第二步交換階段：假定中心點(diǎn)A、B分別被非中心點(diǎn){C、D、E}替換，根據(jù)PAM算法需要計(jì)算下列代價(jià)TCAC、

TCAD、

TCAE、TCBC、TCBD、

TCBE。我們以TCAC為例說明計(jì)算過程：a)當(dāng)A被C替換以后，A不再是一個(gè)中心點(diǎn)，因?yàn)锳離B比A離C近，A被分配到B中心點(diǎn)代表的簇，CAAC=d(A,B)-d(A,A)=1。b)B是一個(gè)中心點(diǎn)，當(dāng)A被C替換以后，B不受影響，CBAC=0。c)C原先屬于A中心點(diǎn)所在的簇，當(dāng)A被C替換以后，C是新中心點(diǎn)，符合PAM算法代價(jià)函數(shù)的第二種情況CCAC=d(C,C)-d(C,A)=0-2=-2。d)D原先屬于A中心點(diǎn)所在的簇，當(dāng)A被C替換以后，離D最近的中心點(diǎn)是C，根據(jù)PAM算法代價(jià)函數(shù)的第二種情況CDAC=d(D,C)-d(D,A)=1-2=-1。e)E原先屬于B中心點(diǎn)所在的簇，當(dāng)A被C替換以后，離E最近的中心仍然是B，根據(jù)PAM算法代價(jià)函數(shù)的第三種情況CEAC=0。因此，TCAC=CAAC+CBAC+CBAC+CDAC+CEAC=1+0-2-1+0=-2。75PAM算法基本思想(續(xù))

在上述代價(jià)計(jì)算完畢后，我們要選取一個(gè)最小的代價(jià)，顯然有多種替換可以選擇，我們選擇第一個(gè)最小代價(jià)的替換（也就是C替換A），根據(jù)圖（a）所示，樣本點(diǎn)被劃分為{B、A、E}和{C、D}兩個(gè)簇。圖（b）和圖（c）分別表示了D替換A，E替換A的情況和相應(yīng)的代價(jià)

a)C替換A,TCAC=-2(b)D替換A,TCAD=-2(c)E替換A,TCAE=-176PAM算法基本思想(續(xù))

C替換B,TCBC=-2(b)D替換B,TCBD=-2(c)E替換B,TCBE=-2通過上述計(jì)算，已經(jīng)完成了PAM算法的第一次迭代。在下一迭代中，將用其他的非中心點(diǎn){A、D、E}替換中心點(diǎn){B、C}，找出具有最小代價(jià)的替換。一直重復(fù)上述過程，直到代價(jià)不再減小為止。77AGNES算法例子序號(hào) 屬性1 屬性2 1 1 1 2 1 2 3 2 1 4 2 2 5 3 4 6 3 5 7 4 4 8 4 5 第1步：根據(jù)初始簇計(jì)算每個(gè)簇之間的距離，隨機(jī)找出距離最小的兩個(gè)簇，進(jìn)行合并，最小距離為1，合并后1，2點(diǎn)合并為一個(gè)簇。第2步：，對(duì)上一次合并后的簇計(jì)算簇間距離，找出距離最近的兩個(gè)簇進(jìn)行合并，合并后3，4點(diǎn)成為一簇。第3步：重復(fù)第2步的工作，5，6點(diǎn)成為一簇。第4步：重復(fù)第2步的工作，7，8點(diǎn)成為一簇。第5步：合并{1，2}，{3，4}成為一個(gè)包含四個(gè)點(diǎn)的簇。第6步：合并{5，6}，{7，8}，由于合并后的簇的數(shù)目已經(jīng)達(dá)到了用戶輸入的終止條件程序結(jié)束。AGNES算法例子(續(xù))步驟最近的簇距離最近的兩個(gè)簇合并后的新簇11{1}，{2}{1，2}，{3}，{4}，{5}，{6}，{7}，{8}21{3}，{4}{1，2}，{3，4}，{5}，{6}，{7}，{8}31{5}，{6}{1，2}，{3，4}，{5，6}，{7}，{8}41{7}，{8}{1，2}，{3，4}，{5，6}，{7，8}51{1，2}，{3，4}{1，2，3，4}，{5，6}，{7，8}61{5，6}，{7，8}{1，2，3，4}，{5，6，7，8}結(jié)束DIANA算法例子序號(hào) 屬性1 屬性2 1 1 1 2 1 2 3 2 1 4 2 2 5 3 4 6 3 5 7 4 4 8 4 5 第1步，找到具有最大直徑的簇，對(duì)簇中的每個(gè)點(diǎn)計(jì)算平均相異度（假定采用是歐式距離）。1的平均距離：（1+1+1.414+3.6+4.24+4.47+5）/7=2.96類似地，2的平均距離為2.526；3的平均距離為2.68；4的平均距離為2