數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘習(xí)題

1、數(shù)據(jù)倉(cāng)庫(kù)與數(shù) 據(jù) 挖 掘,主講教師：王浩暢E-mail: wanghch_angel@tom.comSchool of Computer & Information Technology of NEPU,第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

2、, 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

3、=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

4、 第三個(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.

5、(f)畫(huà)出數(shù)據(jù)的盒圖,解答,噪聲數(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ù)包含屬

6、性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.解釋你的步驟,解答,Step 1: 排序數(shù)據(jù).Step 2: 將有序值劃分到大小為3的等頻箱中Step 3: 計(jì)算每個(gè)箱中

7、數(shù)據(jù)的算術(shù)平均值.Step 4:.將每個(gè)箱中的每個(gè)值用此箱的算術(shù)平均值替換Bin1: 44/3, 44/3, 44/3 Bin2: 55/3, 55/3, 55/3Bin3: 21, 21, 21 Bin4: 24, 24, 24…,規(guī)范化最?。畲笠?guī)范化：對(duì)原始數(shù)據(jù)進(jìn)行線性變換。假定minA 和 maxA 分別為屬性A 的最小和最大值。將A的值v映射到區(qū)間[new _ minA, new _ maxA]

8、中的v’最小-最大規(guī)范化通過(guò)計(jì)算例： 假定屬性income的最小與最大值分別為12 000美元和98 000美元。我們想把income映射到區(qū)間[0.0, 0.1]。根據(jù)最小最大規(guī)范化，income值73 600美元將變換為：,數(shù)據(jù)變換(2),z-score規(guī)范化：屬性A 的值基于A 的平均值和標(biāo)準(zhǔn)差規(guī)范化。最大最小值未知，或者離群點(diǎn)影響較大的時(shí)候適用例：假定屬性income的均值和標(biāo)準(zhǔn)差分別為54 000美元和16 00

9、0美元。使用z-score規(guī)范化，值73 600美元轉(zhuǎn)換為,數(shù)據(jù)變換(3),小數(shù)定標(biāo)規(guī)范化：通過(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ī)范化，用1 000（即j = 3）除每個(gè)值，這樣，－986規(guī)范化為－0.986，而917被規(guī)范化為0.917。,數(shù)據(jù)變換(4),其中，j是使 Max(| |)<1的最小整數(shù)

10、,練習(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

11、, 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 的

12、一個(gè)不同值。,通過(guò)自然劃分分段,將數(shù)值區(qū)域劃分為相對(duì)一致的、易于閱讀的、看上去更直觀或自然的區(qū)間。聚類分析產(chǎn)生概念分層可能會(huì)將一個(gè)工資區(qū)間劃分為：[51263.98, 60872.34]通常數(shù)據(jù)分析人員希望看到劃分的形式為[50000，60000]自然劃分的3-4-5規(guī)則常被用來(lái)將數(shù)值數(shù)據(jù)劃分為相對(duì)一致，“更自然”的區(qū)間,自然劃分的3-4-5規(guī)則,規(guī)則的劃分步驟：如果一個(gè)區(qū)間最高有效位上包含3，6，7或9個(gè)不同的值，就將該區(qū)間劃

13、分為3個(gè)等寬子區(qū)間；(7?2,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ī)則——例

14、子,,假定AllElectronics 所有分部1999 年的利潤(rùn)覆蓋了一個(gè)很寬的區(qū)間，由-$351,976.00 到 $4,700,896.50。用戶希望自動(dòng)地產(chǎn)生利潤(rùn)的概念分層。為了改進(jìn)可讀性，我們使用記號(hào)(l...r]表示區(qū)間(l,r]。例如，(-$1,000,000...$0]表示由-$1,000,000（開(kāi)的）到$0（閉的）的區(qū)間。1． 根據(jù)以上信息，最小和最大值分別為MIN = -$351,976.00 和MAX = $4

15、,700,896.50。對(duì)于分段的頂層或第一層，要考慮的最低（第5 個(gè)百分位數(shù)）和最高（第95 個(gè)百分位數(shù)）值是：LOW =-$159,876，HIGH = $1,838,761。2． 給定LOW 和HIGH，最高有效位在百萬(wàn)美元數(shù)字位（即，msd=1,000,000）。LOW 向下對(duì)百萬(wàn)美元數(shù)字位取整，得到LOW’= -$1,000,000；HIGH 向上對(duì)百萬(wàn)美元數(shù)字位取整，得到HIGH’ = +$2,000,000。,3-4-5

16、規(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，看它們“適合”在第一層分劃的什么地方。由于第

17、一個(gè)區(qū)間(-$1,000,000...$0]覆蓋了MIN 值（即，LOW′ HIGH′，我們需要?jiǎng)?chuàng)建一個(gè)新的區(qū)間來(lái)覆蓋它。對(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

18、規(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

19、,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

20、], ($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ù)迭代􀀀,

21、3-4-5規(guī)則——例子,第3章數(shù)據(jù)倉(cāng)庫(kù)和數(shù)據(jù)挖掘的OLAP技術(shù),習(xí)題,假定 數(shù)據(jù)倉(cāng)庫(kù)包含三個(gè)維：time, doctor 和patient；兩個(gè)度量：count 和charge；其中，charge 是醫(yī)生對(duì)一位病人的一次來(lái)訪的收費(fèi)。(a) 列舉三種流行的數(shù)據(jù)倉(cāng)庫(kù)建模模式。(b) 使用星型模式，畫(huà)出上面數(shù)據(jù)倉(cāng)庫(kù)的模式圖。,解答,(a)星型模式、雪花模式、或事實(shí)星座模式(b),習(xí)題,假定 數(shù)據(jù)倉(cāng)庫(kù)包含三個(gè)維：time, doctor

22、和patient；兩個(gè)度量：count 和charge；其中，charge 是醫(yī)生對(duì)一位病人的一次來(lái)訪的收費(fèi)。(c)由基本方體[day, doctor, patient]開(kāi)始，為列出2004 年每位醫(yī)生的收費(fèi)總數(shù)，應(yīng)當(dāng)執(zhí)行哪些OLAP 操作？,解答,上卷（Roll-up）操作，時(shí)間維的概念分層向上攀升，從day攀升到y(tǒng)ear.切片（Slice）操作， for time=2004.上卷（Roll-up）操作：維規(guī)約，對(duì)patient

23、維進(jìn)行規(guī)約。 patient from individual patient to all.,第4章 挖掘頻繁模式、關(guān)聯(lián)和相關(guān),由事務(wù)數(shù)據(jù)庫(kù)挖掘單維布爾關(guān)聯(lián)規(guī)則,最簡(jiǎn)單的關(guān)聯(lián)規(guī)則挖掘，即單維、單層、布爾關(guān)聯(lián)規(guī)則的挖掘。,最小支持度 50%最小置信度 50%,對(duì)規(guī)則A ? D，其支持度 =60%置信度,,,D A (60%, 75%),?,Apriori算

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

25、-項(xiàng)集的(k-1)-子集不在Lk-1中，則該候選不可能是頻繁的，可以直接從Ck刪除。,,,Apriori算法——示例,Database TDB,1st scan,,C1,L1,L2,C2,C2,,2nd scan,,,C3,L3,3rd scan,,,,最小支持計(jì)數(shù)：2,使用Apiori性質(zhì)由L2產(chǎn)生C3,1 ．連接：C3=L2 L2= {{A,C},{B,C},{B,E}{C,E}} {{A,C},{B,C},

26、{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)

27、子集是{B,C},{B,E},{C,E}，它的所有2－項(xiàng)子集都是L2的元素，因此保留這個(gè)選項(xiàng)。3．這樣，剪枝后得到C3={{B,C,E}},,從FP-tree的項(xiàng)頭表開(kāi)始,由頻率低的節(jié)點(diǎn)開(kāi)始按照每個(gè)頻繁項(xiàng)的連接遍歷 FP-tree列出能夠到達(dá)此項(xiàng)的所有前綴路徑，得到條件模式基,條件模式基itemcond. pattern basecf:3afc:3bfca:1, f:1, c:1mfca:2, fcab:1p

28、fcam:2, cb:1,步驟1: 從 FP-tree 到條件模式基,對(duì)每個(gè)模式基計(jì)算基中每個(gè)項(xiàng)累積計(jì)數(shù)用模式基中的頻繁項(xiàng)建立條件FP-tree,m-條件模式庫(kù):fca:2, fcab:1,All frequent patterns concerning mm, fm, cm, am, fcm, fam, cam, fcam,?,?,{},f:4,c:1,b:1,p:1,b:1,c:3,a:3,b:1,m:2,p:2,m

29、:1,頭表Item frequency head f4c4a3b3m3p3,,,,,,,,,,,,步驟2: 建立條件 FP-tree,通過(guò)建立條件模式庫(kù)得到頻繁集,對(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ò)

30、誤的，因?yàn)槿繉W(xué)生中喝麥片粥的比率是75%，比打籃球?qū)W生的66.7%要高打籃球 => 不喝麥片粥 [20%, 33.3%]這個(gè)規(guī)則遠(yuǎn)比上面那個(gè)要精確，盡管支持度和置信度都要低的多,March 23, 2024,39,由關(guān)聯(lián)分析到相關(guān)分析,打籃球 => 喝麥片粥,打籃球 => 不喝麥片粥,對(duì)強(qiáng)關(guān)聯(lián)規(guī)則的批評(píng)（2）,例1：上述數(shù)據(jù)可以得出buys(X, “computer games”) => buys(X,

31、“videos”) [40%, 60%]但其實(shí)全部人中購(gòu)買(mǎi)錄像帶的人數(shù)是75%，比60%多；事實(shí)上錄像帶和游戲是負(fù)相關(guān)的。由此可見(jià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無(wú)關(guān)， lift >1表明A與

32、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è),March 23, 2024,43,信息增益(2),設(shè)屬性A 具有v 個(gè)不同值{a1,a2,…,av} 。可以用屬性A 將S 劃分

33、為v 個(gè)子集{S1 ,..., Sv}；其中，Sj 包含S 中這樣一些樣本，它們?cè)贏 上具有值aj。如果A 選作測(cè)試屬性（即，最好的劃分屬性），則這些子集對(duì)應(yīng)于由包含集合S 的結(jié)點(diǎn)生長(zhǎng)出來(lái)的分枝。設(shè)Sij 是子集Sj 中類Ci 的樣本數(shù)。根據(jù)A劃分子集的熵或期望信息由下式給出：A 上該劃分的獲得的信息增益定義為具有最高信息增益的屬性,是給定集合中具有高度區(qū)分度的屬性.所以可以通過(guò)計(jì)算集合S中樣本的每個(gè)屬性的信息增益,來(lái)得到一

34、個(gè)屬性的相關(guān)性的排序,判定歸納樹(shù)算法示例,通過(guò)信息增益的屬性選擇,Class: buys_computer = “yes”Class: buys_computer = “no”I(s1,s2) = I(9, 5) =0.940Compute the entropy for age:,HenceSimilarly,判定歸納樹(shù)算法示例 (1),計(jì)算基于熵的度量——信息增益，作為樣本劃分的根據(jù)Gain(age)=0.246Ga

35、in(income)=0.029Gain(student)=0.151Gain(credit_rating)=0.048然后，對(duì)測(cè)試屬性每個(gè)已知的值，創(chuàng)建一個(gè)分支，并以此劃分樣本，得到第一次劃分,判定歸納樹(shù)算法示例 (2),判定歸納樹(shù)算法示例 (3),由決策樹(shù)提取分類規(guī)則,可以提取決策樹(shù)表示的知識(shí)，并以IF-THEN形式的分類規(guī)則表示對(duì)從根到樹(shù)葉的每條路徑創(chuàng)建一個(gè)規(guī)則沿著給定路徑上的每個(gè)屬性-值對(duì)形成規(guī)則前件（"IF

36、"部分）的一個(gè)合取項(xiàng)葉節(jié)點(diǎn)包含類預(yù)測(cè)，形成規(guī)則后件（"THEN"部分）IF-THEN規(guī)則易于理解，尤其樹(shù)很大時(shí)示例：IF age = “40” AND credit_rating = “excellent” THEN buys_computer = “yes”IF age = “>40” AND credit_rating = “fair” THEN buys_computer =

37、 “no”,舉例說(shuō)明,目標(biāo)概念PlayTennis的訓(xùn)練樣例,統(tǒng)計(jì)個(gè)數(shù),表1 類別為cj及在cj條件下Ai取ai的樣例數(shù),估計(jì)先驗(yàn)概率和條件概率,表2 先驗(yàn)概率P(cj) 和條件概率P(ai|cj),樣例判別,現(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)

38、*=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分類為No,March 23, 2024,54,樸素

39、貝葉斯分類 實(shí)例2,Class:C1:buys_computer = ‘yes’C2:buys_computer = ‘no’Data sample X = (age <=30,Income = medium,Student = yesCredit_rating = Fair),估計(jì) 先驗(yàn)概率P(cj) 和條件概率P(ai|cj),樸素貝葉斯分類 實(shí)例2,Compute P(X/Ci) for each class

40、 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 =

41、 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

42、”)=2/5=0.4 X=(age<=30 ,income =medium, student=yes,credit_rating=fair) P(X|Ci) : P(X|buys_computer=“yes”)= 0.222 x 0.444 x 0.667 x 0.667 =0.044 P(X|buys_computer=“no”)= 0.6 x 0.4 x 0.2 x 0.4 =0.019

43、P(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.007X belongs to class “buys_computer=yes”,March 23, 2024,56,打網(wǎng)球?qū)嵗? 估計(jì) P(xi|C),打網(wǎng)球?qū)嵗?/p>

44、: 分類 X,X = 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(wea

45、k|n)·P(n) = 2/5·2/5·4/5·2/5·5/14 = 0.018286樣本 X分類為n (don’t play),第7章聚類分析,對(duì)象間的相似度和相異度(2),例：用x1=(1,2)和x2=（3,5）表示兩個(gè)對(duì)象。求兩點(diǎn)之間的歐幾里得距離和曼哈頓距離。歐幾里得距離曼哈頓距離,二元變量 (2),對(duì)稱的 VS. 不對(duì)稱的 二元變量對(duì)稱的二元變量指變量的兩個(gè)狀態(tài)具有同

46、等價(jià)值，相同權(quán)重；e.g. 性別基于對(duì)稱的二元變量的相似度稱為恒定的相似度，可以使用簡(jiǎn)單匹配系數(shù)評(píng)估它們的相異度：不對(duì)稱的二元變量中，變量的兩個(gè)狀態(tài)的重要性是不同的；e.g. HIV陽(yáng)性 VS HIV陰性給定兩個(gè)不對(duì)稱的二元變量，兩個(gè)都取值1的情況被認(rèn)為比兩個(gè)都取值0的情況更有意義。兩個(gè)都取值0的數(shù)目被認(rèn)為是不重要的，因此被忽略。基于不對(duì)稱的二元變量的相似度稱為非恒定的相似度，可以使用Jaccard系數(shù)評(píng)估,二元變量的相異度

47、——示例,例 二元變量之間的相異度 （病人記錄表）,Name是對(duì)象標(biāo)識(shí)gender是對(duì)稱的二元變量其余屬性都是非對(duì)稱的二元變量如過(guò)Y和P（positive陽(yáng)性）為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有三

48、個(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ì)算方法，如使用歐幾里得距離

49、公式，對(duì)到如下相異度矩陣,K-Means 聚類: 例 2 (1),假設(shè)有四種藥品，每種藥品有兩個(gè)屬性如下表表示。我們的目標(biāo)是將這四種藥品聚為兩個(gè)類，即K=2,K-Means 聚類: 例 2 (2),每種藥品的兩個(gè)屬性表示為坐標(biāo)上的一個(gè)點(diǎn)(X, Y)，如下圖所示,K-Means 聚類: 例 2(3),1、初始中心點(diǎn)的選擇：假設(shè)選擇medicine A 和 medicine B 作為初始的兩個(gè)的簇的中心點(diǎn)。表示為c1=(1,1) 和c

50、2=(2,1) 。2、計(jì)算每個(gè)對(duì)象到中心點(diǎn)的距離：使用歐幾里得公式，我們得到距離矩陣,K-Means 聚類: 例 2(4),3、對(duì)象聚類：將數(shù)據(jù)對(duì)象賦給最近距離的簇集.即medicine A歸為group 1，medicine B歸為group 2，medicine C歸為group 2，medicine D歸為group 2. 4. 迭代 , 重新確定中心點(diǎn):我們重新計(jì)算中心點(diǎn)，Group 1只有一個(gè)對(duì)象medicine A，中

51、心點(diǎn)仍為c1=(1,1) ，Group 2現(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步類似。將medicine B移到Group 1中，其他不變7、再確定中心點(diǎn)，計(jì)算新的分簇的中心點(diǎn)，Group1和Group2各有兩個(gè)對(duì)象，中心點(diǎn)計(jì)算如下式所

52、示：,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é)果，如下表所示,73,假如空間中的五個(gè)點(diǎn)｛A、Ｂ、Ｃ、Ｄ、Ｅ｝如圖1所示，各點(diǎn)之間的距離關(guān)系如表1所示，根據(jù)所給的數(shù)據(jù)對(duì)其運(yùn)行PAM算法實(shí)現(xiàn)劃分聚類（

53、設(shè)k=2）。 樣本點(diǎn)間距離如下表所示: 樣本點(diǎn) 起始中心點(diǎn)為A,B,PAM算法基本思想(續(xù)),,,,,,,,,,,,,,,,,,74,PAM算法基本思想(續(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ù)P

54、AM算法需要計(jì)算下列代價(jià)TCAC、 TCAD、 TCAE、TCBC、TCBD、 TCBE。我們以TCAC為例說(shuō)明計(jì)算過(guò)程：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

55、=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。,7

56、5,PAM算法基本思想(續(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 (

57、c) E替換A, TCAE=-1,,,,,,,76,PAM算法基本思想(續(xù)),,,,,,,,,,,,,,,,,,C替換B, TCBC=-2 (b) D替換B, TCBD=-2 (c) E替換B, TCBE=-2通過(guò)上述計(jì)算，已經(jīng)完成了PAM算法的第一次迭代。在下一迭代中，將用其他的非中心點(diǎn){A、D、E}替換中心點(diǎn){B、C}，找出具有最小代價(jià)的替換。一直重復(fù)上述過(guò)程，直到代價(jià)不再

58、減小為止。,,,,,,,77,AGNES算法例子,,序號(hào)屬性 1屬性 2111212321422534635744845,,,第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步的工作

59、，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ù)),DIANA算法例子,,序號(hào)屬性 1屬性 2111212321422534635744845,,第1步，找到具有最大直

60、徑的簇，對(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.18；5的平均距離為2.18；6的平均距離為2.68；7的平均距離為2.526；8的平均距離為2.96。 挑出平均相異度最大的點(diǎn)1放到splinter group中，剩余點(diǎn)在old par

61、ty中。第2步，在old party里找出到最近的splinter group中的點(diǎn)的距離不大于到old party中最近的點(diǎn)的距離的點(diǎn)，將該點(diǎn)放入splinter group中，該點(diǎn)是2。第3步，重復(fù)第2步的工作，splinter group中放入點(diǎn)3。第4步，重復(fù)第2步的工作，splinter group中放入點(diǎn)4。第5步，沒(méi)有在old party中的點(diǎn)放入了splinter group中且達(dá)到終止條件（k=2），程

62、序終止。如果沒(méi)有到終止條件，因該從分裂好的簇中選一個(gè)直徑最大的簇繼續(xù)分裂。,DIANA算法例子(續(xù)),,,81,下面給出一個(gè)樣本事務(wù)數(shù)據(jù)庫(kù)（見(jiàn)表），對(duì)它實(shí)施DBSCAN算法。 根據(jù)所給的數(shù)據(jù)通過(guò)對(duì)其進(jìn)行DBSCAN算法，以下為算法的步驟（設(shè)n=12，用戶輸入ε=1，MinPts=4）,DBSCAN算法舉例,,,,,,,,,,,,,,,,,樣本事務(wù)數(shù)據(jù)庫(kù),DBSCAN算法舉例（續(xù)）,,,,,,,,,,,,,,,,,DBSCAN算法舉例（

63、續(xù)）,,,,,,,,,,,,,,,,,聚出的類為{1，3，4，5，9，11，12}，{2，6，7，8，10}。具體過(guò)程如下第1步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)1，由于在以它為圓心的，以1為半徑的圓內(nèi)包含2個(gè)點(diǎn)（小于4），因此它不是核心點(diǎn)，選擇下一個(gè)點(diǎn)。第2步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)2，由于在以它為圓心的，以1為半徑的圓內(nèi)包含2個(gè)點(diǎn)，因此它不是核心點(diǎn)，選擇下一個(gè)點(diǎn)。第3步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)3，由于在以它為圓心的，以1為半徑的圓內(nèi)包含3個(gè)點(diǎn)，因此

64、它不是核心點(diǎn)，選擇下一個(gè)點(diǎn)。第4步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)4，由于在以它為圓心的，以1為半徑的圓內(nèi)包含5個(gè)點(diǎn)，因此它是核心點(diǎn)，尋找從它出發(fā)可達(dá)的點(diǎn)（直接可達(dá)4個(gè)，間接可達(dá)3個(gè)），聚出的新類{1，3，4，5，9，10，12}，選擇下一個(gè)點(diǎn)。第5步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)5，已經(jīng)在簇1中，選擇下一個(gè)點(diǎn)。第6步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)6，由于在以它為圓心的，以1為半徑的圓內(nèi)包含3個(gè)點(diǎn)，因此它不是核心點(diǎn)，選擇下一個(gè)點(diǎn)。,DBSCAN算法舉例（續(xù)）,,

65、,,,,,,,,,,,,,,,第7步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)7，由于在以它為圓心的，以1為半徑的圓內(nèi)包含5個(gè)點(diǎn)，因此它是核心點(diǎn)，尋找從它出發(fā)可達(dá)的點(diǎn)，聚出的新類{2，6，7，8，11}，選擇下一個(gè)點(diǎn)。 第8步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)8，已經(jīng)在簇2中，選擇下一個(gè)點(diǎn)。第9步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)9，已經(jīng)在簇1中，選擇下一個(gè)點(diǎn)。第10步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)10，已經(jīng)在簇1中，選擇下一個(gè)點(diǎn)。第11步，在數(shù)據(jù)庫(kù)中選擇一點(diǎn)11，已經(jīng)在簇2中，選擇下一