【正文】 Kmeans 決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 基本概念 ? 發(fā)現(xiàn)特征規(guī)則 ：特征規(guī)則是刻劃某個(gè)概念的特征的斷言，它相當(dāng)于分類(lèi)規(guī)則的逆命題。回歸可以看作一種分類(lèi)，區(qū)別是分類(lèi)的類(lèi)標(biāo)簽值是離散的，而回歸是連續(xù)的。 數(shù)據(jù)庫(kù)統(tǒng)計(jì) 機(jī)器學(xué)習(xí) 證據(jù)理論 可視化技術(shù) 決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 基本概念 ? 解釋與評(píng)價(jià)階段： ? 結(jié)果篩選 ：過(guò)濾 (移去 )不感興趣的或顯而易見(jiàn)的模式?？罩党霈F(xiàn)的主要原因 ： ? 在信息收集時(shí)忽略了一些認(rèn)為不重要的數(shù)據(jù)或信息提供者不愿意提供，而這些數(shù)據(jù)對(duì)以后的信息處理可能是有用的； ? 某些屬性值未知； ? 數(shù)據(jù)模型的限制。 CC ?? )},(,),(),(),{(P}{cP 210i ikiiiiiiiCciCc iii cccccccc ??? ???? ??? ),2,1( nkUxk ??? )),2,1()(,[ 1 iijij kjcc ???PA決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 連續(xù)屬性離散化 離散化方法 典型的有等區(qū)間方法、等信息量方法、基于信息熵的方法、Holte的 1R離散化方法、統(tǒng)計(jì)試驗(yàn)方法、超平面搜索方法以及用戶(hù)自定義區(qū)間等。 ? ?? ?? ?? ??? 21 1121krmkmrk kkjlkljnnnE0?ljE ?ljE2?決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 關(guān)聯(lián)規(guī)則發(fā)現(xiàn) (Apriori算法 ) ? The Apriori method: ? Proposed by Agrawal Srikant 1994 ? Major idea: ? A subset of a frequent itemset must be frequent ?., if {beer, diaper, nuts} is frequent, {beer, diaper} must be. Anyone is infrequent, its superset cannot be! ? A powerful, scalable candidate set pruning technique: ?It reduces candidate kitemsets dramatically (for k 2) 決策理論與方法 智能決策理論與方法 知識(shí)發(fā)現(xiàn) — 關(guān)聯(lián)規(guī)則發(fā)現(xiàn) (Apriori算法 ) ? 關(guān)聯(lián)規(guī)則的例子 For rule A ? C: support = support({A ?C}) = 50% confidence = support({A ? C})/support({A}) = % The Apriori principle: Any subset of a frequent itemset must be frequent. T r a n sa ctio n I D It e m s B o u g h t2023 A ,B ,C1000 A ,C4000 A ,D5000 B ,E ,FF r e q u e n t I te m s e t S u p p o r t{ A } 75%{ B } 50%{ C} 50%{ 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}。 ? 在實(shí)際應(yīng)用時(shí)常分析兩個(gè)樣品之間的相對(duì)距離，這時(shí)需要對(duì)樣品數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理，然后用標(biāo)準(zhǔn)化數(shù)據(jù)計(jì)算距離。 一般可以以 G(m)中各類(lèi)的重心 作為新的聚點(diǎn)。設(shè) X1, X2, …, X n是 U關(guān)于 R的所有等價(jià)類(lèi)，則有： ?Xi∩Xj=φ（ i≠j， i, j=1,2,…,n ） ?X1∪ X2∪ … ∪ Xn=U ? 劃分 ： 所有等價(jià)類(lèi)的集合稱(chēng)為 U關(guān)于 R的商集，它構(gòu)成了 U的一個(gè)劃分，記為 U/R。則稱(chēng) IND(B)為 不可分辨關(guān)系 (?)。邊界域中的元素根據(jù)可用知識(shí)沒(méi)有確定的分類(lèi)，即它既不能劃分到 X中也不能劃分到 X的補(bǔ)集中。 ?F的近似質(zhì)量：近似質(zhì)量給出了能正確分類(lèi)的百分?jǐn)?shù)。如果知識(shí) D的所有初等范疇都能用知識(shí) C的某些初等范疇來(lái)定義，則稱(chēng)知識(shí) D可由知識(shí) C推得，也稱(chēng) D完全依賴(lài)于 C，記為 C?D。 ?實(shí)際：確定對(duì)象所屬的類(lèi)只需其中幾個(gè)屬性甚至一個(gè)屬性，而不需要知道對(duì)象所有的屬性，這與人類(lèi)對(duì)實(shí)體的識(shí)別是一致的。 ? 設(shè)信息系統(tǒng) I=U,C∪ D,V,f，對(duì)于 C的非空子集 B，其重要度為 ? 若 B的重要度為０，則表示 B可以從 C中移去，也即 B是冗余的。 ? 什么是值約簡(jiǎn)？ ?值約簡(jiǎn)就是移去對(duì)分類(lèi)沒(méi)有實(shí)際價(jià)值的冗余的屬性值?；趯傩砸蕾?lài)度的屬性約簡(jiǎn)算法就是將 γp(D|B)作為尋找最小屬性約簡(jiǎn)的啟發(fā)式信息。 ? C的 D約簡(jiǎn)是不含任何冗余知識(shí)且與 C具有相同分類(lèi)能力的子集（用知識(shí) C將對(duì)象劃分到知識(shí) D的初等范疇中的能力）。 DUCU /~/ ? )( ))(()( UCard DPOSCardDk CC ?? ?粗糙集理論 (Rough Set Theory) 智能決策方法 粗糙集理論的經(jīng)典模型 —— 知識(shí)依賴(lài) ? R1={T1}： U/R1={{p2, p3, p5}， {p1, p4, p6}}； ? R2={T2,T1}： U/R2={{p1, p4, p6}, {p2, p5}, {p3}}； ? R3={T1, T2, T3}： U/R3=({p1}, {p3}, {p6}, {p2, p5},{p4}}。 ? 分類(lèi) F={E}： U/F={{p1, p2, p3, p6}, {p4, p5}} ? X1={p1, p2, p3, p6}是 R粗糙集， X1的 R下近似是 {p1, p3, p6}， R上近似是 {p1, p2, p3, p5, p6}， R精度為 ； R粗糙度為 ； ? X2={p4, p5}也是 R粗糙集， X2的 R下近似是{p4}， X2的 R上近似是 {p2, p4, p5}， R精度為 ； R粗糙度為 ； ? p2隸屬于 X1的隸屬度為 。αR(X)=1為 精確集， 0≤αR(X)1為粗糙集。 ?每個(gè)粗糙集 X都可用兩個(gè)與之相關(guān)的精確集近似表示即 X的上近似和下近似，他們是粗糙集理論的兩個(gè)最基本運(yùn)算。粗糙集理論反映了人們以不完全信息或知識(shí)去處理一些不可分辨現(xiàn)象的能力，或依據(jù)觀察、度量到某些不精確的結(jié)果而進(jìn)行分類(lèi)數(shù)據(jù)的能力。 決策理論與方法 智能決策理論與方法 智能決策理論與方法 智能決策理論的形成背景 知識(shí)發(fā)現(xiàn) 粗糙集理論 機(jī)器學(xué)習(xí) 決策理論與方法 智能決策理論與方法 智能決策方法 預(yù)備知識(shí) —— 相關(guān)名詞解釋 ?論域 ：研究對(duì)象的全體成員構(gòu)成的集合，一般用字母 U表示；若 X?U，則稱(chēng) X是 U的 子集 ?隸屬度 ：描述一個(gè)對(duì)象 x與某個(gè)子集 X之間的隸屬程度，一般用符號(hào) ??表示， ?若 x?X, 則 ?=1。聚點(diǎn)可由用戶(hù)根據(jù)經(jīng)驗(yàn)選擇，也可將全部樣品人為地或隨機(jī)地分成 k類(lèi)，以每類(lèi)的重心作為聚點(diǎn)。 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。 (2)等信息量離散化方法 等信息量分割首先將測(cè)量值進(jìn)行排序，然后將屬性值域分成k個(gè)區(qū)間，每個(gè)區(qū)間包含相同數(shù)量的測(cè)量值。設(shè) 是 上的分割點(diǎn)集合，記為 其中