VFDT是一種基于Hoeffding不等式建立決課件

VFDT(VeryFastDecisionTree)?VFDT是一種基于Hoeffding不等式建立決策樹(shù)的方法，透過(guò)不斷地將葉節(jié)點(diǎn)替換為決策節(jié)點(diǎn)而生成，其中每個(gè)葉節(jié)點(diǎn)都保存有關(guān)于屬性值的統(tǒng)計(jì)信息。當(dāng)一個(gè)新樣本到達(dá)後，在樹(shù)的每個(gè)節(jié)點(diǎn)都進(jìn)行劃分測(cè)試，根據(jù)不同的屬性取值進(jìn)入不同的分支，最終到達(dá)樹(shù)的葉節(jié)點(diǎn)。在數(shù)據(jù)到達(dá)葉節(jié)點(diǎn)後，節(jié)點(diǎn)上的統(tǒng)計(jì)信息會(huì)被更新，同時(shí)該節(jié)點(diǎn)基于屬性的測(cè)試值將重新計(jì)算。6/4/20231DataMining:ConceptsandTechniquesVFDT(VeryFastDecisionTree)?

(Cont.)VFDT特性：主要是利用Hoeffding不等式確定葉節(jié)點(diǎn)進(jìn)行劃分所需要的樣本數(shù)目。VFDT所産生的決策樹(shù)在大量減少處理樣本數(shù)目的同時(shí)，能夠保證和用全部樣本所産生的決策樹(shù)具有無(wú)限接近的精確度。VFDT中沒(méi)有處理連續(xù)值屬性的問(wèn)題，同時(shí)也無(wú)法處理概念流。6/4/20232DataMining:ConceptsandTechniquesVFDT(VeryFastDecisionTree)?

?

(Cont.)VFDT與HoeffdingTree比較：速度較快佔(zhàn)記憶體空間較小VFDT與傳統(tǒng)決策樹(shù)比較：兩者正確性相似處理大量資料VFDT時(shí)間花費(fèi)少Examples：處理1.6million資料量傳統(tǒng)決策樹(shù)：花費(fèi)24小時(shí)VFDT決策樹(shù)：花費(fèi)21分鐘VFDT仍然無(wú)法處理概念流6/4/20233DataMining:ConceptsandTechniquesCVFDT(Concept-adaptingVFDT)?由Hulten等人在VFDT的基礎(chǔ)上提出了解決概念流問(wèn)題的演算法—CVFDT。概念流(ConceptDrift)：時(shí)間改變資料流(連續(xù)資料)。合併新資料與去除舊資料。6/4/20234DataMining:ConceptsandTechniquesCVFDT(Concept-adaptingVFDT)?

?

(Cont.)CVFDT：在葉節(jié)點(diǎn)可能會(huì)産生概念流時(shí)，預(yù)先産生一棵備選子樹(shù)，並將新子樹(shù)變得更精確，用新子樹(shù)替代原先的舊子樹(shù)，從而解決了概念流所導(dǎo)致的預(yù)測(cè)性能下降的問(wèn)題。每當(dāng)有新樣本到達(dá)，就把VFDT應(yīng)用到滑動(dòng)窗口(Slidingwindow)上，CVFDT透過(guò)不斷地把VFDT演算法應(yīng)用到固定大小的滑動(dòng)窗口上，從不斷變化的數(shù)據(jù)流上生成決策樹(shù)。執(zhí)行時(shí)間較VFDT少。6/4/20235DataMining:ConceptsandTechniquesEnsembleofClassifiersAlgorithm由wang等人提出了一種利用加權(quán)的多個(gè)分類器挖掘概念漂移數(shù)據(jù)流的方法。系統(tǒng)首先從資料流中產(chǎn)生幾個(gè)分類器，同時(shí)根據(jù)測(cè)試資料集上的分類精度進(jìn)行加權(quán)。集合分類器不但提高了學(xué)習(xí)模型的效率，也提高了分類精度。6/4/20236DataMining:ConceptsandTechniquesEnsembleofClassifiersAlgorithm

(Cont.)集合分類器優(yōu)點(diǎn)：提高了預(yù)測(cè)的精確度由于大部分分類器模型的建立複雜度都是非線性的，因此建立集合分類器比建立單一的分類器要高效得多集合分類器本身就可以使其能夠並行擴(kuò)展和在線分類大數(shù)據(jù)庫(kù)6/4/20237DataMining:ConceptsandTechniquesClusteringEvolvimgDataStreams為了更有效的datastream分群，有以下幾個(gè)方法：計(jì)算與儲(chǔ)存過(guò)去的資料概要應(yīng)用Divide-and-Conquer策略增加進(jìn)來(lái)的datastream分群實(shí)行microclustering和macroclustering分析把stream分群分為on-line和off-line處理6/4/20238DataMining:ConceptsandTechniquesSTREAMSTREAM是用在k-medians問(wèn)題上k-medians是把N個(gè)datapoints聚集為k個(gè)分群，要達(dá)到在points與clustercenter間的sumsquarederror(SSQ)是最低的把相似的points放在相同的分群裡面，分群與分群間的point都不一樣6/4/20239DataMining:ConceptsandTechniquesSTREAM(Cont.)為了達(dá)到高品質(zhì)的分群分析，STREAM以batch方式處理datastream作法：把batch的datapoints聚集為k個(gè)分群藉由被指定到分群的point數(shù)量，把每個(gè)clustercenter做加權(quán)只保留k個(gè)clustercenter的相關(guān)資訊，拋棄points6/4/202310DataMining:ConceptsandTechniquesSTREAM(Cont.)收集足夠的clustercenter後，再把被加權(quán)後的clustercenter分為其它的k個(gè)clustercenter重複做完最後只剩m個(gè)point被保留缺點(diǎn)：對(duì)於發(fā)展中的datastream分群分析功能較少且品質(zhì)較低6/4/202311DataMining:ConceptsandTechniquesCluStream優(yōu)點(diǎn)：對(duì)於發(fā)展中的datastream分群分析功能較多且品質(zhì)較高不浪費(fèi)空間且效率高把分群處理分為on-line和off-line兩部分6/4/202312DataMining:ConceptsandTechniquesCluStream(Cont.)on-line部分：週期性地儲(chǔ)存有關(guān)datastream的統(tǒng)計(jì)資料off-line：以儲(chǔ)存的統(tǒng)計(jì)資料為基礎(chǔ)，回答各式各樣的使用者問(wèn)題6/4/202313DataMining:ConceptsandTechniquesCluStream(Cont.)Micro-cluster統(tǒng)計(jì)有關(guān)資料區(qū)域性的資訊Onlinemicro-clustermaintenance一開(kāi)始產(chǎn)生q個(gè)micro-clusterq通常比naturalcluster的數(shù)量還大6/4/202314DataMining:ConceptsandTechniquesCluStream(Cont.)增