【正文】 ⑹for each test_attribute中的已知值ai 由節(jié)點N長出一個條件為test_attribute=ai的分枝。它的目的是使得屬于同一類別的個體之間的距離盡可能的小而不同類別上的個體間的距離盡可能的大。 ⑻if si 為空 then 加上一個樹葉，標記為samples中最普通的類。,知識發(fā)現(xiàn)的定義,數(shù)據(jù)庫中的知識發(fā)現(xiàn)是識別數(shù)據(jù)中有效的（Valid）、新穎的（Novel）、潛在有用的（Potentially Useful）和最終可被理解（Ultimately Understandable）的模式（Pattern）的非平凡過程,KDD：Knowledge Discovery in Database,數(shù)據(jù)挖掘的定義,數(shù)據(jù)挖掘(Data Mining)是KDD過程的一個步驟，它是在現(xiàn)實可接受的計算效率限制下，應用數(shù)據(jù)分析和知識發(fā)現(xiàn)算法，在數(shù)據(jù)的基礎上，對模式(Pattern)的特定枚舉,數(shù)據(jù)挖掘的任務與方法,關聯(lián)分析（Associations）,目的和含義 目的：發(fā)現(xiàn)數(shù)據(jù)庫中數(shù)據(jù)間的相互關聯(lián) 含義：給定一組數(shù)據(jù)項（例如：商品號）和一個交易集合（例如交易記錄），通過分析記錄集合，推導出數(shù)據(jù)項間的相關性（例如：在交易活動中商品間的相關性） 基本形式 給定： 一組事務集 每一個事務中包含若干個數(shù)據(jù)項 挖掘: 各個數(shù)據(jù)項之間的關聯(lián) 例如, 98% 的顧客在購買電動剃須刀的同時會購買一些電池,關聯(lián)規(guī)則興趣度的度量值：支持度,推導出的數(shù)據(jù)間的相關性稱為規(guī)則（或模式），對規(guī)則興趣度的描述采用支持度、置信度概念 支持度（Support）：在關聯(lián)分析中表示滿足規(guī)則的記錄數(shù)與總記錄數(shù)的比，它表明了規(guī)則的模式在數(shù)據(jù)庫中出現(xiàn)的頻度對于規(guī)則： X ? Y，則其支持度表示為：,購買商品Y的交易,同時購買商品X和Y的交易,購買商品X的交易,關聯(lián)規(guī)則興趣度的度量值：置信度,置信度（Confidence），在關聯(lián)分析中表示為滿足規(guī)則的記錄數(shù)與出現(xiàn)被分析數(shù)據(jù)項的記錄數(shù)之比 對于規(guī)則： X ? Y，則其置信度表示為： 最小支持度和最小置信度 用戶（分析員）不關心可信程度太低的規(guī)則，因而用戶需要輸入兩個參數(shù)：最小支持度和最小置信度,支持度和置信度舉例,零售商場銷售分析 數(shù)據(jù)項為商品，記錄集合為交易記錄集合 規(guī)則為：“購買商品X的顧客，同時購買商品Y”，即X ? Y； 設最小支持度為0 .3；最小置信度也為0.3 分析結(jié)果：,關聯(lián)分析的基本步驟,術語 設I={i1, i2, …im}是項的集合(itemset)，包含k個項的稱為k項集 設D是事務的集合，其中每個事務T是項的集合，T ? I 設A是一個項集，事務T包含A當且僅當A ? T 項集的出現(xiàn)頻率：D中包含項集的事務數(shù) 頻繁項集：如果項集的出現(xiàn)頻率大于或等于最小支持度min_sup與D中事務總數(shù)的乘積；頻繁k項集記作Lk 關聯(lián)規(guī)則A?B：其中A?I，B?I，并且A?B=? 強規(guī)則：同時滿足最小支持度和最小置信度的規(guī)則,關聯(lián)分析的例子,Min. support 50% Min. confidence 50%,For rule A ? C: support = support({A}?{C}) = 50% confidence = support({A}?{C})/support({A}) = 66.6%,For rule C ? A: support = support({A}?{C}) = 50% confidence = support({A}?{C})/support({C}) = 100%,關聯(lián)分析的基本步驟,通常，關聯(lián)分析的過程分為以下兩步： 發(fā)現(xiàn)頻繁項集(frequent itemset)，這些項集出現(xiàn)的頻率至少和預定義的最小支持度一樣 由頻繁項集來產(chǎn)生強關聯(lián)規(guī)則：這些規(guī)則必須滿足最小支持度和最小置信度,Apriori算法,Apriori性質(zhì) 先驗（ Apriori ）法則：一個頻繁項集的任何非空子集肯定也是一個頻繁項集 例如{A，B}為高頻項集，那么其子集{A}、{B}一定都為高頻項集 反單調(diào)：一個集合如果不能通過測試，則它的任何超集也不能通過測試 反復尋找高頻項集(從1到K階),Apriori算法,如何由Lk1產(chǎn)生Lk ？ 連接步：對K1階頻繁項集Lk1做SelfJoin操作，形成K階頻繁項集的候選集Ck 具體算法如下： insert into Ck select p.item1, p.item2, …, p.itemk1, q.itemk1 from Lk1 p, Lk1 q where p.item1=q.item1 ,…, p.itemk2=q.itemk2 , p.itemk1 q.itemk1,Apriori算法,剪枝步：任何K1階非頻繁項集，則其不可能為K階頻繁項集的子集 具體算法如下： for all item sets c in Ck do for all (k1)subsets s of c do if (s is not in Lk1) then delete c from Ck,Apriori算法,示例 3階高頻項目集：L3={abc, abd, acd, ace, bcd} 連接步 Selfjoining: L3*L3 abc，abd ? abcd acd, ace ? acde 剪枝步 acde 移出，因為 ade不包含在 L3中 4階候選集：C4={abcd},Apriori算法,數(shù)據(jù)庫事務數(shù)據(jù)D,最小支持度min_sup=2,Apriori算法,掃描D，對每 個候選記數(shù),比較sup.與 min_sup,C1,L1,Apriori算法,由L1產(chǎn)生C2,掃描D，對每 個候選記數(shù),C2,C2,Apriori算法,比較sup.與 min_sup,L2,由L2產(chǎn)生C3,C3,Apriori算法,使用Apriori 性質(zhì)剪枝,C3,掃描D，對每 個候選記數(shù),C3,比較sup.與 min_sup,L3,由頻繁項集來產(chǎn)生關聯(lián)規(guī)則,步驟 對于每個頻繁項集l，產(chǎn)生l的所有非空子集 對于L的每個非空子集s，如果: 則輸出規(guī)則“s ? (ls)”，其中min_conf是最小置信度閾值 由于規(guī)則由頻繁項集產(chǎn)生，每個規(guī)則自動滿足最小支持度,由頻繁項集來產(chǎn)生關聯(lián)規(guī)則,示例 l = {I1, I2, I5} l的非空子集{I1},{I2},{I5},{I1, I2},{I1, I5},{I2, I5} I1 ? I2 ? I5, c = 2/6 = 33% I2 ? I1 ? I5, c = 2/7 = 29% I5 ? I1 ? I2, c = 2/2 = 100% I1 ? I2 ? I5, c = 2/4 = 50% I1 ? I5 ? I2, c = 2/2 = 100% I2 ? I5 ? I1, c = 2/2 = 100% 若min_conf=70%，則輸出第3，5，6條規(guī)則,分類分析（Classifiers）,含義 有一個記錄集合和一組標記，標記用以標識記錄的類別 先為每個記錄賦予一個標記（按標記對記錄分類） 對同類記錄的特征進行描述 顯式描述：例如，一組規(guī)則定義 隱式描述：例如，一個數(shù)學模型或公式 分類具有極其廣泛的應用 分類常用于預測 醫(yī)療診斷、性能預測、選擇購物、信譽證實等,分類分析的兩個步驟,構(gòu)建模型:對預先確定的類別給出相應的描述 先假設一個元組（或樣本）集合中的每一個元組（或樣本）屬于預先定義的某一個類別，由一個類標號屬性(class label attribute)來確定 這些元組（或樣本）的集合稱為訓練集，用于構(gòu)建模型；由于提供了每個訓練樣本的類標號，稱作有指導的學習 最終的模型用決策樹、分類規(guī)則或者數(shù)學公式等來表示 模型應用: 對未知的數(shù)據(jù)對象進行分類,分類分析第一步：構(gòu)建模型,分類分析第二步：模型應用,分類分析舉例,對信用卡持卡人的信譽進行分類分析 記錄集合： 持卡人的記錄集 一組標記：