VFDT是一種基于Hoeffding不等式建立決策樹的方法

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

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

?

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

?

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

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