2023學(xué)年完整公開課版數(shù)據(jù)流挖掘

數(shù)據(jù)流挖掘?qū)W習(xí)目標(biāo)2知識目標(biāo)●數(shù)據(jù)平穩(wěn)分布的分類方法●數(shù)據(jù)帶概念漂移分類方法能力目標(biāo)●了解數(shù)據(jù)流漂移挖掘研究現(xiàn)狀●掌握數(shù)據(jù)流挖掘分類方法●掌握數(shù)據(jù)挖掘之?dāng)?shù)據(jù)流處理學(xué)習(xí)任務(wù)3數(shù)據(jù)流挖掘分類方法數(shù)據(jù)流漂移分類研究現(xiàn)狀數(shù)據(jù)挖掘之?dāng)?shù)據(jù)流處理過濾數(shù)據(jù)4數(shù)據(jù)挖掘之?dāng)?shù)據(jù)流處理數(shù)據(jù)流挖掘分類方法目錄數(shù)據(jù)流挖掘分類方法5在數(shù)據(jù)流挖掘分類方法的應(yīng)用上有：電子郵件的區(qū)分、個性化網(wǎng)站、電腦入侵檢測等，因為無法在一個分類器建立完成前獲取到所有適合用來做訓(xùn)練樣本的數(shù)據(jù)，數(shù)據(jù)流挖掘的增量式方法一般都假設(shè)取得的樣本是由平穩(wěn)分布的數(shù)據(jù)中所獲得，但現(xiàn)實世界中，新數(shù)據(jù)的概念可能會隨著時間的延續(xù)而與歷史數(shù)據(jù)產(chǎn)生改變，定義為St={(x，y)|y=f(x)+st}，t=1,2,…代表數(shù)據(jù)集合是由伴隨著時間變化參數(shù)的函數(shù)所產(chǎn)生的，以致相同的條件可能會產(chǎn)生不同的行動，這種概念隨著時間延續(xù)而改變的情形，稱為概念漂移。6VFDTVFDT(veryfastdecisiontree)是一種基于Hoefiding不等式建立決策樹的方法，它通過不斷地將葉節(jié)點替換為決策節(jié)點而生成其中每個葉節(jié)點都保存有關(guān)于屬性值的統(tǒng)計信息，這些統(tǒng)計信息用于計算基于屬性值的測試當(dāng)一個新樣本到達后，在沿著決策樹從上到下遍歷的過程中，它在樹的每個節(jié)點都進行劃分測試，根據(jù)不同的屬性取值進入不同的分支，最終到達樹的葉節(jié)點當(dāng)數(shù)據(jù)到達葉節(jié)點后，節(jié)點上的統(tǒng)計信息就被更新，同時該節(jié)點基于屬性值的測試值就被重新計算，如果統(tǒng)計信息計算顯示測試滿足一定的條件，則該葉節(jié)點變?yōu)闆Q策節(jié)點新的決策節(jié)點根據(jù)屬性的可能取值的數(shù)目產(chǎn)生相應(yīng)數(shù)目的子女葉節(jié)點決策節(jié)點只保存該節(jié)點的劃分測試所需要的信息。7VFDTcVFDT只是在有足夠多樣本情況下才將一個葉節(jié)點轉(zhuǎn)換為決策節(jié)點，這通常需要較多樣本為分類測試樣本，大部分分類策略只是用到類分布信息，而沒有用到屬性值信息，這顯然只用到了可用信息的一部分，只是對樣本分布的粗略近似，另一方面貝葉斯分類不僅考慮類的前驗分布，而且考慮在給定分類的情況下屬性值的條件概率，通過這種方"法可以更多地利用每個葉節(jié)點的可用信息此外，貝葉斯本身就是增量式的，在處理不同類型的數(shù)據(jù)和缺值數(shù)據(jù)方面都有好處。VFDTc提出了解決連續(xù)屬性的方法，但是它在劃分點的選擇上將考慮所有的連續(xù)屬性的可能取值"這帶來了很大的開銷Fayyad等人已經(jīng)證明屬性的兩個緊鄰值只有取不同的分類，其中間點才可能是最佳劃分點，這在VFDTc中并沒有得到應(yīng)用。8NIPDTSmallClassHistograms。主要由離散屬性的類，直方圖構(gòu)成離散屬性的元素數(shù)目不會太多因此每個屬性的類直方圖都不會太大此外，對于那些屬性取值小于指定數(shù)目的連續(xù)屬性也維持一個小尺寸類直方圖。

對于連續(xù)屬性，在處理時的一個問題就是備選劃分節(jié)點的數(shù)目過多，因此選擇最佳劃分節(jié)點就非常耗時計算資源，針對VFDT中處理了離散屬性的問題。NIP方法的基本做法就是將連續(xù)屬性取值劃分為不同的區(qū)間，然后利用統(tǒng)計測試對這些區(qū)間進行剪枝任何時刻，每個區(qū)間或者被剪枝或者保持完整如果一個區(qū)間不可能包含最佳劃分節(jié)點則把該區(qū)間剪枝掉、完整區(qū)間是指沒有被剪枝的區(qū)間。對于連續(xù)屬性，為了選擇最佳劃分節(jié)點，NIP方法為每個節(jié)點保存下列數(shù)據(jù)集合。9NIPDTConciseClassHistograms。對于有很多不同取值的連續(xù)屬性將其取值劃分成多個區(qū)間對于連續(xù)屬性的每個區(qū)間，精確類直方圖用于記錄該區(qū)間范圍內(nèi)各個類別的樣本出現(xiàn)的次數(shù)。DetailedInformation。詳細(xì)信息根據(jù)效率分成兩種方式:第1種方式是區(qū)間的樣本數(shù)目直方圖當(dāng)樣本數(shù)目很多而連續(xù)屬性的取值相對較小時，這種方式比較有效:第2種方式只是簡單地保存每個分類的樣本數(shù)目，而不需要處理剪枝掉的區(qū)間中的詳細(xì)信息以獲取最佳劃分節(jié)點這種方法的好處是不需要處理剪枝掉的區(qū)間內(nèi)的詳細(xì)信息，因此可以在少精下很好地減少執(zhí)行時間。10IFDTIFDT(incrementalfuzzydecisiontrees)是由Guetova等人提出的一種增量式模糊決策樹數(shù)據(jù)流分類方法它綜合了決策樹和模糊邏輯的優(yōu)點同時它是增量式的，很好地滿足了數(shù)據(jù)流分類的要求首先它生成決策樹，這就很好地利用了決策樹的特點:其次，它使用模糊邏輯，這非常符合人們?nèi)粘５乃季S習(xí)慣:此外它是增量式的這為分類器提供了學(xué)習(xí)新數(shù)據(jù)的能力算法綜合了模糊決策樹的決策能力和決策樹在經(jīng)典邏輯下的增量算法，并且能多和非增量算法產(chǎn)生相同的結(jié)果。11數(shù)據(jù)帶概念漂移分類方法數(shù)據(jù)流中的概念流可以通過以下三種方式進行處理：基于窗口的方法、基于重量的方法以及集成分類?；诖翱诘姆椒ㄊ峭ㄟ^選擇一個固定的或動態(tài)的滑動窗口構(gòu)建一個分類模型，在分類精度的基礎(chǔ)上調(diào)整窗口的大小（Lee，2009）。在以重量為基礎(chǔ)的方法上，每個訓(xùn)練實例被分配一個權(quán)重。最流行的演變技術(shù)來處理概念漂移的數(shù)據(jù)流是使用集成分類（分類器的組合），幾個輸出分類器的組合是用來確定最終的分類，這通常被稱為融合規(guī)則。另外，在每個時間點的個體輸出分類器上分配權(quán)重，權(quán)重通常為一個歷史表現(xiàn)函數(shù)，通過使用交叉驗證過去或估計的函數(shù)。12數(shù)據(jù)流概念漂移挖掘研究現(xiàn)狀為了從大量來自真實世界的復(fù)雜數(shù)據(jù)中提取最有用的信息和知識，在過去十年，各種數(shù)據(jù)挖掘算法已經(jīng)被提出和發(fā)展。Masud等（2011）建議在真正的標(biāo)記新類型的實例之前應(yīng)使用分類器來檢測新的類別。為了確定每個個體是否屬于某一新類型，其分類模型有時需要收集更多的測試實例來發(fā)現(xiàn)數(shù)據(jù)之間的異同。Polikar（2011）也推出了可以漸進式學(xué)習(xí)流的分類器集合體，并命名為學(xué)習(xí)+NSE方法，通過當(dāng)前和過去的環(huán)境動態(tài)加權(quán)多數(shù)表決技術(shù)結(jié)合這些分類可以調(diào)整各個分類時間的準(zhǔn)確率。Song（2010）提出了一種基于關(guān)聯(lián)規(guī)則的關(guān)聯(lián)分類算法的數(shù)據(jù)流，其工作宗旨是發(fā)現(xiàn)各項集之間的關(guān)系，并從輸入的數(shù)據(jù)集中提取一套完整的頻繁模式。13在數(shù)據(jù)挖掘和機器學(xué)習(xí)領(lǐng)域中的數(shù)據(jù)流分析和挖掘是一項具有挑戰(zhàn)性的研究，它最近受到許多計算智能研究人員的關(guān)注（Holmes，2012）。數(shù)據(jù)流分類是提取知識和連續(xù)數(shù)據(jù)點信息的方法（Read，2010）。在數(shù)據(jù)流中的數(shù)據(jù)是隨著時間的推移所產(chǎn)生的，并且不能由任何預(yù)先定義的順序來控制。一個數(shù)據(jù)流與傳統(tǒng)的靜態(tài)數(shù)據(jù)或數(shù)據(jù)庫相比有非常多元化的特點，包括：動態(tài)、無限、高維、有序、不重復(fù)、高速和時變（Zliobaite，2009年）。大多數(shù)現(xiàn)有的數(shù)據(jù)挖掘技術(shù)不能檢測及在數(shù)據(jù)流環(huán)境中進行分類（Qin，2007），因而現(xiàn)有的挖掘模型會將這些分類新實例與類標(biāo)簽弄錯（Biswas，2004）。因此，這樣的數(shù)據(jù)流分類需要不斷更新和再培訓(xùn)通過在線數(shù)據(jù)流中標(biāo)記新來的數(shù)據(jù)。數(shù)據(jù)流概念漂移分類研究現(xiàn)狀14

數(shù)據(jù)流查詢的類型和處理策略：數(shù)據(jù)挖掘之?dāng)?shù)據(jù)流處理

固定查詢：對前來的數(shù)據(jù)一直在執(zhí)行查詢和計算。即時查詢adhoc：僅當(dāng)一個查詢操作提交時，才對數(shù)據(jù)進行計算查詢計算問題的近似解，比精確解高效的多hash技術(shù)，對求解近似解非常有幫助151.

抽樣統(tǒng)計帶來的問題;2.

統(tǒng)計用戶的重復(fù)查詢問題;3.

抽樣時，涉及概率的乘法定理要謹(jǐn)慎處理，因為抽樣后的概率運行可能與全集下的概率運算結(jié)果完全不同;大數(shù)據(jù)流抽樣帶來的問題16大數(shù)據(jù)流抽樣帶來的問題解決方法：對用戶進行抽樣，而不是對每個用戶的數(shù)據(jù)進行抽樣。一般性的抽樣問題：將某些字段看成關(guān)鍵字組合，并利用hash的a/b策略，即b個桶，a作為閾值，保留小于a的采樣值。新問題：新用戶出現(xiàn)，每個用戶的樣本規(guī)模不斷變大，以至于抽樣的數(shù)據(jù)都超出了分配的空間，如何處理？那么就設(shè)定新的閾值a-1，即降低閾值，并將hash值等于a的數(shù)據(jù)刪除，這樣可以提高效率，節(jié)省空間。17過濾指定規(guī)則的數(shù)據(jù)主要是指Bloom過濾器;Bloom過濾器組成部分：n位的數(shù)組；k個hash函數(shù)；m個待過濾的元素；則bloom過濾器的假陽的概率是：(1-e^(-km/n))^k推導(dǎo)：元素不能落入指定的位置的概率是(n-1)/n，那么m個元素，hash了k次，仍未落入指定位置的概率是(1-1/n)^(km)，即當(dāng)n較大時，指定位置為0的概率近似于e^(-km/n)，為1的概率為1-e^(-km/n)。而假陽的概率，是k個hash函數(shù)產(chǎn)生的k個指定位置，都為1的概率：

(1-e^(-km/n))^k。過濾數(shù)據(jù)18如果對N位的二進制數(shù)據(jù)，統(tǒng)計1的個數(shù)，那么精確統(tǒng)計1的個數(shù)就需要只是O(N)的開銷,當(dāng)N大于內(nèi)存的容量時，那么快速的求解這個問題，可以采用求近似解的策略。DGIM算法：(1)維護一個數(shù)據(jù)結(jié)構(gòu)：將二進制分組，每組中1的個數(shù)是2的次冪，從