資料挖掘--資料流挖掘

一個多月沒更新了，去考托福和gre了，英語太差有點難過。。。

我最近看到資料流這個字眼，想到對資料流挖掘了解的太少了，幾乎是一竅不通，是以就像學學資料流挖掘。

這篇部落格算是我學習資料流的一個筆記吧。

一些我看到比較有收獲的網站

https://www.cnblogs.com/jean925/p/8963512.html

https://blog.csdn.net/viewcode/article/details/9088467

https://blog.csdn.net/dashuniuniu/article/details/50705389

基本知識

（https://blog.csdn.net/viewcode/article/details/9088467 ）

1. 資料流的查詢

   固定查詢：對前來的資料一直在執行查詢和計算

   即時查詢ad hoc：僅當一個查詢操作送出時，才對資料進行計算查詢

2. 算法政策

   記憶體有大小限制，是以，資料流處理算法的兩個政策：

   計算問題的近似解，比精确解高效的多

   hash技術，對求解近似解非常有幫助

3. 抽樣計算

   從流中選擇一個子集，以便能夠對它進行查詢并給出統計性上對整個流具有代表性的結果。資料流巨大時，隻需随機抽樣一部分資料，進行存儲，并供ad hoc分析使用。

   統計使用者的重複查詢問題：抽樣時，涉及機率的乘法定理要謹慎處理，因為抽樣後的機率運作可能與全集下的機率運算結果完全不同。

   解決方法：對使用者進行抽樣，而不是對每個使用者的資料進行抽樣。

   一個抽樣的方法–蓄水池采樣

   (來自 https://blog.csdn.net/dm_ustc/article/details/45875971)

我們要從資料流中随機抽取k個元素。如果資料流長度m事先已經知道，那這個問題就非常簡單，每個元素以k/m的機率選取即可。但這個問題要求m未知，那就不太好搞了。這個問題的解法是儲存一個k大小的視窗。資料流的前k個元素依次加入到視窗。對于資料流第i個元素（i>k），以k/i的機率替換視窗中的某個元素。最終視窗的元素出現機率均為k/m。

下面使用數學歸納法給出該算法合理性的簡單證明。

1.假設i=1，元素被選中的機率為1；

2.設前i個元素被選中的機率為k/i。對于第i+1個元素，我們以k/i+1的機率替換視窗中的元素。其中k/i為某個元素在第i+1個元素來到前被選中的機率。如果第i+1個元素替換視窗内的元素，則以1/k的機率從視窗選一個元素去除，将第i+1個元素添加進去。計算出的結果表明元素仍存在視窗的機率為k/(i+1)。得證。

一個實際例子(來自mining massive dataset)

1.問題：對于搜尋引擎是不斷有查詢流的，這些資料可以用來研究典型使用者的行為。假設資料流的每個元素由三元組組成(user,query,time)。假設想要查詢“在過去一個月中典型使用者所送出重複查詢的比例是多少”。假設我們隻希望存儲1/10的元素。

2.錯誤做法

一個很容易的做法就是對于每個查詢都以1/10的機率進行儲存。但是這個方法對于我們的問題會帶來錯誤結果。假定某使用者在過去一個月有s個查詢隻送出過1次，有d個查詢送出過兩次，不存在送出超過2次的查詢。該使用者送出重複查詢的比例為s/(s+d)。

如果我們的查詢比例為1/10，那麼在該使用者的查詢中，送出過1次的查詢達到我們期望的s/10。而出現2次的d個查詢中隻有d/100會在樣本中出現1次（兩個相同的查詢都出現在樣本中的機率為(1/10)(1/10)=1/100），有18d/100的查詢在樣本中出現1次（兩個相同的查詢隻有一個出現在樣本中，機率為(1/10)(9/10)*2=(18/100)）。則該使用者送出重複查詢比例為(d/100)/(d/100+s/10+18d/100)=d/(10s+19d)。顯然和期望值不相等。

3.正确做法

對于這類問題，不能從每個使用者查詢的抽樣樣本中得到正确答案。是以我們必須挑選出1/10的使用者，将他們的所有查詢放入到樣本中，而不考慮其他使用者的查詢。也就是說我們采樣的對象不是查詢，而是使用者。

4.一般性的抽樣問題：

将某些字段看成關鍵字組合，并利用hash的a/b政策，即b個桶，a作為門檻值，保留小于a的采樣值。

新問題： 新使用者出現，每個使用者的樣本規模不斷變大，以至于抽樣的資料都超出了配置設定的空間，如何處理？

那麼就設定新的門檻值a-1，即降低門檻值，并将hash值等于a的資料删除，這樣可以提高效率，節省空間。

1. 過濾資料–bloom過濾器https://www.jianshu.com/p/6f9b2d6fba68https://www.jianshu.com/p/6f9b2d6fba68 裡面的例子很清楚

   比如垃圾郵件的過濾，采用布隆過濾的方法，建立一個位數組，初始化所有值為0，将合法的郵件映射到位數組上，并設定值為1，用不同的hash函數檢查郵件，如果有一個值為0，則拒絕

2. 統計某時段内，出現的不同元素的數目

   一種方案是記憶體中儲存目前所有元素清單，可以用hash或搜尋樹來儲存和檢索資料。問題：元素數目可能大到無法全部放入記憶體。

   解決方案：

   1.使用多台機器，并行處理

   2.FM（Flajolet-Martin）算法，統計某元素hash後尾部0的個數，若其hash值尾部0的個數至少為r的機率是2^(-r)，而任何元素hash值尾部都不滿足至少有r個0的機率為(1 - 2(-r))m。 然後估計出所有元素的個數m：2^R, 最大尾長為R

   優化政策： 多個hash函數，分組：組内平均值 + 元件中值濾波（取中位數）

Flajolet-Martin(FM)算法能夠較好地解決估算資料流序列中獨立元素數目的問題。

（https://blog.csdn.net/llwszjj/article/details/25629009?utm_source=blogxgwz3）

假設我們有1萬個int型數字可重複的），我們想找出這個數字集合中不重複的數字的個數。怎麼辦呢？很簡單，将這1萬個數字讀進記憶體，存放到hashset中，那麼hashset的size就是不重複數字的個數。接下來，問題變得更加的複雜，有100億個數字，怎麼辦? 全部讀取到記憶體中可能會有問題，如果這其中有1億個不重複的數字，那麼至少需要記憶體 100M sizeof(int)，記憶體也許不夠。 FM算法就是為了解決這個問題。假設n個object，其中有m個唯一的，那麼FM算法隻需要log(m)的記憶體占用（實際操作中會是klog(m)），以及O(n)的運算時間。當然，FM的問題是，它的結果隻是一個估計值，不是精确結果。

具體思路如下：

假定哈希函數H(e)能夠把元素e映射到[0, 2^m-1]區間上；再假定函數TailZero(x)能夠計算正整數x的二進制表示中末尾連續的0的個數，譬如TailZero(2) = TailZero(0010) = 1，TailZero(8) = TailZero(1000) = 3，TailZero(10) = TailZero(1010) = 1；我們對每個元素e計算TailZero(H(e))，并求出最大的TailZero(H(e))記為Max，那麼對于獨立元素數目的估計為2^Max。

舉例來說，給定序列{e1, e2, e3, e2}，獨立元素數目N = 3。假設給定哈希函數H(e)，有：

H(e1) = 2 = 0010，TailZero(H(e1)) = 1

H(e2) = 8 = 1000，TailZero(H(e2)) = 3

H(e3) = 10 = 1010，TailZero(H(e3)) = 1

第1步，将Max初始化為0；

第2步，對于序列中第1項e1，計算TailZero(H(e1)) = 1 > Max，更新Max = 1；

第3步，對于序列中第2項e2，計算TailZero(H(e2)) = 3 > Max，更新Max = 3；

第4步，對于序列中第3項e3，計算TailZero(H(e3)) = 1 ≤ Max，不更新Max；

第5步，對于序列中第4項e2，計算TailZero(H(e2)) = 3 ≤ Max，不更新Max；

第6步，估計獨立元素數目為N’ = 2^Max = 2^3 = 8。

在這個簡單例子中，實際值N = 3，估計值N’ = 8，誤差比較大。此外，估計值隻能取2的乘方，精度不夠高。

在實際應用中，為了減小誤差，提高精度，我們通常采用一系列的哈希函數H1(e), H2(e), H3(e)……，計算一系列的Max值Max1, Max2, Max3……，進而估算一系列的估計值2^Max1, 2^Max2, 2^Max3……，最後進行綜合得到最終的估計值。具體做法是：首先設計A*B個互不相同的哈希函數，分成A組，每組B個哈希函數；然後利用每組中的B個哈希函數計算出B個估計值;接着求出B個估計值的算術平均數為該組的估計值；最後選取各組的估計值的中位數作為最終的估計值。

舉例來說，對于序列S，使用3*4 = 12個互不相同的哈希函數H(e)，分成3組，每組4個哈希函數，使用12個H(e)估算出12個估計值：

第1組的4個估計值為<2, 2, 4, 4>，算術平均值為(2 + 2 + 4 + 4) / 4 = 3；

第2組的4個估計值為<8, 2, 2, 2>，算術平均值為(8 + 2 + 2 + 2) / 4 = 3.5；

第3組的4個估計值為<2, 8, 8, 2>，算術平均值為(2 + 8 + 8 + 2) / 4 = 5；

3個組的估計值分别為<3, 3.5, 5>，中位數為3.5；

是以3.5 ≈ 4即為最終的估計值。

1. 總結一下資料流相關的例子

（https://blog.csdn.net/sun33170161/article/details/18769541 ）

1.資料抽樣

比如過去一個月中典型使用者所送出的重複 查詢的數目。在使用者規模較大的時候，将使用者hash到不同的桶中，當空間不足時，則丢棄一部分桶。

2.流過濾

比如垃圾郵件的過濾，采用布隆過濾的方法，建立一個位數組，初始化所有值為0，将合法的郵件映射到位數組上，并設定值為1，用不同的hash函數檢查郵件，如果有一個值為0，則拒絕

3.獨立元素統計

比如統計web查詢的數目，可以應用FM算法，将所有的査詢hash到一個位串中，檢查其末尾最大0的數目，設為R，則總數可以估計為2^R。

4.元素分布

一般用二階矩估計，即每個元素出現數目的平方和來判斷流元素分布的均勻性。可以采用AMS算法來近似計算二階矩：在流中随機選取多個位置，并統計每個位置上的元素出現的次數，設為c，用n表示總的元素數目，則二階矩為n*(2*c-1)的均值

5.計數

為了能夠查詢視窗内任意數目的元素中1的個數，采用DGIM算法，每出現元素1，則建立一個新的桶，并遞歸地嘗試合并之前的桶，使得每個桶的大小為2的幂，且相同大小的桶最多為2個。每個桶隻用儲存最近的時間戳和桶的大小，有效避免了精确計數帶來的空間開銷。為了減小估計結果的誤差，可以增加所允許出現的相同大小的桶的數目。

6.流行元素

比如最近流行的電影，可以定義一個衰減視窗，獨立計算每一部電影流，對每張新的電影票，首先将所有的電影乘以一個衰減值，然後檢查電影票對應的電影得分是否已存在，如果不存在，則建立新的電影流并設定得分為1，否則将該電影的得分加1。為了減少需要統計的數目，可以設定一個閥值，将低于閥值的得分丢掉。

1. 資料流分析有以下方面

   資料流頻繁項集挖掘

   資料流聚類

   資料流分類

   資料流離群點檢測

   資料流Skyline計算

   資料流子序列比對

   資料流索引結構

   資料流概要結構生成

   資料采樣以及壓縮

   資料流粒度表示

   資料流相似性度量

   資料流趨勢預測

資料流聚類

我有點好奇這個，是以想仔細看看

支撐知識（在csdn上下載下傳了一個ppt看的）

1. 資料流模型

• 按照算法處理資料流時所采用的時序範圍分類按照算法處理資料流時所采用的時序範圍分類：

  (1)快照模型 ( Snapshot Model) :處理資料的範圍限制在兩個預定義的時間戳之間。

  (2)界标模型 (Landmark Model) :處理資料的範圍從某一個已知的初始時間點到目前時間點為止。

  (3)滑動視窗模型 (Sliding Window Model) :處理資料的範圍由某個固定大小的滑動視窗确定 ,此滑動視窗的終點永遠為目前時刻。其中 ,滑動視窗的大小可以由一個時間區間定義 ,也可以由視窗所包含的資料項數目定義。

• 資料流中的資料項 x 1 , …, xi , …, xn 依次按下标順序到達 ,它們描述了一個信号 A。

  按 xi描述信号 A的方式 ,資料流模型可分為以下幾類:

  (1)時序( Time Series)模型:A [ i ] = xi 。

  (2)現金登記 (Cash Register)模型:令 xi = ( j,Ii ) ,且 Ii≥0,則 Ai [j] =Ai-1 [ j ] + I i。此時 ,資料流中的多個資料項增量式地表達一個 A [ j ]。

  (3)十字轉門( Turnstile)模型:令 xi = ( j,Ui) ,則Ai[ j ] =Ai -1 [ j ] +Ui。其中 , Ui可為正數 ,也可為負數。

1. 基于資料的技術

• 抽樣（Sampling）

  使用水庫抽樣（reservior sampling）在“水庫”中維護s個候選的樣本，随着資料流的流動，新的資料元素都有一定的機率替代水庫中的元素。

• 梗概（Sketching）

  梗概是一個将資料流中的資料向量做一個随機投影的過程。它建立這些分布向量（如直方圖）的小空間彙總。梗概廣泛用于不同資料流的比較和聚集查詢。缺乏精度。

1. 衰減函數（Fading Function）

   強調近期資料的重要性、消減曆史資料對計算結果影響的方法是衰減因子和衰減函數。資料元素在參與計算前，先經過衰減函數的作用。是以，每個資料元素對最終結果的影響将随着時間的推移逐漸減小。一種常用的衰減函數形式為指數形式。

stream聚類

對于資料流來說，使用批處理的方式。

STREAM算法采用分級聚類的方法，首先對最初的m 個輸入資料進行聚類得到O(K)個1 級帶權質心，然後将上述過程重複m/O(K) 次，得到m 個1 級帶權質心，然後對這m 個1 級帶權質心再進行聚類得到O(K) 個2級帶權質心；同理，每當得到m 個i 級帶權質心時，就對這些質心進行一次聚類得到O(K) 個i+1 級帶權質心；重複這一過程直到得到最終的O(K)個質心。對于每個第i+1 級帶權質心而言，其權值是與它對應的i 級質心的權值之和。

也就是将大量的資料分成m批，每一批内部使用k-means聚類，這樣可到mk個質心，對mk作為新的資料進行批處理聚類，得到了m’k’個質心，這樣一級級向上聚類。

clustream

引入的新的概念：

• 簇，線上部分，微聚類
• 時間幀，離線部分，宏聚類

1. 線上部分（微簇）

• 初始化簇

  首先在磁盤上存儲最初始的initNumber個資料點，然後采用标準的k-means算法形成q個微簇：M1、M2…Mq。

• 線上處理　　

  對于以後達到的每一個資料點Xik，要麼被上述的某個微簇吸收，要麼放進它自己的簇中。首先計算Xik與q個微簇中的每一個的距離（實際上是其中心）。将其放到離它最近的那個簇Mp中。

  特殊情況：

  1.Xik雖然離Mp最近，但是Xik卻在Mp的邊界外；

  2.由于資料流的演化，Xik可能是一個新簇的開端。

  處理方法：

  為落在邊界外的資料點建立一個帶獨有标志id的新簇，這需要減少一個其他已經存在的簇。這可以通過删除一個最早的簇或者合并兩個最早的簇來實作。

1. 離線處理（時間幀，宏簇）

   使用者在該部分可以在不同時間幅度内發現簇。這部分所用的資料是線上部分形成的統計資訊，這可以滿足記憶體有限的需求。使用者提供兩個參數h和k，h是時間幅度，k是預定義的需要形成的簇的數目。

   算法：

   該部分采用改進的k-means算法

• 初始階段

  不再随機的選取種子，而是選擇可能被劃分到給定簇的種子，這些種子其實是對應微簇的中心。

• 劃分階段

  一個種子到一個“僞資料點”（也就是微簇）的距離就等于它到“僞資料點”中心的距離。

• 調整階段

  一個給定劃分的新種子被定義成那個劃分中帶權重的微簇中心

總結：離線聚類就是在線上聚類的基礎上，對線上簇進行聚類

下面是資料流聚類的方法，我想等到具體應用的時候再仔細研究剩下的方法

資料流分類

https://blog.csdn.net/tanhy21/article/details/53363508