VFDT是一种基于Hoeffding不等式建立决课件

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

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

‏

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

‏

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

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