【文章內(nèi)容簡(jiǎn)介】 { A ,C} 50%Min. support 50% Min. confidence 50% 決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 關(guān)聯(lián)規(guī)則發(fā)現(xiàn) (Apriori算法 ) ? Procedure ?Find the frequent itemsets: the sets of items that have minimum support (Apriori) ?A subset of a frequent itemset must also be a frequent itemset, ., if {A ? B} is a frequent itemset, both {A} and {B} should be a frequent itemset ?Iteratively find frequent itemsets with cardinality from 1 to k (kitemset) ?Use the frequent itemsets to generate association rules. 決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 關(guān)聯(lián)規(guī)則發(fā)現(xiàn) (Apriori算法 ) ? Algorithm ? Join Step Ck is generated by joining Lk1with itself ? Prune Step Any (k1)itemset that is not frequent cannot be a subset of a frequent kitemset, hence should be removed. (Ck: Candidate itemset of size k) (Lk : frequent itemset of size k) 決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 關(guān)聯(lián)規(guī)則發(fā)現(xiàn) (Apriori算法 ) ? Pseudocode（正式代碼見(jiàn)附件 1） Ck: Candidate itemset of size k Lk : frequent itemset of size k L1 = {frequent items}。 for (k = 1。 Lk !=?。 k++) do begin Ck+1 = candidates generated from Lk。 for each transaction t in database do increment the count of all candidates in Ck+1 that are contained in t Lk+1 = candidates in Ck+1 with min_support end return ?k Lk。 決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 關(guān)聯(lián)規(guī)則發(fā)現(xiàn) (Apriori算法 ) T ID Ite m s100 1 3 4200 2 3 5300 1 2 3 5400 2 5Database D ite m s e t s u p .{ 1 } 2{ 2 } 3{ 3 } 3{ 4 } 1{ 5 } 3i te m s e t s u p .{ 1 } 2{ 2 } 3{ 3 } 3{ 5 } 3Scan D C1 L1 item set{1 2}{1 3}{1 5}{2 3}{2 5}{3 5}ite m s et s up{ 1 2} 1{ 1 3} 2{ 1 5} 1{ 2 3} 2{ 2 5} 3{ 3 5} 2ite m s e t s u p{ 1 3 } 2{ 2 3 } 2{ 2 5 } 3{ 3 5 } 2L2 C2 C2 Scan D C3 L3 item set{2 3 5}Scan D ite m s e t s u p{ 2 3 5 } 2決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 聚類 (Kmeans算法 ) ? 聚類分析是把研究對(duì)象按照一定的規(guī)則分成若干類別，并使類之間的差別盡可能地大，類內(nèi)的差別盡可能地小，換句話說(shuō)，使類間的相似性最小、而類內(nèi)的相似性最大。 ? 聚類方法的核心問(wèn)題是樣品間的相似性度量，通常用距離來(lái)度量。 決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 聚類 (Kmeans算法 ) 聚類分析中的常用距離 (1)歐氏 (Euclidean)距離 (2)絕對(duì)距離 (3)Minkowski距離 ? 顯然當(dāng) m=1時(shí)就是絕對(duì)距離， m=2時(shí)就是歐氏距離。 ? 在實(shí)際應(yīng)用時(shí)常分析兩個(gè)樣品之間的相對(duì)距離，這時(shí)需要對(duì)樣品數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理，然后用標(biāo)準(zhǔn)化數(shù)據(jù)計(jì)算距離。 2112 ])([),( ????pkjkikji xxxxd ????pkjkikji xxxxd1||),( )1(]||[),( 11??? ??mxxxxd mpkmjkikji決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 聚類 (Kmeans算法 ) ? 對(duì)于給定的 n個(gè)樣品，先粗略地形成 k(k≤n)個(gè)分割，使得每個(gè)分割對(duì)應(yīng)一個(gè)類、每個(gè)類至少有一個(gè)樣品并且每個(gè)樣品精確地屬于一個(gè)類，然后按照某種原則進(jìn)行修正，直至分類比較合理為止。具體步驟如下： (1)聚點(diǎn)的選擇 ：聚點(diǎn)是一批有代表性的樣品，它的選擇決定了初始分類。首先確定分類數(shù) k，然后選擇 k個(gè)有代表性的樣品作為每個(gè)類的初始元素即聚點(diǎn)。聚點(diǎn)可由用戶根據(jù)經(jīng)驗(yàn)選擇，也可將全部樣品人為地或隨機(jī)地分成 k類，以每類的重心作為聚點(diǎn)。 決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 聚類 (Kmeans算法 ) 聚點(diǎn)的最小最大原則選擇法： ①設(shè)將 n個(gè)樣品分成 k類，先選擇所有樣品中相距最遠(yuǎn)的兩個(gè)樣品 為前兩個(gè)聚點(diǎn)，因此有 21 , ii xx )m ax(),( 21 ijii dxxd ?②設(shè)已經(jīng)找到了 l個(gè) (2≤ l＜ k)聚點(diǎn)，則第 l+1個(gè)聚點(diǎn) 的選擇方法是使得 與前 l個(gè)聚點(diǎn)的距離最小者等于所有其余的與前 l個(gè)聚點(diǎn)的較小距離的最大者，直至選定 k個(gè)聚點(diǎn)，即 將所獲得的 k個(gè)聚點(diǎn)的集合記為 ),,2,1),2,1),(ma x( mi n(),2,1),(mi n(211rijiiiiijnjlrxxdlrxxdrrl???????????1?lix1?lix },{ )0()0(2)0(1)0( kxxxL ??決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 聚類 (Kmeans算法 ) (2)初始聚類 有了聚點(diǎn)集合后，可根據(jù)下列最靠近原則實(shí)現(xiàn)初始分類： 若對(duì)于某樣品 x出現(xiàn) ，則 x任意歸于 Gi(0) 或 Gj(0) 類。這樣就得到了樣品空間的初始分類： kiijkjxxdxxdxG jii ,2,1},。,2,1),(),(:{ )0()0()0( ?? ????? ),(),( )0()0( ji xxdxxd ? },{ )0()0(2)0(1)0( kGGGG ??決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 聚類 (Kmeans算法 ) (3)迭代過(guò)程 設(shè)聚類形成的一個(gè)分類為 則可從 G(m)出發(fā)計(jì)算新的聚點(diǎn)集合 L(m+1)。 一般可以以 G(m)中各類的重心 作為新的聚點(diǎn)。其中 根據(jù)新的聚點(diǎn)集，對(duì)樣品空間重新聚類，形成新的分類： 其中 },{ )1()1(2)1(1)1( ???? ? mkmmm xxxL ?kixGcardxmil Gxlmimi ,2,1,)(1)()()1( ??? ???0},{ )1()1(2)1(1)1( ?? ???? mGGGG mkmmm ? kiijkjxxdxxdx mjmimi ,2,1},。,2,1),(),(:{ )1()1()1( ?? ????? ???0},{ )()(2)(1)( ?? mGGGG mkmmm ?決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 聚類 (Kmeans算法 ) (4)迭代終止 隨著 m的增大，分類趨于穩(wěn)定。當(dāng) G(m+1)=G(m)或在一定的精度范圍內(nèi)近似有 G(m+1)=G(m)，則遞推過(guò)程結(jié)束。 決策理論與方法 智能決策理論與方法 智能決策理論與方法 智能決策理論的形成背景 知識(shí)發(fā)現(xiàn) 粗糙集理論 機(jī)器學(xué)習(xí) 決策理論與方法 智能決策理論與方法 智能決策方法 預(yù)備知識(shí) —— 相關(guān)名詞解釋 ?論域 ：研究對(duì)象的全體成員構(gòu)成的集合，一般用字母 U表示；若 X?U，則稱 X是 U的 子集 ?隸屬度 ：描述一個(gè)對(duì)象 x與某個(gè)子集 X之間的隸屬程度，一般用符號(hào) ??表示， ?若 x?X, 則 ?=1。 ?若 ,則 ?=0。 ?其他： 0?1。(?常用某個(gè)函數(shù)加以描述，稱為隸屬度函數(shù) ) Xx?高斯函數(shù) 粗糙集理論 (Rough Set Theory) 智能決策方法 預(yù)備知識(shí) —— 相關(guān)名詞解釋 ? 等價(jià)關(guān)系 ： R是 U上的一個(gè)等價(jià)關(guān)系，當(dāng)且僅當(dāng) ?對(duì)于任意 x?U，均有 x R x（自反性） ?對(duì)于任意 x, y?U， x R y?y R x （對(duì)稱性） ?對(duì)于任意 x, y, z?U， x R y ∧ y R z→ x R z（傳遞性） ? 等價(jià)類 ：若 R是 U上的一個(gè)等價(jià)關(guān)系，對(duì)于任意 x?U，稱集合[x]={y| y R x, y ?U}為 U關(guān)于 R的一個(gè)等價(jià)類，記為 [x]R。設(shè) X1,