數(shù)據(jù)挖掘常用算法概述

1、關(guān)聯(lián)分析關(guān)聯(lián)分析關(guān)聯(lián)規(guī)則挖掘的提出關(guān)聯(lián)規(guī)則挖掘的提出l關(guān)聯(lián)規(guī)則挖掘的典型案例：購物籃問題關(guān)聯(lián)規(guī)則挖掘的典型案例：購物籃問題l在商場中擁有大量的商品（項目），如：牛奶、面包等，客戶將在商場中擁有大量的商品（項目），如：牛奶、面包等，客戶將所購買的商品放入到自己的購物籃中。所購買的商品放入到自己的購物籃中。l通過發(fā)現(xiàn)顧客放入購物籃中的不同商品之間的聯(lián)系，分析顧客的通過發(fā)現(xiàn)顧客放入購物籃中的不同商品之間的聯(lián)系，分析顧客的購買習(xí)慣購買習(xí)慣l哪些物品經(jīng)常被顧客購買？哪些物品經(jīng)常被顧客購買？l同一次購買中，哪些商品經(jīng)常會被一起購買？同一次購買中，哪些商品經(jīng)常會被一起購買？l一般用戶的購買過程中是否存在一定

2、的購買時間序列？一般用戶的購買過程中是否存在一定的購買時間序列？l具體應(yīng)用：利潤最大化具體應(yīng)用：利潤最大化l商品貨架設(shè)計：更加適合客戶的購物路徑商品貨架設(shè)計：更加適合客戶的購物路徑l貨存安排貨存安排 ：實現(xiàn)超市的零庫存管理：實現(xiàn)超市的零庫存管理l用戶分類用戶分類 ：提供個性化的服務(wù)：提供個性化的服務(wù)其他典型應(yīng)用其他典型應(yīng)用l相關(guān)文獻(xiàn)的收集相關(guān)文獻(xiàn)的收集l購物籃購物籃 = 文檔（文檔（Document）l項項 目目 = 單詞（單詞（Word）l相關(guān)網(wǎng)站的收集相關(guān)網(wǎng)站的收集l購物籃購物籃 = 詞句（詞句（Sentences）l項項 目目 =鏈接文檔（鏈接文檔（Document）什么是關(guān)聯(lián)規(guī)則挖掘什

3、么是關(guān)聯(lián)規(guī)則挖掘? ?l關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則挖掘l簡單的說，關(guān)聯(lián)規(guī)則挖掘發(fā)現(xiàn)大量數(shù)據(jù)中項集之間有簡單的說，關(guān)聯(lián)規(guī)則挖掘發(fā)現(xiàn)大量數(shù)據(jù)中項集之間有趣的關(guān)聯(lián)趣的關(guān)聯(lián)l在交易數(shù)據(jù)、關(guān)系數(shù)據(jù)或其他信息載體中，查找存在在交易數(shù)據(jù)、關(guān)系數(shù)據(jù)或其他信息載體中，查找存在于項目集合或?qū)ο蠹现g的頻繁模式、關(guān)聯(lián)、相關(guān)于項目集合或?qū)ο蠹现g的頻繁模式、關(guān)聯(lián)、相關(guān)性、或因果結(jié)構(gòu)。性、或因果結(jié)構(gòu)。l應(yīng)用應(yīng)用l購物籃分析、交叉銷售、產(chǎn)品目錄設(shè)計、購物籃分析、交叉銷售、產(chǎn)品目錄設(shè)計、 loss-leader analysis、聚集、分類等。、聚集、分類等。關(guān)聯(lián)規(guī)則挖掘形式化定義關(guān)聯(lián)規(guī)則挖掘形式化定義l給定給定:l交易數(shù)據(jù)

4、庫交易數(shù)據(jù)庫 l每筆交易是：一個項目列表每筆交易是：一個項目列表 (消費者一次購買活動中購買的商消費者一次購買活動中購買的商品品)l查找查找: l所有描述一個項目集合與其他項目集合相關(guān)性的規(guī)則所有描述一個項目集合與其他項目集合相關(guān)性的規(guī)則l應(yīng)用應(yīng)用l* 護(hù)理用品護(hù)理用品 (商店應(yīng)該怎樣提高護(hù)理用品的銷售？商店應(yīng)該怎樣提高護(hù)理用品的銷售？)l家用電器家用電器 * (其他商品的庫存有什么影響其他商品的庫存有什么影響?)l在產(chǎn)品直銷中使用附加郵寄在產(chǎn)品直銷中使用附加郵寄其它相關(guān)概念其它相關(guān)概念l包含包含k個項目的集合，稱為個項目的集合，稱為k-項集項集l項集的出現(xiàn)頻率是包含項集的事務(wù)個數(shù)，稱為項集的

5、頻率、支持計數(shù)項集的出現(xiàn)頻率是包含項集的事務(wù)個數(shù)，稱為項集的頻率、支持計數(shù)或者計數(shù)或者計數(shù)l關(guān)聯(lián)規(guī)則的基本形式：前提條件關(guān)聯(lián)規(guī)則的基本形式：前提條件 結(jié)論結(jié)論 支持度支持度, 置信度置信度lbuys(x, “diapers”) buys(x, “beers”) 0.5%, 60%lmajor(x, “CS”) takes(x, “DB”) grade(x, “A”) 1%, 75%關(guān)聯(lián)規(guī)則興趣度的度量值：支持度關(guān)聯(lián)規(guī)則興趣度的度量值：支持度l推導(dǎo)出的數(shù)據(jù)間的相關(guān)性可稱為規(guī)則（或模式），對規(guī)則興趣度的描推導(dǎo)出的數(shù)據(jù)間的相關(guān)性可稱為規(guī)則（或模式），對規(guī)則興趣度的描述采用支持度、置信度概念。述采用支

6、持度、置信度概念。l支持度（支持度（Support）：規(guī)則）：規(guī)則XY在交易數(shù)據(jù)庫在交易數(shù)據(jù)庫D中的支持度是交易集中的支持度是交易集中包含中包含X和和Y的交易數(shù)與所有交易數(shù)之比，記為的交易數(shù)與所有交易數(shù)之比，記為support(XY)，即，即support(XY)=|T:X Y T，T D|/ |D|，它是概率，它是概率P（ X Y ），具），具體體表示為表示為：購買商品購買商品Y的交易的交易同時購買商品同時購買商品X和和Y的交易的交易購買商品購買商品X的交易的交易關(guān)聯(lián)規(guī)則興趣度的度量值：置信度關(guān)聯(lián)規(guī)則興趣度的度量值：置信度l置信度（置信度（Confidence），規(guī)則），規(guī)則XY在交易集中的

7、置信度是指包在交易集中的置信度是指包含含X和和Y的交易數(shù)與包含的交易數(shù)與包含X的交易數(shù)之比，記為的交易數(shù)之比，記為confidence(XY)，即即confidence(XY)=|T: X Y T，T D|/|T:X T，T D|，它，它是概率是概率P（ X|Y ），具體），具體表示為表示為：l最小支持度和最小置信度最小支持度和最小置信度用戶（分析員）不關(guān)心可信程度太低的規(guī)則，因而用戶需要輸入用戶（分析員）不關(guān)心可信程度太低的規(guī)則，因而用戶需要輸入兩個參數(shù)：最小支持度和最小置信度。兩個參數(shù)：最小支持度和最小置信度。購買商品購買商品Y的交易的交易同時購買商品同時購買商品X和和Y的交易的交易購買商

8、品購買商品X的交易的交易支持度和置信度舉例支持度和置信度舉例l零售商場銷售分析：零售商場銷售分析：l數(shù)據(jù)項為商品，記錄集合為交易記錄集合數(shù)據(jù)項為商品，記錄集合為交易記錄集合l規(guī)則為：規(guī)則為：“購買商品購買商品X的顧客，同時購買商品的顧客，同時購買商品Y”，即，即X Y；l設(shè)最小支持度為設(shè)最小支持度為0 .3；最小置信度也為；最小置信度也為0.3。l分析結(jié)果：分析結(jié)果： Item1 Item2 置置信信度度C 支支持持度度S A B 1 0.33 B A 0.33 0.33 B C 0.33 0.33 B D 0.66 0.66 C B 1 0.33 C D 1 0.33 D B 1 0.66

9、D C 0.5 0.33 交交易易號號 顧顧客客號號 商商品品號號 數(shù)數(shù)量量 日日期期 1 甲甲 A 14 3/4/95 甲甲 B 3 3/4/95 2 乙乙 C 2 5/6/95 乙乙 B 3 5/6/95 乙乙 D 13 5/6/95 3 乙乙 B 10 8/6/95 乙乙 D 12 8/6/95頻繁項集及其基本特征頻繁項集及其基本特征l頻繁項集的定義頻繁項集的定義l如果項集滿足最小支持度，則稱之為頻繁項集（高頻項集）如果項集滿足最小支持度，則稱之為頻繁項集（高頻項集）l頻繁項集的基本特征頻繁項集的基本特征l任何頻繁項集的子集均為頻繁項集。例如：任何頻繁項集的子集均為頻繁項集。例如：ABC

10、是頻繁項集，則是頻繁項集，則AB、AC、BC均為頻繁項集均為頻繁項集l在數(shù)據(jù)庫表分區(qū)的情況下，一個項集是頻繁的，則至少在一個分在數(shù)據(jù)庫表分區(qū)的情況下，一個項集是頻繁的，則至少在一個分區(qū)內(nèi)是頻繁的區(qū)內(nèi)是頻繁的關(guān)聯(lián)規(guī)則挖掘的種類關(guān)聯(lián)規(guī)則挖掘的種類l布爾布爾 vs. 數(shù)值型關(guān)聯(lián)數(shù)值型關(guān)聯(lián) (基于基于 處理數(shù)據(jù)的類型處理數(shù)據(jù)的類型)l性別性別“女女” 職業(yè)職業(yè)“ 秘書秘書” 1%, 75% 布爾型關(guān)聯(lián)規(guī)則布爾型關(guān)聯(lián)規(guī)則 l性別性別“女女” 收入收入 = 2000 1%, 75% 數(shù)值型關(guān)聯(lián)規(guī)則數(shù)值型關(guān)聯(lián)規(guī)則 l單維單維 vs. 多維多維 關(guān)聯(lián)關(guān)聯(lián)lage(x, “30.39”) income(x, “

11、42.48K”) buys(x, “PC”) 1%, 75%lbuys(x, “Book”) buys(x, “Pen”) buys(x, “Ink”) 1%, 75%l單層單層 vs. 多層多層 分析分析l那個品種牌子的啤酒與那個牌子的尿布有關(guān)系那個品種牌子的啤酒與那個牌子的尿布有關(guān)系?l各種擴(kuò)展各種擴(kuò)展l相關(guān)性、因果分析相關(guān)性、因果分析l關(guān)聯(lián)并不一定意味著相關(guān)或因果關(guān)聯(lián)并不一定意味著相關(guān)或因果l最大模式和閉合相集最大模式和閉合相集l添加約束添加約束l如如, 哪些哪些“小東西小東西”的銷售促發(fā)了的銷售促發(fā)了“大家伙大家伙”的買賣？的買賣？關(guān)聯(lián)規(guī)則挖掘的基本過程關(guān)聯(lián)規(guī)則挖掘的基本過程l找出所有

12、的找出所有的頻繁項集頻繁項集 F，其中對于任何的其中對于任何的 Z F，在交易集合在交易集合D中至少中至少 s%的事務(wù)包含的事務(wù)包含Zl根據(jù)置信度和頻繁項集根據(jù)置信度和頻繁項集F, 產(chǎn)生關(guān)聯(lián)規(guī)則。具體方法如下：產(chǎn)生關(guān)聯(lián)規(guī)則。具體方法如下：lconf(X Y) = supp(X)/supp(X Y)l如果如果 conf(X Y) c 成立，則產(chǎn)生成立，則產(chǎn)生 X Y 的規(guī)則的規(guī)則, 因為因為:lsupp(X Y) = supp(X Y) s 且且lconf(X Y) cl因此關(guān)聯(lián)規(guī)則的挖掘可以轉(zhuǎn)換為頻繁項集的挖掘和頻繁項集之間的關(guān)聯(lián)。因此關(guān)聯(lián)規(guī)則的挖掘可以轉(zhuǎn)換為頻繁項集的挖掘和頻繁項集之間的關(guān)聯(lián)

13、。關(guān)聯(lián)規(guī)則挖掘：一個例子關(guān)聯(lián)規(guī)則挖掘：一個例子l對于對于 A C：lsupport = support(A 、C) = 50%lconfidence = support(A 、C)/support(A) = 66.6%交易ID購買商品2000A,B,C1000A,C4000A,D5000B,E,F頻繁項集支持度A75%B50%C50%A,C50%l最小值尺度最小值尺度 50%l最小可信度最小可信度 50%關(guān)聯(lián)規(guī)則挖掘的優(yōu)缺點關(guān)聯(lián)規(guī)則挖掘的優(yōu)缺點l優(yōu)點優(yōu)點l它可以產(chǎn)生清晰有用的結(jié)果它可以產(chǎn)生清晰有用的結(jié)果l它支持間接數(shù)據(jù)挖掘它支持間接數(shù)據(jù)挖掘l可以處理變長的數(shù)據(jù)可以處理變長的數(shù)據(jù)l它的計算的消耗

14、量是可以預(yù)見的它的計算的消耗量是可以預(yù)見的 l缺點缺點l當(dāng)問題變大時，計算量增長得厲害當(dāng)問題變大時，計算量增長得厲害l難以決定正確的數(shù)據(jù)難以決定正確的數(shù)據(jù)l容易忽略稀有的數(shù)據(jù)容易忽略稀有的數(shù)據(jù)查找頻繁項集查找頻繁項集 Apriori算法算法l查找具有最小支持度的頻繁項集是關(guān)聯(lián)規(guī)則挖掘最為重要的步驟查找具有最小支持度的頻繁項集是關(guān)聯(lián)規(guī)則挖掘最為重要的步驟lApriori算法是目前最有影響力的一個算法，在算法是目前最有影響力的一個算法，在1994年，由年，由R.Agrawal, S.Srikant提出提出l該算法基于頻繁項集的特征：如果項集該算法基于頻繁項集的特征：如果項集l = i1,i2,in

15、 是頻繁的，當(dāng)且是頻繁的，當(dāng)且僅當(dāng)項集的所有子集均為頻繁項集僅當(dāng)項集的所有子集均為頻繁項集.也就是說，如果也就是說，如果supp(l) s，當(dāng)且僅，當(dāng)且僅當(dāng)當(dāng) supp(l ) s, l ll因此，我們可以采用層次順序的方法來實現(xiàn)頻繁項集的挖掘。首先，因此，我們可以采用層次順序的方法來實現(xiàn)頻繁項集的挖掘。首先，挖掘一階頻繁項集挖掘一階頻繁項集L1。在此基礎(chǔ)上，形成二階候選項集，挖掘二階頻繁。在此基礎(chǔ)上，形成二階候選項集，挖掘二階頻繁項集。依此類推。項集。依此類推。AprioriApriori算法算法l連接連接: 用用 Lk-1自連接得到自連接得到Ckl剪枝剪枝: 一個一個k-項集，如果它的一個

16、項集，如果它的一個k-1項集（它的子集項集（它的子集 ）不是頻繁）不是頻繁的，那他本身也不可能是頻繁的。的，那他本身也不可能是頻繁的。l偽代碼偽代碼:lCk: 長度為長度為k的候選項集的候選項集lLk :長度為長度為k的頻繁項集的頻繁項集lL1 = frequent items; for (k = 1; Lk !=; k+) do begin Ck+1 = 從從Lk 生成候選項集生成候選項集; 對于數(shù)據(jù)庫中的任一交易對于數(shù)據(jù)庫中的任一交易 t do 如果如果 t 中包含中包含 Ck+1中所包含的項集，則計數(shù)加中所包含的項集，則計數(shù)加 1 Lk+1 = Ck+1 中超過最小支持度的頻繁項集中超過

17、最小支持度的頻繁項集 end return k Lk;AprioriApriori算法算法 例子例子TID Items100 1 3 4200 2 3 5300 1 2 3 5400 2 5數(shù)據(jù)庫數(shù)據(jù)庫 Ditemset sup.1223334153itemset sup.12233353掃描掃描 DC1L1itemset1 21 31 52 32 53 5itemset sup1 211 321 512 322 533 52itemset sup1 322 322 533 52L2C2C2掃描掃描 DC3L3itemset2 3 5掃描掃描 Ditemset sup2 3 52Apriori

18、 Apriori 夠快了嗎夠快了嗎? ? 性能瓶頸性能瓶頸lApriori算法的核心算法的核心:l用頻繁的用頻繁的(k 1)-項集生成候選的頻繁項集生成候選的頻繁 k-項集項集l用數(shù)據(jù)庫掃描和模式匹配計算候選集的支持度用數(shù)據(jù)庫掃描和模式匹配計算候選集的支持度lApriori 的瓶頸的瓶頸: 候選集生成候選集生成l巨大的候選集巨大的候選集:l104 個頻繁個頻繁1-項集要生成項集要生成 107 個候選個候選 2-項集，并且累計和檢項集，并且累計和檢查它們的頻繁性查它們的頻繁性l要找長度為要找長度為100的頻繁模式，如的頻繁模式，如 a1, a2, , a100, 你必須你必須先產(chǎn)生先產(chǎn)生2100

19、 1030 個候選集個候選集l重復(fù)掃描數(shù)據(jù)庫：重復(fù)掃描數(shù)據(jù)庫：l如果最長的模式是如果最長的模式是n的話，則需要的話，則需要 (n +1 ) 次數(shù)據(jù)庫掃描次數(shù)據(jù)庫掃描關(guān)聯(lián)規(guī)則結(jié)果顯示關(guān)聯(lián)規(guī)則結(jié)果顯示 (Table Form )(Table Form )關(guān)聯(lián)規(guī)則可視化關(guān)聯(lián)規(guī)則可視化Using Rule GraphUsing Rule Graph擴(kuò)展知識：多層關(guān)聯(lián)規(guī)則擴(kuò)展知識：多層關(guān)聯(lián)規(guī)則l項通常具有層次項通常具有層次l底層的項通常支持度也低底層的項通常支持度也低l某些特定層的規(guī)則可能更有某些特定層的規(guī)則可能更有意義意義l交易數(shù)據(jù)庫可以按照維或?qū)咏灰讛?shù)據(jù)庫可以按照維或?qū)泳幋a編碼l可以進(jìn)行共享的多維挖

20、掘可以進(jìn)行共享的多維挖掘食品面包牛奶脫脂奶光明統(tǒng)一酸奶白黃TID ItemsT1111, 121, 211, 221T2111, 211, 222, 323T3112, 122, 221, 411T4111, 121T5111, 122, 211, 221, 413擴(kuò)展知識：多維關(guān)聯(lián)規(guī)則擴(kuò)展知識：多維關(guān)聯(lián)規(guī)則l單維關(guān)聯(lián)規(guī)則（維內(nèi)關(guān)聯(lián)規(guī)則）單維關(guān)聯(lián)規(guī)則（維內(nèi)關(guān)聯(lián)規(guī)則）l關(guān)聯(lián)規(guī)則中僅包含單個謂詞（維）關(guān)聯(lián)規(guī)則中僅包含單個謂詞（維）l通常針對的是事務(wù)數(shù)據(jù)庫通常針對的是事務(wù)數(shù)據(jù)庫 buys(X, “milk”) buys(X, “bread”)l多維關(guān)聯(lián)規(guī)則：規(guī)則內(nèi)包含多維關(guān)聯(lián)規(guī)則：規(guī)則內(nèi)包含2 個以

21、上維個以上維/謂詞謂詞l維間關(guān)聯(lián)規(guī)則維間關(guān)聯(lián)規(guī)則 (不重復(fù)謂詞不重復(fù)謂詞)age(X,”19-25”) occupation(X,“student”) buys(X,“coke”)l混合維關(guān)聯(lián)規(guī)則混合維關(guān)聯(lián)規(guī)則 (存在重復(fù)存在重復(fù)謂詞謂詞) age(X,”19-25”) buys(X, “popcorn”) buys(X, “coke”)分類與預(yù)測分類與預(yù)測本章內(nèi)容本章內(nèi)容l分類與預(yù)測的基本概念分類與預(yù)測的基本概念l決策樹分類決策樹分類l實例：移動通信客戶流失分析系統(tǒng)實例：移動通信客戶流失分析系統(tǒng)l神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)l其他分類方法其他分類方法l預(yù)測（回歸）預(yù)測（回歸）建立模型過程建立模型過程歷史

22、數(shù)據(jù)歷史數(shù)據(jù)模型模型建模建模記錄集合記錄集合預(yù)測預(yù)測數(shù)學(xué)公式數(shù)學(xué)公式規(guī)則集合規(guī)則集合l分類分類 l為一個事件或?qū)ο筮M(jìn)行歸類為一個事件或?qū)ο筮M(jìn)行歸類l預(yù)測分類標(biāo)簽（離散值）預(yù)測分類標(biāo)簽（離散值）l基于訓(xùn)練集形成一個模型，訓(xùn)練集中的類標(biāo)簽是已知的。使用基于訓(xùn)練集形成一個模型，訓(xùn)練集中的類標(biāo)簽是已知的。使用該模型對新的數(shù)據(jù)進(jìn)行分類該模型對新的數(shù)據(jù)進(jìn)行分類l分類模型：分類器（分類函數(shù)、分類規(guī)則等）分類模型：分類器（分類函數(shù)、分類規(guī)則等）l預(yù)測預(yù)測: l對連續(xù)或者有序的值進(jìn)行建模和預(yù)測（回歸方法）對連續(xù)或者有序的值進(jìn)行建模和預(yù)測（回歸方法） l典型應(yīng)用典型應(yīng)用l客戶客戶/用戶分類用戶分類l信用評分信用評

23、分l目標(biāo)營銷目標(biāo)營銷l醫(yī)療診斷醫(yī)療診斷l(xiāng)分類和預(yù)測分類和預(yù)測分類的相關(guān)概念分類的相關(guān)概念l訓(xùn)練集（訓(xùn)練集（Training Set）：由一組數(shù)據(jù)庫記錄或者元組構(gòu)成，每個）：由一組數(shù)據(jù)庫記錄或者元組構(gòu)成，每個記錄由有關(guān)字段值組成特征向量，這些字段稱為屬性。記錄由有關(guān)字段值組成特征向量，這些字段稱為屬性。l用于分類的屬性稱為標(biāo)簽屬性。標(biāo)簽屬性也就是訓(xùn)練集的類別標(biāo)用于分類的屬性稱為標(biāo)簽屬性。標(biāo)簽屬性也就是訓(xùn)練集的類別標(biāo)記。記。l標(biāo)簽屬性的類型必須是離散的，而且標(biāo)簽屬性的可能值的數(shù)目越標(biāo)簽屬性的類型必須是離散的，而且標(biāo)簽屬性的可能值的數(shù)目越少越好。少越好。分類的兩個步驟分類的兩個步驟l模型創(chuàng)建模型創(chuàng)建

24、: 對一個已經(jīng)事先確定的類別創(chuàng)建模型對一個已經(jīng)事先確定的類別創(chuàng)建模型l每個元組屬于一個事先確定的類別，使用分類標(biāo)簽屬性予以確定每個元組屬于一個事先確定的類別，使用分類標(biāo)簽屬性予以確定l用于創(chuàng)建模型的數(shù)據(jù)集叫用于創(chuàng)建模型的數(shù)據(jù)集叫: 訓(xùn)練集。單個元組稱為訓(xùn)練樣本訓(xùn)練集。單個元組稱為訓(xùn)練樣本l模型可以用分類規(guī)則，決策樹，或者數(shù)學(xué)方程的形式來表達(dá)。模型可以用分類規(guī)則，決策樹，或者數(shù)學(xué)方程的形式來表達(dá)。l模型使用模型使用: 用創(chuàng)建的模型預(yù)測未來或者類別未知的記錄用創(chuàng)建的模型預(yù)測未來或者類別未知的記錄l估計模型的準(zhǔn)確率估計模型的準(zhǔn)確率l使用創(chuàng)建的模型在一個測試集上進(jìn)行預(yù)測，并將結(jié)果和實際值進(jìn)行比較使用創(chuàng)

25、建的模型在一個測試集上進(jìn)行預(yù)測，并將結(jié)果和實際值進(jìn)行比較l準(zhǔn)確率：準(zhǔn)確率：l測試集和訓(xùn)練集是獨立的。測試集和訓(xùn)練集是獨立的。分類過程：模型創(chuàng)建（學(xué)習(xí)過分類過程：模型創(chuàng)建（學(xué)習(xí)過程）程）訓(xùn)練集NAME RANKYEARS TENUREDMikeAssistant Prof3noMaryAssistant Prof7yesBill Professor2yesJimAssociate Prof7yesDaveAssistant Prof6noAnneAssociate Prof3no分類算法IF rank = professorOR years 6THEN tenured = yes 模型分類過程分

26、類過程 : 使用模型使用模型模型測試集NAMERANKYEARS TENUREDTomAssistant Prof2noMerlisa Associate Prof7noGeorge Professor5yesJoseph Assistant Prof7yes未知數(shù)據(jù)(Jeff, Professor, 4)Tenured?本章內(nèi)容本章內(nèi)容l分類與預(yù)測的基本概念分類與預(yù)測的基本概念l決策樹分類決策樹分類l實例：移動通信客戶流失分析系統(tǒng)實例：移動通信客戶流失分析系統(tǒng)l神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)l其他分類方法其他分類方法l預(yù)測預(yù)測（回歸）（回歸）使用決策樹進(jìn)行分類使用決策樹進(jìn)行分類l決策樹決策樹 l一個樹型的

27、結(jié)構(gòu)一個樹型的結(jié)構(gòu)l內(nèi)部節(jié)點上選用一個屬性進(jìn)行分裂內(nèi)部節(jié)點上選用一個屬性進(jìn)行分裂 （決策節(jié)點）（決策節(jié)點）l每個分叉都是分裂的一個部分每個分叉都是分裂的一個部分l葉子節(jié)點表示一個分布葉子節(jié)點表示一個分布l節(jié)點的子節(jié)點個數(shù)跟算法相關(guān)節(jié)點的子節(jié)點個數(shù)跟算法相關(guān)age?student?credit rating?noyesfairexcellent40nonoyesyesyes30.40決策樹分類的特點決策樹分類的特點l優(yōu)點優(yōu)點l容易生成可以理解的規(guī)則容易生成可以理解的規(guī)則l計算量相對來說不大計算量相對來說不大l可以處理離散和連續(xù)字段可以處理離散和連續(xù)字段l可以清晰顯示哪些字段比較重要可以清晰顯示哪

28、些字段比較重要l缺點缺點l對連續(xù)性的字段難以預(yù)測對連續(xù)性的字段難以預(yù)測l類別太多的時候，錯誤的可能性會加大類別太多的時候，錯誤的可能性會加大l一般情況下，標(biāo)簽屬性的個數(shù)有限一般情況下，標(biāo)簽屬性的個數(shù)有限決策樹的生成與使用決策樹的生成與使用l決策樹生成算法分成兩個步驟決策樹生成算法分成兩個步驟l樹的生成樹的生成l開始，數(shù)據(jù)都在根節(jié)點開始，數(shù)據(jù)都在根節(jié)點l遞歸的進(jìn)行數(shù)據(jù)分割遞歸的進(jìn)行數(shù)據(jù)分割l樹的修剪樹的修剪l去掉一些可能是噪音或者異常的數(shù)據(jù)去掉一些可能是噪音或者異常的數(shù)據(jù)l決策樹使用決策樹使用: 對未知數(shù)據(jù)進(jìn)行分割對未知數(shù)據(jù)進(jìn)行分割l按照決策樹上采用的分割屬性逐層往下，直到一個葉子節(jié)點按照決策樹

29、上采用的分割屬性逐層往下，直到一個葉子節(jié)點訓(xùn)練集訓(xùn)練集ageincome studentcredit_ratingbuys_computer=30highnofairno40mediumnofairyes40lowyesfairyes40lowyesexcellentno3140 lowyesexcellentyes=30mediumnofairno40mediumyesfairyes40mediumnoexcellentnoID3算法決策樹結(jié)果：決策樹結(jié)果： “buys_computer”age?overcaststudent?credit rating?noyesfairexcellent

30、40nonoyesyesyes30.40決策樹算法決策樹算法l基本算法（貪心算法）基本算法（貪心算法）l自上而下分而治之的方法自上而下分而治之的方法l開始時，所有的數(shù)據(jù)都在根節(jié)點開始時，所有的數(shù)據(jù)都在根節(jié)點l屬性都是種類字段屬性都是種類字段 (如果是連續(xù)的，將其離散化如果是連續(xù)的，將其離散化)l所有記錄用所選屬性遞歸的進(jìn)行分割所有記錄用所選屬性遞歸的進(jìn)行分割l屬性的選擇是基于一個啟發(fā)式規(guī)則或者一個統(tǒng)計的度量屬性的選擇是基于一個啟發(fā)式規(guī)則或者一個統(tǒng)計的度量 (如如, information gain)l停止分割的條件停止分割的條件l一個節(jié)點上的數(shù)據(jù)都是屬于同一個類別一個節(jié)點上的數(shù)據(jù)都是屬于同一個

31、類別l沒有屬性可以再用于對數(shù)據(jù)進(jìn)行分割沒有屬性可以再用于對數(shù)據(jù)進(jìn)行分割幾種經(jīng)典算法介紹幾種經(jīng)典算法介紹lCARTl min(P(c1),P(c2)l 2P(c1)P(c2)l P(c1)logP(c1)+P(c2)logP(c2) C4.5(ID3)lC4.5(ID3)l對種類字段處理時，缺省是對每個值作為一個分割對種類字段處理時，缺省是對每個值作為一個分割lGain和和Gain RatiolCHAIDl在在Overfitting前停止樹的生成前停止樹的生成l必須都是分類屬性必須都是分類屬性l選擇分割。選擇分割。X2檢驗檢驗 從樹中生成分類規(guī)則從樹中生成分類規(guī)則l用用 IF-THEN 這種形式

32、來表現(xiàn)規(guī)則這種形式來表現(xiàn)規(guī)則l每個葉子節(jié)點都創(chuàng)建一條規(guī)則每個葉子節(jié)點都創(chuàng)建一條規(guī)則l每個分割都成為一個規(guī)則中的一個條件每個分割都成為一個規(guī)則中的一個條件l葉子節(jié)點中的類別就是葉子節(jié)點中的類別就是Then的內(nèi)容的內(nèi)容l規(guī)則對于人來說更容易理解規(guī)則對于人來說更容易理解l例子例子lIF age = “=30” AND student = “no” THEN buys_computer = “no”lIF age = “40” AND credit_rating = “excellent” THEN buys_computer = “yes”lIF age = “=30” AND credit_rat

33、ing = “fair” THEN buys_computer = “no”本章內(nèi)容本章內(nèi)容l分類與預(yù)測的基本概念分類與預(yù)測的基本概念l決策樹分類決策樹分類l實例：移動通信客戶流失分析系統(tǒng)實例：移動通信客戶流失分析系統(tǒng)l神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)l其他分類方法其他分類方法l預(yù)測（回歸）預(yù)測（回歸）應(yīng)用背景與問題定義應(yīng)用背景與問題定義l背景背景l(fā)在移動通信領(lǐng)域，客戶流失成為通信運營企業(yè)關(guān)注的焦點在移動通信領(lǐng)域，客戶流失成為通信運營企業(yè)關(guān)注的焦點l通信業(yè)務(wù)產(chǎn)生的海量、珍貴數(shù)據(jù)為數(shù)據(jù)挖掘的研究提供了堅實通信業(yè)務(wù)產(chǎn)生的海量、珍貴數(shù)據(jù)為數(shù)據(jù)挖掘的研究提供了堅實的基礎(chǔ)的基礎(chǔ)l把數(shù)據(jù)挖掘理論應(yīng)用于移動通信領(lǐng)域的客戶流

34、失分析，進(jìn)而為把數(shù)據(jù)挖掘理論應(yīng)用于移動通信領(lǐng)域的客戶流失分析，進(jìn)而為通信企業(yè)的實際業(yè)務(wù)提供指導(dǎo)是一項具有挑戰(zhàn)性的工作通信企業(yè)的實際業(yè)務(wù)提供指導(dǎo)是一項具有挑戰(zhàn)性的工作l定義定義l客戶流失分析，就是利用數(shù)據(jù)挖掘等分析方法，對已流失客戶客戶流失分析，就是利用數(shù)據(jù)挖掘等分析方法，對已流失客戶過去一段時間的通話、繳費等信息進(jìn)行分析，提煉出流失客戶過去一段時間的通話、繳費等信息進(jìn)行分析，提煉出流失客戶的行為特征，利用這些特征預(yù)測在網(wǎng)客戶的流失傾向的行為特征，利用這些特征預(yù)測在網(wǎng)客戶的流失傾向 按真實比例抽取，可能掩蓋流失用戶的特征 解決方法：“樣本放大”數(shù)據(jù)預(yù)處理數(shù)據(jù)預(yù)處理抽樣抽樣原始數(shù)據(jù)（流失概率3.2

35、%）采樣后（流失概率25%）10,000310,000300,00050%20:15,00015,00020,000流失非流失數(shù)據(jù)預(yù)處理數(shù)據(jù)預(yù)處理時間相關(guān)屬性時間相關(guān)屬性屬性序列S1用用戶戶標(biāo)標(biāo)識識性性別別年年齡齡入入網(wǎng)網(wǎng)品品牌牌 1 1月月份份通通話話時時長長2 2月月份份通通話話時時長長6 6月月份份通通話話時時長長 1 1月月份份話話費費 6 6月月份份話話費費是是否否流流失失屬性序列Sn“靜態(tài)”屬性流失標(biāo)志解決方法：生成匯總屬性（求和、取均值等）生成“趨勢屬性”，如由屬性序列S1生成屬性“通話時長趨勢”問題： 決策樹算法缺乏處理時間相關(guān)屬性的能力，致使效率下降數(shù)據(jù)預(yù)處理數(shù)據(jù)預(yù)處理生成趨

36、勢屬性生成趨勢屬性0200400600800100012001400160018002000123456月份通話時長用戶1用戶2把每個月通話時長Y視為月份X（取值從1到6）的線性函數(shù)，即Y = + X ，系數(shù)作為屬性“通話時長趨勢”的取值，從而把求趨勢屬性的問題轉(zhuǎn)化為簡單的線形回歸問題，siisiiixxyyxx121)()(數(shù)據(jù)預(yù)處理數(shù)據(jù)預(yù)處理生成趨勢屬性（續(xù)）生成趨勢屬性（續(xù)）siiisiiiixxwyyxxw121)()(實際應(yīng)用中，發(fā)現(xiàn)各個月份的數(shù)值對趨勢屬性的影響不同，可以對各個月份指定不同的權(quán)重w作為新生成的趨勢屬性，可以進(jìn)一步轉(zhuǎn)換成離散值，如，顯著上升、小幅上升、持平、小幅下降、

37、顯著下降例如：1到6月份權(quán)重分別取1、1、1、2、3、4決策樹示例決策樹示例通話次數(shù)=20品牌話費金額神州行全球通 流失=25 流失 非流失 非流失用戶用戶ID通話次數(shù)通話次數(shù)品牌品牌話費金額話費金額流失標(biāo)志流失標(biāo)志139*88423全球通全球通23品牌 非流失神州行全球通第一步：建立決策樹第二步：預(yù)測流失流失20,80 0.2通話次數(shù)=20品牌消費金額神州行10,30 0.2510,50 0.167全球通2,23 0.088,7 0.53=254,36 0.1品牌6,14 0.3神州行全球通1,8 0.115,6 0.45Cx,y k%x:流失用戶數(shù)y:未流失用戶數(shù)k:流失概率 k = x/

38、(x+y)A決策樹算法決策樹算法數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)主要內(nèi)容主要內(nèi)容l分類與預(yù)測的基本概念分類與預(yù)測的基本概念l決策樹分類決策樹分類l實例：移動通信客戶流失分析系統(tǒng)實例：移動通信客戶流失分析系統(tǒng)l神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)l其他分類方法其他分類方法l預(yù)測預(yù)測（回歸）（回歸）神經(jīng)網(wǎng)絡(luò)技術(shù)神經(jīng)網(wǎng)絡(luò)技術(shù)l生物神經(jīng)系統(tǒng)的計算模擬生物神經(jīng)系統(tǒng)的計算模擬 (實際上是一個很好的學(xué)習(xí)系統(tǒng)的例子實際上是一個很好的學(xué)習(xí)系統(tǒng)的例子)l海量并行計算技術(shù)使得性能大大提高海量并行計算技術(shù)使得性能大大提高l最早的神經(jīng)網(wǎng)絡(luò)算法為最早的神經(jīng)網(wǎng)絡(luò)算法為 1959由由Rosenblatt提出提出l基本結(jié)構(gòu)基本結(jié)構(gòu)神經(jīng)元結(jié)構(gòu)神經(jīng)元結(jié)構(gòu) k-f加權(quán)

39、和加權(quán)和輸入輸入向量向量X輸出輸出 y激活函數(shù)激活函數(shù)權(quán)重權(quán)重向量向量 ww0w1wnx0 x1xn)sign(yExampleFor n0ikiixw多層感知系統(tǒng)多層感知系統(tǒng)Output nodesInput nodesHidden nodesOutput vectorInput vector: xiwijijiijjOwIjIjeO11)(1 (jjjjjOTOOErrjkkkjjjwErrOOErr)1 (ijijijOErrlww)(jjjErrl)(計算實例計算實例l一個訓(xùn)練樣本一個訓(xùn)練樣本X=1,0,1,輸出為輸出為1lX1=1,x2=0,x3=1,w14=0.2,w15=-0.3

40、,w24=0.4,w25=0.1,w34=-.5,w35=0.2,w46=-0.3,w56=-0.2,l偏置值偏置值:節(jié)點節(jié)點4:-0.4,節(jié)點節(jié)點5:0.2,節(jié)點節(jié)點6:0.1l學(xué)習(xí)率設(shè)為學(xué)習(xí)率設(shè)為0.9l節(jié)點節(jié)點4:輸入值輸入值:w14*x1+w24*x2+w34*x3+節(jié)點節(jié)點4的偏置的偏置=1*0.2+0.4*0-0.5*1-0.4=-0.7輸出值輸出值: 可得可得0.332l同理同理: 節(jié)點節(jié)點5輸入值輸入值0.1,輸出值輸出值0.525l節(jié)點節(jié)點6: 輸入值輸入值:w46*o4+w56*o5+節(jié)點節(jié)點6的偏置的偏置=-0.3*0.332-0.2*0.525+0.1=-0.105輸出

41、值輸出值:0.474計算實例計算實例誤差計算誤差計算l節(jié)點節(jié)點6:0.474*(1-0.474)*(1-0.474)=0.1311l節(jié)點節(jié)點5:0.525*(1-0.525)*0.1311*(-0.2)=-0.0065l同理節(jié)點同理節(jié)點4誤差為誤差為:-0.0087)(1 (jjjjjOTOOErrjkkkjjjwErrOOErr)1(更新權(quán)值和偏置值更新權(quán)值和偏置值lW46:-0.3+(0.9)(0.1311)(0.332)=-0.261l其他其他Wij同理同理l節(jié)點節(jié)點6的偏置的偏置:0.1+(0.9)*(0.1311)=0.218l其他偏置同理其他偏置同理ijijijOErrlww)(j

42、jjErrl)(終止條件終止條件l對所有樣本作一次掃描稱為一個周期對所有樣本作一次掃描稱為一個周期l終止條件終止條件:對前一周期所有對前一周期所有Wij的修改值都小于某個指的修改值都小于某個指定的閾值定的閾值;或超過預(yù)先指定的周期數(shù)或超過預(yù)先指定的周期數(shù).l防止訓(xùn)練過度防止訓(xùn)練過度前饋神經(jīng)網(wǎng)絡(luò)前饋神經(jīng)網(wǎng)絡(luò)l前饋網(wǎng)絡(luò)的表達(dá)能力l布爾函數(shù)。任何布爾函數(shù)可以被具有兩層單元的網(wǎng)絡(luò)準(zhǔn)確表示，盡管對于最壞的情況，所需隱藏單元的數(shù)量隨著網(wǎng)絡(luò)輸入數(shù)量的增加指數(shù)級增長。 l連續(xù)函數(shù)。任何有界的連續(xù)函數(shù)可以由一個兩層的網(wǎng)絡(luò)以任意小的誤差逼近。這個理論適用于隱藏層使用sigmoid單元、輸出層使用（非閾值的）線性單

43、元的網(wǎng)絡(luò)。所需的隱藏單元數(shù)量依賴于要逼近的函數(shù)。l任意函數(shù)。任意函數(shù)可以被一個有三層單元的網(wǎng)絡(luò)以任意精度逼近。與前面相同，輸出層使用線性單元，兩個隱藏層使用sigmoid單元，每一層所需的單元數(shù)量一般不確定。神經(jīng)網(wǎng)絡(luò)特點神經(jīng)網(wǎng)絡(luò)特點l優(yōu)點優(yōu)點l有很強的非線性擬合能力，可映射任意復(fù)雜的非線性關(guān)系。有很強的非線性擬合能力，可映射任意復(fù)雜的非線性關(guān)系。l學(xué)習(xí)規(guī)則簡單，便于計算機實現(xiàn)。學(xué)習(xí)規(guī)則簡單，便于計算機實現(xiàn)。l具有很強的魯棒性、記憶能力以及強大的自學(xué)習(xí)能力。具有很強的魯棒性、記憶能力以及強大的自學(xué)習(xí)能力。 l缺點缺點l最嚴(yán)重的問題是沒能力來解釋自己的推理過程和推理依據(jù)。最嚴(yán)重的問題是沒能力來解釋

44、自己的推理過程和推理依據(jù)。l不能向用戶提出必要的詢問，而且當(dāng)數(shù)據(jù)不充分的時候，不能向用戶提出必要的詢問，而且當(dāng)數(shù)據(jù)不充分的時候，神經(jīng)網(wǎng)絡(luò)就無法進(jìn)行工作。神經(jīng)網(wǎng)絡(luò)就無法進(jìn)行工作。 l把一切問題的特征都變?yōu)閿?shù)字，把一切推理都變?yōu)閿?shù)值計把一切問題的特征都變?yōu)閿?shù)字，把一切推理都變?yōu)閿?shù)值計算，其結(jié)果勢必是丟失信息。算，其結(jié)果勢必是丟失信息。l理論和學(xué)習(xí)算法還有待于進(jìn)一步完善和提高。理論和學(xué)習(xí)算法還有待于進(jìn)一步完善和提高。 應(yīng)用應(yīng)用l適合神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)的問題適合神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)的問題 l實例是用很多實例是用很多“屬性屬性-值值”對表示的。對表示的。 l目標(biāo)函數(shù)的輸出可能是離散值、實數(shù)值或者由若干目標(biāo)函數(shù)的輸出可

45、能是離散值、實數(shù)值或者由若干實數(shù)屬性或離散屬性組成的向量。實數(shù)屬性或離散屬性組成的向量。 l訓(xùn)練數(shù)據(jù)可能包含錯誤。訓(xùn)練數(shù)據(jù)可能包含錯誤。 l可容忍長時間的訓(xùn)練。可容忍長時間的訓(xùn)練。 l可能需要快速求出目標(biāo)函數(shù)值?？赡苄枰焖偾蟪瞿繕?biāo)函數(shù)值。 l人類能否理解學(xué)到的目標(biāo)函數(shù)是不重要的。人類能否理解學(xué)到的目標(biāo)函數(shù)是不重要的。實驗實驗l使用使用Clementine進(jìn)行神經(jīng)網(wǎng)絡(luò)分類挖掘進(jìn)行神經(jīng)網(wǎng)絡(luò)分類挖掘（工具使用參見補充教材）（工具使用參見補充教材）主要內(nèi)容主要內(nèi)容l分類與預(yù)測的基本概念分類與預(yù)測的基本概念l決策樹分類決策樹分類l實例：移動通信客戶流失分析系統(tǒng)實例：移動通信客戶流失分析系統(tǒng)l神經(jīng)網(wǎng)絡(luò)神

46、經(jīng)網(wǎng)絡(luò)l其他分類方法其他分類方法l預(yù)測預(yù)測（回歸）（回歸）其它分類方法其它分類方法l貝葉斯（貝葉斯（Bayesian）分類）分類lk-臨近分類臨近分類l基于案例的推理基于案例的推理l遺傳算法遺傳算法l粗糙集理論粗糙集理論l模糊集方法模糊集方法分類的準(zhǔn)確性：評估錯誤率分類的準(zhǔn)確性：評估錯誤率l數(shù)據(jù)分區(qū)數(shù)據(jù)分區(qū):訓(xùn)練訓(xùn)練-測試數(shù)據(jù)測試數(shù)據(jù)l將一個數(shù)據(jù)集合分成兩個獨立的數(shù)據(jù)集。例如：將一個數(shù)據(jù)集合分成兩個獨立的數(shù)據(jù)集。例如：訓(xùn)練數(shù)據(jù)訓(xùn)練數(shù)據(jù) (2/3), 測試數(shù)據(jù)測試數(shù)據(jù)(1/3)l通常應(yīng)用于大量數(shù)據(jù)樣本的數(shù)據(jù)集通常應(yīng)用于大量數(shù)據(jù)樣本的數(shù)據(jù)集l交叉驗證交叉驗證l將一個數(shù)據(jù)集合分成若干個子樣本集將一個

47、數(shù)據(jù)集合分成若干個子樣本集l用用k-1個子樣本作為訓(xùn)練數(shù)據(jù)，個子樣本作為訓(xùn)練數(shù)據(jù)，1個子樣本作為個子樣本作為測試數(shù)據(jù)測試數(shù)據(jù)l每一個數(shù)據(jù)集合具有合適的寬度每一個數(shù)據(jù)集合具有合適的寬度分類的準(zhǔn)確性：混淆矩陣分類的準(zhǔn)確性：混淆矩陣l混淆矩陣（混淆矩陣（confusion matrix ）用來作為分類規(guī)則特征）用來作為分類規(guī)則特征的表示，它包括了每一類的樣本個數(shù)，包括正確的和錯誤的表示，它包括了每一類的樣本個數(shù)，包括正確的和錯誤的分類。的分類。l主對角線給出了每一類正確分類的樣本的個數(shù)，非對角線主對角線給出了每一類正確分類的樣本的個數(shù)，非對角線上的元素則表示未被正確分類的樣本個數(shù)上的元素則表示未被正

48、確分類的樣本個數(shù)實際的類實際的類預(yù)預(yù)測測的的類類A A類類B B類類C C類類總計總計A A類類4545235050B B類類10383825050C C類類4640405050總計總計5959464645451501503個類的混淆矩陣個類的混淆矩陣分類的準(zhǔn)確性：收益圖分類的準(zhǔn)確性：收益圖查全率分析圖：X軸：按離網(wǎng)傾向評分從大到小排序后的客戶占目標(biāo)客戶人數(shù)的百分比；Y軸：前x%的客戶中被準(zhǔn)確預(yù)測為離網(wǎng)的客戶占目標(biāo)客戶中離網(wǎng)總?cè)藬?shù)的百分比，即查全率。 Lift分析圖：X軸：按離網(wǎng)傾向評分從大到小排序后的客戶占目標(biāo)客戶人數(shù)的百分比；Y軸：命中率的提升倍數(shù)。 聚類分析聚類分析聚類分析聚類分析l什么

49、是聚類分析什么是聚類分析?l劃分方法（劃分方法（Partitioning Methods）l分層方法分層方法l基于密度的方法基于密度的方法l異常分析異常分析什么是聚類分析什么是聚類分析? ?l簇（簇（Cluster）:一個數(shù)據(jù)對象的集合一個數(shù)據(jù)對象的集合l在同一個簇中，對象之間具有盡可能大的相似性；在同一個簇中，對象之間具有盡可能大的相似性；l不同簇的對象之間具有盡可能大的相異性。不同簇的對象之間具有盡可能大的相異性。l聚類分析聚類分析l把一個給定的數(shù)據(jù)對象集合分成不同的簇，即把一個給定的數(shù)據(jù)對象集合分成不同的簇，即“ 物以類聚物以類聚 ”；l聚類是一種無監(jiān)督分類法聚類是一種無監(jiān)督分類法: 沒

50、有預(yù)先指定的類別標(biāo)識；沒有預(yù)先指定的類別標(biāo)識；l典型的應(yīng)用典型的應(yīng)用l作為一個獨立的分析工具，用于了解數(shù)據(jù)的分布；作為一個獨立的分析工具，用于了解數(shù)據(jù)的分布； l作為其它算法的一個數(shù)據(jù)預(yù)處理步驟；作為其它算法的一個數(shù)據(jù)預(yù)處理步驟；應(yīng)用聚類分析的例子應(yīng)用聚類分析的例子l市場銷售市場銷售: 幫助市場人員發(fā)現(xiàn)客戶數(shù)據(jù)庫中不同群體，然后利用這些知識幫助市場人員發(fā)現(xiàn)客戶數(shù)據(jù)庫中不同群體，然后利用這些知識來開展一個目標(biāo)明確的市場計劃；來開展一個目標(biāo)明確的市場計劃；l土地使用土地使用: 在一個陸地觀察數(shù)據(jù)庫中標(biāo)識那些土地使用相似的地區(qū)；在一個陸地觀察數(shù)據(jù)庫中標(biāo)識那些土地使用相似的地區(qū)；l保險保險: 對購買了

51、汽車保險的客戶，標(biāo)識那些有較高平均賠償成本的客戶；對購買了汽車保險的客戶，標(biāo)識那些有較高平均賠償成本的客戶；l城市規(guī)劃城市規(guī)劃: 根據(jù)類型、價格、地理位置等來劃分不同類型的住宅；根據(jù)類型、價格、地理位置等來劃分不同類型的住宅；l地震研究地震研究: 根據(jù)地質(zhì)斷層的特點把已觀察到的地震中心分成不同的類；根據(jù)地質(zhì)斷層的特點把已觀察到的地震中心分成不同的類；如何評價一個好的聚類方法如何評價一個好的聚類方法? ?l一個好的聚類方法要能產(chǎn)生高質(zhì)量的聚類結(jié)一個好的聚類方法要能產(chǎn)生高質(zhì)量的聚類結(jié)果果簇，這些簇具備以下兩個特征：簇，這些簇具備以下兩個特征：l簇內(nèi)極大相似性簇內(nèi)極大相似性l簇間極小相似性簇間極小相

52、似性 l聚類結(jié)果的好壞取決于該聚類方法采用的相似聚類結(jié)果的好壞取決于該聚類方法采用的相似性評估方法以及該方法的具體實現(xiàn)；性評估方法以及該方法的具體實現(xiàn)；l聚類方法的好壞還取決與該方法是能發(fā)現(xiàn)某些聚類方法的好壞還取決與該方法是能發(fā)現(xiàn)某些還是所有的隱含模式；還是所有的隱含模式；聚類分析中的數(shù)據(jù)類型聚類分析中的數(shù)據(jù)類型l如何度量對象間的距離？如何度量對象間的距離？l歐幾里德距離 l曼哈頓距離 l明考斯基距離聚類分析聚類分析l什么是聚類分析什么是聚類分析?l劃分方法（劃分方法（Partitioning Methods）l分層方法分層方法l基于密度的方法基于密度的方法l異常分析異常分析 劃分方法劃分方法

53、: 基本概念基本概念l劃分方法劃分方法: 將一個包含將一個包含n個數(shù)據(jù)對象的數(shù)據(jù)庫組織成個數(shù)據(jù)對象的數(shù)據(jù)庫組織成k個個劃分（劃分（k=n），其中每個劃分代表一個簇（），其中每個劃分代表一個簇（Cluster）。）。l給定一個給定一個k，要構(gòu)造出，要構(gòu)造出k個簇，并滿足采用的劃分準(zhǔn)則：個簇，并滿足采用的劃分準(zhǔn)則：l全局最優(yōu)全局最優(yōu):盡可能的列舉所有的劃分；盡可能的列舉所有的劃分；l啟發(fā)式方法啟發(fā)式方法: k-均值和均值和k-中心點算法中心點算法lk-均值均值 (MacQueen67):由簇的中心來代表簇；由簇的中心來代表簇；lk-中心點或中心點或 PAM (Partition around me

54、doids) (Kaufman & Rousseeuw87): 每個簇由簇中的某個每個簇由簇中的某個數(shù)據(jù)對象來代表。數(shù)據(jù)對象來代表。 K-均值算法均值算法l給定給定k，算法的處理流程如下，算法的處理流程如下:1.隨機的把所有對象分配到隨機的把所有對象分配到k個非空的簇中；個非空的簇中；2.計算每個簇的平均值，并用該平均值代表相應(yīng)的計算每個簇的平均值，并用該平均值代表相應(yīng)的簇；簇；3.將每個對象根據(jù)其與各個簇中心的距離，重新分將每個對象根據(jù)其與各個簇中心的距離，重新分配到與它最近的簇中；配到與它最近的簇中； 4.回到第二步，直到不再有新的分配發(fā)生?；氐降诙剑钡讲辉儆行碌姆峙浒l(fā)生。K-均值算法圖示均值算法圖示0123456789100123456789100123456789100123456789100123456789100123456