【正文】 Kmeans 決策理論與方法 智能決策理論與方法 知識發(fā)現(xiàn) — 基本概念 ? 發(fā)現(xiàn)特征規(guī)則 ：特征規(guī)則是刻劃某個概念的特征的斷言，它相當于分類規(guī)則的逆命題?；貧w可以看作一種分類，區(qū)別是分類的類標簽值是離散的，而回歸是連續(xù)的。 數(shù)據(jù)庫統(tǒng)計 機器學習 證據(jù)理論 可視化技術(shù) 決策理論與方法 智能決策理論與方法 知識發(fā)現(xiàn) — 基本概念 ? 解釋與評價階段： ? 結(jié)果篩選 ：過濾 (移去 )不感興趣的或顯而易見的模式?？罩党霈F(xiàn)的主要原因 ： ? 在信息收集時忽略了一些認為不重要的數(shù)據(jù)或信息提供者不愿意提供，而這些數(shù)據(jù)對以后的信息處理可能是有用的； ? 某些屬性值未知； ? 數(shù)據(jù)模型的限制。 CC ?? )},(,),(),(),{(P}{cP 210i ikiiiiiiiCciCc iii cccccccc ??? ???? ??? ),2,1( nkUxk ??? )),2,1()(,[ 1 iijij kjcc ???PA決策理論與方法 智能決策理論與方法 知識發(fā)現(xiàn) — 連續(xù)屬性離散化 離散化方法 典型的有等區(qū)間方法、等信息量方法、基于信息熵的方法、Holte的 1R離散化方法、統(tǒng)計試驗方法、超平面搜索方法以及用戶自定義區(qū)間等。 ? ?? ?? ?? ??? 21 1121krmkmrk kkjlkljnnnE0?ljE ?ljE2?決策理論與方法 智能決策理論與方法 知識發(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) 決策理論與方法 智能決策理論與方法 知識發(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% 決策理論與方法 智能決策理論與方法 知識發(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. 決策理論與方法 智能決策理論與方法 知識發(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) 決策理論與方法 智能決策理論與方法 知識發(fā)現(xiàn) — 關(guān)聯(lián)規(guī)則發(fā)現(xiàn) (Apriori算法 ) ? Pseudocode（正式代碼見附件 1） Ck: Candidate itemset of size k Lk : frequent itemset of size k L1 = {frequent items}。 ? 在實際應用時常分析兩個樣品之間的相對距離，這時需要對樣品數(shù)據(jù)進行標準化處理，然后用標準化數(shù)據(jù)計算距離。 一般可以以 G(m)中各類的重心 作為新的聚點。設 X1, X2, …, X n是 U關(guān)于 R的所有等價類，則有： ?Xi∩Xj=φ（ i≠j， i, j=1,2,…,n ） ?X1∪ X2∪ … ∪ Xn=U ? 劃分 ： 所有等價類的集合稱為 U關(guān)于 R的商集，它構(gòu)成了 U的一個劃分，記為 U/R。則稱 IND(B)為 不可分辨關(guān)系 (?)。邊界域中的元素根據(jù)可用知識沒有確定的分類，即它既不能劃分到 X中也不能劃分到 X的補集中。 ?F的近似質(zhì)量：近似質(zhì)量給出了能正確分類的百分數(shù)。如果知識 D的所有初等范疇都能用知識 C的某些初等范疇來定義，則稱知識 D可由知識 C推得，也稱 D完全依賴于 C，記為 C?D。 ?實際：確定對象所屬的類只需其中幾個屬性甚至一個屬性，而不需要知道對象所有的屬性，這與人類對實體的識別是一致的。 ? 設信息系統(tǒng) I=U,C∪ D,V,f，對于 C的非空子集 B，其重要度為 ? 若 B的重要度為０，則表示 B可以從 C中移去，也即 B是冗余的。 ? 什么是值約簡？ ?值約簡就是移去對分類沒有實際價值的冗余的屬性值?；趯傩砸蕾嚩鹊膶傩约s簡算法就是將 γp(D|B)作為尋找最小屬性約簡的啟發(fā)式信息。 ? C的 D約簡是不含任何冗余知識且與 C具有相同分類能力的子集（用知識 C將對象劃分到知識 D的初等范疇中的能力）。 DUCU /~/ ? )( ))(()( UCard DPOSCardDk CC ?? ?粗糙集理論 (Rough Set Theory) 智能決策方法 粗糙集理論的經(jīng)典模型 —— 知識依賴 ? 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}}。 ? 分類 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為粗糙集。 ?每個粗糙集 X都可用兩個與之相關(guān)的精確集近似表示即 X的上近似和下近似，他們是粗糙集理論的兩個最基本運算。粗糙集理論反映了人們以不完全信息或知識去處理一些不可分辨現(xiàn)象的能力，或依據(jù)觀察、度量到某些不精確的結(jié)果而進行分類數(shù)據(jù)的能力。 決策理論與方法 智能決策理論與方法 智能決策理論與方法 智能決策理論的形成背景 知識發(fā)現(xiàn) 粗糙集理論 機器學習 決策理論與方法 智能決策理論與方法 智能決策方法 預備知識 —— 相關(guān)名詞解釋 ?論域 ：研究對象的全體成員構(gòu)成的集合，一般用字母 U表示；若 X?U，則稱 X是 U的 子集 ?隸屬度 ：描述一個對象 x與某個子集 X之間的隸屬程度，一般用符號 ??表示， ?若 x?X, 則 ?=1。聚點可由用戶根據(jù)經(jīng)驗選擇，也可將全部樣品人為地或隨機地分成 k類，以每類的重心作為聚點。 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)等信息量離散化方法 等信息量分割首先將測量值進行排序，然后將屬性值域分成k個區(qū)間，每個區(qū)間包含相同數(shù)量的測量值。設 是 上的分割點集合，記為 其中