【正文】 它的目的是使得屬于同一類別的個(gè)體之間的距離盡可能的小而不同類別上的個(gè)體間的距離盡可能的大?？梢杂脤傩訟將S劃分為v個(gè)子集{s1, s2, … sv}，其中si中樣本在屬性A上具有值ai。,利用決策樹進(jìn)行數(shù)據(jù)分類：ID3,信息增益(information gain) 設(shè)S是s個(gè)樣本的集合，假定類標(biāo)號(hào)屬性有m個(gè)不同值，定義m個(gè)不同類Ci，設(shè)si是Ci中樣本數(shù)。 ⑻if si 為空 then 加上一個(gè)樹葉，標(biāo)記為samples中最普通的類。 ⑹for each test_attribute中的已知值ai 由節(jié)點(diǎn)N長(zhǎng)出一個(gè)條件為test_attribute=ai的分枝。 ⑷選擇attribute_list中具有最高信息增益的屬性test_attribute。 ⑵if samples都在同一個(gè)類C then 返回N作為葉節(jié)點(diǎn)，以類C標(biāo)記。,知識(shí)發(fā)現(xiàn)的定義,數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)是識(shí)別數(shù)據(jù)中有效的（Valid）、新穎的（Novel）、潛在有用的（Potentially Useful）和最終可被理解（Ultimately Understandable）的模式（Pattern）的非平凡過程,KDD：Knowledge Discovery in Database,數(shù)據(jù)挖掘的定義,數(shù)據(jù)挖掘(Data Mining)是KDD過程的一個(gè)步驟，它是在現(xiàn)實(shí)可接受的計(jì)算效率限制下，應(yīng)用數(shù)據(jù)分析和知識(shí)發(fā)現(xiàn)算法，在數(shù)據(jù)的基礎(chǔ)上，對(duì)模式(Pattern)的特定枚舉,數(shù)據(jù)挖掘的任務(wù)與方法,關(guān)聯(lián)分析（Associations）,目的和含義 目的：發(fā)現(xiàn)數(shù)據(jù)庫(kù)中數(shù)據(jù)間的相互關(guān)聯(lián) 含義：給定一組數(shù)據(jù)項(xiàng)（例如：商品號(hào)）和一個(gè)交易集合（例如交易記錄），通過分析記錄集合，推導(dǎo)出數(shù)據(jù)項(xiàng)間的相關(guān)性（例如：在交易活動(dòng)中商品間的相關(guān)性） 基本形式 給定： 一組事務(wù)集 每一個(gè)事務(wù)中包含若干個(gè)數(shù)據(jù)項(xiàng) 挖掘: 各個(gè)數(shù)據(jù)項(xiàng)之間的關(guān)聯(lián) 例如, 98% 的顧客在購(gòu)買電動(dòng)剃須刀的同時(shí)會(huì)購(gòu)買一些電池,關(guān)聯(lián)規(guī)則興趣度的度量值：支持度,推導(dǎo)出的數(shù)據(jù)間的相關(guān)性稱為規(guī)則（或模式），對(duì)規(guī)則興趣度的描述采用支持度、置信度概念 支持度（Support）：在關(guān)聯(lián)分析中表示滿足規(guī)則的記錄數(shù)與總記錄數(shù)的比，它表明了規(guī)則的模式在數(shù)據(jù)庫(kù)中出現(xiàn)的頻度對(duì)于規(guī)則： X ? Y，則其支持度表示為：,購(gòu)買商品Y的交易,同時(shí)購(gòu)買商品X和Y的交易,購(gòu)買商品X的交易,關(guān)聯(lián)規(guī)則興趣度的度量值：置信度,置信度（Confidence），在關(guān)聯(lián)分析中表示為滿足規(guī)則的記錄數(shù)與出現(xiàn)被分析數(shù)據(jù)項(xiàng)的記錄數(shù)之比 對(duì)于規(guī)則： X ? Y，則其置信度表示為： 最小支持度和最小置信度 用戶（分析員）不關(guān)心可信程度太低的規(guī)則，因而用戶需要輸入兩個(gè)參數(shù)：最小支持度和最小置信度,支持度和置信度舉例,零售商場(chǎng)銷售分析 數(shù)據(jù)項(xiàng)為商品，記錄集合為交易記錄集合 規(guī)則為：“購(gòu)買商品X的顧客，同時(shí)購(gòu)買商品Y”，即X ? Y； 設(shè)最小支持度為0 .3；最小置信度也為0.3 分析結(jié)果：,關(guān)聯(lián)分析的基本步驟,術(shù)語(yǔ) 設(shè)I={i1, i2, …im}是項(xiàng)的集合(itemset)，包含k個(gè)項(xiàng)的稱為k項(xiàng)集 設(shè)D是事務(wù)的集合，其中每個(gè)事務(wù)T是項(xiàng)的集合，T ? I 設(shè)A是一個(gè)項(xiàng)集，事務(wù)T包含A當(dāng)且僅當(dāng)A ? T 項(xiàng)集的出現(xiàn)頻率：D中包含項(xiàng)集的事務(wù)數(shù) 頻繁項(xiàng)集：如果項(xiàng)集的出現(xiàn)頻率大于或等于最小支持度min_sup與D中事務(wù)總數(shù)的乘積；頻繁k項(xiàng)集記作Lk 關(guān)聯(lián)規(guī)則A?B：其中A?I，B?I，并且A?B=? 強(qiáng)規(guī)則：同時(shí)滿足最小支持度和最小置信度的規(guī)則,關(guān)聯(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%,關(guān)聯(lián)分析的基本步驟,通常，關(guān)聯(lián)分析的過程分為以下兩步： 發(fā)現(xiàn)頻繁項(xiàng)集(frequent itemset)，這些項(xiàng)集出現(xiàn)的頻率至少和預(yù)定義的最小支持度一樣 由頻繁項(xiàng)集來(lái)產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則：這些規(guī)則必須滿足最小支持度和最小置信度,Apriori算法,Apriori性質(zhì) 先驗(yàn)（ Apriori ）法則：一個(gè)頻繁項(xiàng)集的任何非空子集肯定也是一個(gè)頻繁項(xiàng)集 例如{A，B}為高頻項(xiàng)集，那么其子集{A}、{B}一定都為高頻項(xiàng)集 反單調(diào)：一個(gè)集合如果不能通過測(cè)試，則它的任何超集也不能通過測(cè)試 反復(fù)尋找高頻項(xiàng)集(從1到K階),Apriori算法,如何由Lk1產(chǎn)生Lk ？ 連接步：對(duì)K1階頻繁項(xiàng)集Lk1做SelfJoin操作，形成K階頻繁項(xiàng)集的候選集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階非頻繁項(xiàng)集，則其不可能為K階頻繁項(xiàng)集的子集 具體算法如下： 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階高頻項(xiàng)目集：L3={abc, abd, acd, ace, bcd} 連接步 Selfjoining: L3*L3 abc，abd ? abcd acd, ace ? acde 剪枝步 acde 移出，因?yàn)?ade不包含在 L3中 4階候選集：C4={abcd},Apriori算法,數(shù)據(jù)庫(kù)事務(wù)數(shù)據(jù)D,最小支持度min_sup=2,Apriori算法,掃描D，對(duì)每 個(gè)候選記數(shù),比較sup.與 min_sup,C1,L1,Apriori算法,由L1產(chǎn)生C2,掃描D，對(duì)每 個(gè)候選記數(shù),C2,C2,Apriori算法,比較sup.與 min_sup,L2,由L2產(chǎn)生C3,C3,Apriori算法,使用Apriori 性質(zhì)剪枝,C3,掃描D，對(duì)每 個(gè)候選記數(shù),C3,比較sup.與 min_sup,L3,由頻繁項(xiàng)集來(lái)產(chǎn)生關(guān)聯(lián)規(guī)則,步驟 對(duì)于每個(gè)頻繁項(xiàng)集l，產(chǎn)生l的所有非空子集 對(duì)于L的每個(gè)非空子集s，如果: 則輸出規(guī)則“s ? (ls)”，其中min_conf是最小置信度閾值 由于規(guī)則由頻繁項(xiàng)集產(chǎn)生，每個(gè)規(guī)則自動(dòng)滿足最小支持度,由頻繁項(xiàng)集來(lái)產(chǎn)生關(guā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）,含義 有一個(gè)記錄集合和一組標(biāo)記，標(biāo)記用以標(biāo)識(shí)記錄的類別 先為每個(gè)記錄賦予一個(gè)標(biāo)記（按標(biāo)記對(duì)記錄分類） 對(duì)同類記錄的特征進(jìn)行描述 顯式描述：例如，一組規(guī)則定義 隱式描述：例如，一個(gè)數(shù)學(xué)模型或公式 分類具有極其廣泛的應(yīng)用 分類常用于預(yù)測(cè) 醫(yī)療診斷、性能預(yù)測(cè)、選擇購(gòu)物、信譽(yù)證實(shí)等,分類分析的兩個(gè)步驟,構(gòu)建模型:對(duì)預(yù)先確定的類別給出相應(yīng)的描述 先假設(shè)一個(gè)元組（或樣本）集合中的每一