1分類和流數(shù)據(jù)分類2基于貝葉斯的分類3基于決策樹的分類4集成分類5小結(jié)批數(shù)據(jù)分類概述分類和流數(shù)據(jù)分類2批數(shù)據(jù)的分類什么是分類？3貓科動(dòng)物

犬科動(dòng)物

熊科動(dòng)物訓(xùn)練數(shù)據(jù)新動(dòng)物屬于哪一類？批數(shù)據(jù)的分類4IFrank=‘professor’ORyears>

6THENtenured=

‘yes’分類器（模型）IF(rank!=’professor’)AND(years

<6)THENtenured=

‘no’訓(xùn)練數(shù)據(jù)集NAMERANKYEARSTENUREDMikeAssistant

Prof3noMaryAssistant

Prof7yesBillProfessor2yesJimAssociate

Prof7yesDaveAssistant

Prof6noAnneAssociate

Prof3no類屬性預(yù)測(cè)屬性測(cè)試數(shù)據(jù)集NAMERANKYEARSTENUREDJeffProfessor4?PatrickAssistant

Professor8?MariaAssistant

Professor2?Tenured???Tenured?Tenured?模型構(gòu)建預(yù)測(cè)分類算法有限訓(xùn)練集D={(x,y)}，其中y={y1,y2,…,yk},|D|=n，找出y=f(x)，對(duì)未遇見樣本x

預(yù)測(cè)y

值批數(shù)據(jù)的分類分類和聚類的區(qū)別有監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)常見的分類問題垃圾分類：干垃圾、濕垃圾智慧安防：人臉識(shí)別智慧醫(yī)療：醫(yī)療影像識(shí)別互聯(lián)網(wǎng)服務(wù)：拍照識(shí)花……5批數(shù)據(jù)的分類常用分類算法K近鄰法（k-NearestNeighbor）決策樹（Decision

Trees）支持向量機(jī)（Support

Vector

Machine）6KNN支持向量機(jī)決策樹最大邊距決策邊界理論信息論熵模型距離模型可以無需標(biāo)記樣本需要標(biāo)記樣本需要標(biāo)記樣本批數(shù)據(jù)的分類常用分類算法（續(xù)）邏輯回歸（Logistic

Regression）人工神經(jīng)網(wǎng)絡(luò)（ArtificialNeuralNetwork）7神經(jīng)網(wǎng)絡(luò)邏輯回歸從線性回歸到

非線性回歸需要標(biāo)記樣本需要標(biāo)記樣本流數(shù)據(jù)分類概述分類和流數(shù)據(jù)分類8流數(shù)據(jù)分類的場(chǎng)景社交網(wǎng)站數(shù)據(jù)流的情感分類9流數(shù)據(jù)分類的場(chǎng)景新聞聚合網(wǎng)站的話題分類10流數(shù)據(jù)分類的場(chǎng)景詐騙、騷擾、推銷電話檢測(cè)11關(guān)于防范和打擊電信網(wǎng)絡(luò)詐騙犯罪的通告

電信網(wǎng)絡(luò)詐騙犯罪是嚴(yán)重影響人民群眾合法權(quán)益、破壞社會(huì)和諧穩(wěn)定的社會(huì)公害，必須堅(jiān)決依法嚴(yán)懲。為切實(shí)保障廣大人民群眾合法權(quán)益，維護(hù)社會(huì)和諧穩(wěn)定，根據(jù)《中華人民共和國(guó)刑法》《中華人民共和國(guó)刑事訴訟法》《全國(guó)人民代表大會(huì)常務(wù)委員會(huì)關(guān)于加強(qiáng)網(wǎng)絡(luò)信息保護(hù)的決定》等有關(guān)規(guī)定，現(xiàn)就防范和打擊電信網(wǎng)絡(luò)詐騙犯罪相關(guān)事項(xiàng)通告如下：流數(shù)據(jù)分類批數(shù)據(jù)分類將整個(gè)數(shù)據(jù)集劃分為訓(xùn)練集、測(cè)試集、驗(yàn)證集，訓(xùn)練并驗(yàn)證分類模型（標(biāo)記樣本）當(dāng)模型性能下降時(shí)，使用新數(shù)據(jù)構(gòu)造新訓(xùn)練集、測(cè)試集、驗(yàn)證集，并重新生成模型（重新標(biāo)記樣本）適合目標(biāo)數(shù)據(jù)特征固定場(chǎng)景流數(shù)據(jù)存在概念漂移可以使用新數(shù)據(jù)增量更新已有的模型但無法離線標(biāo)記樣本流數(shù)據(jù)存在資源限制單遍數(shù)據(jù)掃描（非隨機(jī)訪問）

歷史數(shù)據(jù)無法重復(fù)遍歷12訓(xùn)練集測(cè)試集驗(yàn)證集概念漂移：特征分布隨時(shí)間而變化流數(shù)據(jù)分類流數(shù)據(jù)分類問題無限長(zhǎng)度二元組序列(x,y)，其中y={y1,y2,…,yk}，

|D|=n，找出y=f(x)，對(duì)未遇見樣本x

預(yù)測(cè)y

值非穩(wěn)態(tài)數(shù)據(jù)分布變化概念漂移13分類邊界從b1漂移到b2，再漂移到b3流數(shù)據(jù)分類的評(píng)價(jià)分類和流數(shù)據(jù)分類14基線分類器隨機(jī)分類器隨機(jī)將樣本分配給各個(gè)類多數(shù)類分類器將樣本預(yù)測(cè)為當(dāng)前最頻繁的類需要為所有類維護(hù)一個(gè)計(jì)數(shù)器（頻繁項(xiàng)）不變分類器自相關(guān)性用前一個(gè)樣本的標(biāo)簽預(yù)測(cè)當(dāng)前樣本的標(biāo)簽15設(shè)計(jì)的分類器不能“瞎猜”評(píng)價(jià)方式：是否比基線分類器好？評(píng)價(jià)指標(biāo)使用與訓(xùn)練集不同的測(cè)試集評(píng)價(jià)分類器的質(zhì)量對(duì)于測(cè)試集中的每個(gè)樣本，已知其真實(shí)的類標(biāo)簽對(duì)比分類器的預(yù)測(cè)類和真實(shí)類正樣本與負(fù)樣本正樣本Positive：關(guān)注的主類樣本（如行人檢測(cè)中的人）負(fù)樣本Negative：所有其他類樣本混淆矩陣是評(píng)價(jià)分類器性能的工具m分類問題的混淆矩陣m×m16C1C2TotalsC1TP(true

positive)FN(false

negative)PC2FP

(false

positive)TN(true

negative)NTotalsP’N’真實(shí)類預(yù)測(cè)類評(píng)價(jià)指標(biāo)準(zhǔn)確率/識(shí)別率測(cè)試集中正確分類樣本的比例錯(cuò)誤率/誤分類率測(cè)試集中錯(cuò)誤分類樣本的比例精確率預(yù)測(cè)正樣本中真實(shí)正樣本的比例召回率真實(shí)的正樣本被正確預(yù)測(cè)的比例Fβ-Measure精確率和召回率的調(diào)和均值17C1C2totalsC1TP(true

positive)FN(false

negative)PC2FP(false

positive)TN(true

negative)NTotalsP’N’

真實(shí)類預(yù)測(cè)類

評(píng)價(jià)指標(biāo)例：計(jì)算準(zhǔn)確率、錯(cuò)誤率、精確率、召回率、F1-Measure18

classesbuy_computer=

yesbuy_computer=

nototalbuy_computer=

yes6954467000buy_computer=

no41225883000total7366263410000

TPFNFPTN6954+258810000=95.42%412+4610000=4.58%69546954+412=94.41%69546954+46=99.34%

2×69542×6954+412+46=96.81%評(píng)價(jià)指標(biāo)ROC（ReceiverOperatorCharacteristic）曲線X軸為假正率：在所有實(shí)際負(fù)樣本中，

被錯(cuò)誤判斷為正樣本的比率Y軸為真正率：在所有實(shí)際正樣本中，

被正確判斷為正樣本的比率如何評(píng)價(jià)分類器？曲線距離左上角越近，證明分類器效果越好19好于隨機(jī)分類器差于隨機(jī)分類器遍歷所有的閾值

評(píng)價(jià)指標(biāo)AUC（AreaUndertheROCCurve）ROC曲線下面積物理意義：假設(shè)分類器輸出樣本屬于正樣本的分值，AUC表示任取一對(duì)正負(fù)樣本，正樣本大于負(fù)樣本分值的概率如何評(píng)價(jià)分類器性能是否變化？20AUCAUC=1完美分類器0.5<AUC<1優(yōu)于隨機(jī)分類器0<AUC<0.5差于隨機(jī)分類器80%AUC的變化趨勢(shì)評(píng)價(jià)指標(biāo)前兆（Prequential）AUC使用帶滑動(dòng)窗口的紅黑樹計(jì)算具有遺忘特征的AUC適合于流計(jì)算場(chǎng)景21捕獲突然的概念漂移無概念漂移PrequentialAUC:propertiesoftheareaundertheROCcurvefordatastreamswithconceptdrift評(píng)價(jià)指標(biāo)

22Kappa值分類器性能0%-20%差21%-40%一般41%-60%中等61%-80%良好81%-100%幾乎完美

批數(shù)據(jù)的評(píng)價(jià)方法保留式驗(yàn)證將數(shù)據(jù)隨機(jī)分成兩個(gè)獨(dú)立的集合約2/3用于模型構(gòu)建，1/3用于模型評(píng)價(jià)k折交叉驗(yàn)證（一般k=10）將數(shù)據(jù)集分為k個(gè)不相交的子集D1,…,Dk進(jìn)行k

輪訓(xùn)練和測(cè)試第i

輪中，將Di

作為作為測(cè)試集，

其他作為訓(xùn)練集準(zhǔn)確率為所有輪準(zhǔn)確率的平均值自助法（.632自助法）假設(shè)給定的數(shù)據(jù)集包含d

個(gè)樣本該數(shù)據(jù)集有放回抽樣

m

次，產(chǎn)生m

個(gè)樣本的訓(xùn)練集，沒有進(jìn)入該訓(xùn)練集的樣本最終形成測(cè)試集23數(shù)據(jù)樣本豐富時(shí)適用數(shù)據(jù)樣本有限時(shí)適用數(shù)據(jù)樣本非正態(tài)分布流數(shù)據(jù)的評(píng)價(jià)方法保留式驗(yàn)證（Holdout）數(shù)據(jù)流用于不斷訓(xùn)練模型保留一個(gè)驗(yàn)證子集用于評(píng)價(jià)模型交織式先測(cè)試后訓(xùn)練（Interleavedtest-then-train）每個(gè)樣本都先用于測(cè)試模型，再用于訓(xùn)練模型前兆序列（Prequential）與交織式先測(cè)試后訓(xùn)練類似但通過使用滑動(dòng)窗口或衰減因子，使得

新樣本對(duì)模型性能評(píng)價(jià)的重要性更大交織塊（Interleavedchunks）與交織式先測(cè)試后訓(xùn)練類似面向數(shù)據(jù)塊序列24難以確定驗(yàn)證子集！tnow1.測(cè)試模型2.訓(xùn)練模型分類正確嗎？流數(shù)據(jù)的評(píng)價(jià)方法k折分布式分裂驗(yàn)證每個(gè)到達(dá)樣本以1/k概率用于測(cè)試

所有分類器每個(gè)到達(dá)樣本以1-1/k概率用于訓(xùn)練

一個(gè)分類器適用于樣本量大的場(chǎng)景k

折分布式交叉驗(yàn)證每個(gè)到達(dá)樣本隨機(jī)選擇

一個(gè)分類器進(jìn)行測(cè)試，

其他分類器進(jìn)行訓(xùn)練適用于樣本量小的場(chǎng)景25測(cè)試分類器1、2訓(xùn)練分類器2訓(xùn)練分類器1測(cè)試分類器1、訓(xùn)練分類器2測(cè)試分類器2、訓(xùn)練分類器1流數(shù)據(jù)的評(píng)價(jià)方法c×k

分布式交叉驗(yàn)證擴(kuò)展k

折分布式交叉驗(yàn)證分類器分為c

組，每組k個(gè)對(duì)于每組分類器，每個(gè)到達(dá)樣本隨機(jī)選擇一個(gè)分類器進(jìn)行測(cè)試，其他分類器進(jìn)行訓(xùn)練適用于樣本量小的場(chǎng)景26……分類器組1分類器組c分類器C1,1分類器C1,2分類器Cc,1分類器Cc,2……訓(xùn)練測(cè)試訓(xùn)練測(cè)試1分類和流數(shù)據(jù)分類2基于貝葉斯的分類3基于決策樹的分類4集成分類5小結(jié)貝葉斯分類流數(shù)據(jù)28貝葉斯公式

29后驗(yàn)概率類的先驗(yàn)概率預(yù)測(cè)器的先驗(yàn)概率似然函數(shù)

今天晴天，昨天出現(xiàn)晚霞的概率概率分類器建立分類的概率模型判別模型30判別式概率分類器輸入x條件下，輸出特定分類的概率概率分類器建立分類的概率模型判別模型的示例31概率分類器建立分類的概率模型生成模型32類1的生成概率模型類L的生成概率模型特定分類c條件下，輸入x屬于該分類的概率概率分類器建立分類的概率模型生成模型的示例33概率分類器最大后驗(yàn)概率的分類準(zhǔn)則MAP：MaximumAPosteriorx

屬于c*的條件為判別模型可直接使用MAP生成模型使用貝葉斯定理轉(zhuǎn)換為后驗(yàn)概率34樸素貝葉斯分類器貝葉斯分類器樸素貝葉斯分類器假設(shè)所有的輸入屬性條件獨(dú)立35對(duì)所有類為常數(shù)需最大化，但聯(lián)合概率難以學(xué)習(xí)樸素貝葉斯分類器

36樸素貝葉斯分類器—舉例37訓(xùn)練階段OutlookPlay=YesPlay=NoSunny2/93/5Overcast4/90/5Rain3/92/5TemperaturePlay=YesPlay=NoHot2/92/5Mild4/92/5Cool3/91/5HumidityPlay=YesPlay=NoHigh3/94/5Normal6/91/5WindPlay=YesPlay=NoStrong3/93/5Weak6/92/5P(Play=Yes)=9/14P(Play=No)=5/14樸素貝葉斯分類器—舉例38測(cè)試階段查表MAP規(guī)則P(Outlook=Sunny|Play=No)=3/5P(Temperature=Cool|Play==No)=1/5P(Huminity=High|Play=No)=4/5P(Wind=Strong|Play=No)=3/5P(Play=No)=5/14P(Outlook=Sunny|Play=Yes)=2/9P(Temperature=Cool|Play=Yes)=3/9P(Huminity=High|Play=Yes)=3/9P(Wind=Strong|Play=Yes)=3/9P(Play=Yes)=9/14P(Yes|x’):[P(Sunny|Yes)P(Cool|Yes)P(High|Yes)P(Strong|Yes)]P(Play=Yes)=0.0053P(No|x’):[P(Sunny|No)P(Cool|No)P(High|No)P(Strong|No)]P(Play=No)=0.0206x’=(Outlook=Sunny,Temperature=Cool,Humidity=High,Wind=Strong)P(Yes|x’)<P(No|x’)，預(yù)測(cè)結(jié)果為No樸素貝葉斯分類器—總結(jié)39

1聚類和流數(shù)據(jù)聚類2基于貝葉斯的分類3基于決策樹的分類4集成分類5小結(jié)決策樹批處理41決策樹訓(xùn)練集：D={(x,y)}樣本屬性：x=<x1,x2,…,xd>類標(biāo)簽：y={y1,y2,…,yk}目標(biāo)：訓(xùn)練函數(shù)y=f(x)決策樹模型節(jié)點(diǎn)對(duì)樣本屬性進(jìn)行測(cè)試葉子節(jié)點(diǎn)對(duì)類標(biāo)簽進(jìn)行預(yù)測(cè)42訓(xùn)練集決策樹基礎(chǔ)算法(ID3,Quinlan1986)按照自上而下迭代的分而治之開始時(shí)，所有的訓(xùn)練樣本都位于根節(jié)點(diǎn)最優(yōu)屬性？劃分結(jié)果的純度盡量高，盡量使

劃分內(nèi)的所有實(shí)例都屬于一個(gè)類信息增益、增益率、Gini系數(shù)43主循環(huán)A←下個(gè)節(jié)點(diǎn)的最優(yōu)決策屬性將A作為節(jié)點(diǎn)的決策屬性對(duì)于A的每個(gè)值，創(chuàng)建子節(jié)點(diǎn)將訓(xùn)練樣本在決策樹上傳送到葉子節(jié)點(diǎn)如果訓(xùn)練樣本可被完美分類，則結(jié)束；否則在新的葉子結(jié)點(diǎn)上迭代決策樹：信息增益ID3算法使用信息增益作為屬性選擇指標(biāo)使用信息熵(entropy)來評(píng)價(jià)數(shù)據(jù)的純度屬性A的信息增益Gain(S,A)樣本集S由屬性A

分裂帶來的熵的減少量Gain(S,A)越大，表明屬性A分裂后的數(shù)據(jù)純度越高

（A分裂后的熵更小了）44分裂前A分裂后應(yīng)該選擇信息增益大的屬性進(jìn)行分裂

決策樹：熵S為二分類問題的正負(fù)樣本集合p+：S中正樣本的比例p-：S中負(fù)樣本的比例熵表示S的不純度：例：熵為0，表示所有的樣本屬于同一個(gè)類熵為1，表示正負(fù)樣本數(shù)量相同45Entropy(S

)

p

log2

(

p

)

p

log2

(

p

)

決策樹：示例選擇哪個(gè)屬性進(jìn)行分裂？460.78850.892分裂后的熵變小→向數(shù)據(jù)純度更高的方向分裂Hoeffding樹流數(shù)據(jù)47Hoeffding樹在流數(shù)據(jù)處理場(chǎng)景下無需觀察整個(gè)數(shù)據(jù)集（數(shù)據(jù)流也無法觀察整個(gè)數(shù)據(jù)集）是否可以利用流過節(jié)點(diǎn)的少量樣本來選擇其最優(yōu)分裂屬性？例如：使用最初的幾個(gè)樣本來決定根節(jié)點(diǎn)的分裂面臨的問題是：需要多少個(gè)樣本？Hoeffding界以極大概率保證分裂屬性的選擇是最優(yōu)的Hoeffding樹的變形快速?zèng)Q策樹VeryFastDecisionTree,VFDT概念自適應(yīng)快速?zèng)Q策樹Concept-adaptingVFDT,CVFDT48Hoeffding界

49

Hoeffding界

50Hoeffding樹算法簡(jiǎn)介51啟發(fā)式指標(biāo)G()

葉子節(jié)點(diǎn)使用多數(shù)類分類器Hoeffding樹的特性使用有限的內(nèi)存資源只在每個(gè)葉子存儲(chǔ)必要的統(tǒng)計(jì)量用于分裂決策與看到的樣本數(shù)量相獨(dú)立增量式的構(gòu)建樹結(jié)構(gòu)每個(gè)樣本僅處理一次以統(tǒng)計(jì)學(xué)支撐的穩(wěn)定決策每個(gè)節(jié)點(diǎn)都能收到構(gòu)成穩(wěn)定決策所需數(shù)量的樣本缺點(diǎn)：無法保證在有限時(shí)間內(nèi)產(chǎn)生分裂決策兩個(gè)屬性的性能極其相似？52Hoeffding樹的改進(jìn)

53概念自適應(yīng)快速?zèng)Q策樹CVFDT流數(shù)據(jù)54CVFDT簡(jiǎn)介基于滑動(dòng)窗口的模型更新使模型與滑動(dòng)窗口中的模型一致為應(yīng)對(duì)概念漂移構(gòu)建備用分支當(dāng)備用分支準(zhǔn)確度足夠時(shí)取代原分支55t溫度濕度風(fēng)速跑步健身健步走打球休息遺忘：減少流經(jīng)節(jié)點(diǎn)的統(tǒng)計(jì)量增加流經(jīng)節(jié)點(diǎn)統(tǒng)計(jì)量、屬性分裂、創(chuàng)建備用子樹空氣質(zhì)量備用子樹CVFDT算法

56與VFDT的區(qū)別：保持模型與滑動(dòng)窗口內(nèi)的數(shù)據(jù)一致CVFDT算法

57與VFDT的區(qū)別：CVFDT在每個(gè)節(jié)點(diǎn)都維護(hù)統(tǒng)計(jì)量，而不只是在葉子CVFDT算法

58與VFDT的區(qū)別：必要時(shí)在內(nèi)部節(jié)點(diǎn)維護(hù)備用子樹1分類和流數(shù)據(jù)分類2基于貝葉斯的分類3基于決策樹的分類4集成分類5小結(jié)集成分類的思想

60如何生成集成分類器通過操縱訓(xùn)練集通過重采樣原始訓(xùn)練集生成多個(gè)訓(xùn)練集每個(gè)訓(xùn)練集學(xué)到一個(gè)分類器如：bagging、boosting通過操