一種基於網格和聚類優化的實時數據流核密度估計方法與流程
2023-09-19 21:13:05
本發明屬於概率密度估計的技術領域，具體涉及一種基於網格和聚類優化的實時數據流核密度估計方法。
背景技術：
近年來，隨著網絡技術和硬體性能的快速發展，科學和商業應用產生的海量數據以數據流的形式被傳輸。例如，無線傳感器網絡由大量具有感知和通訊能力的分布式節點構成。這些節點實時採樣環境參數並通過多種類型的異構網絡將數據傳送到中央處理器集群。這些數據的特徵是隨時間到達、快速變化、海量的和潛在無限的。在這樣的條件下，存儲全體數據不易操作且沒有必要。數據流對處理算法提出了如下新的要求：(1)為趕上數據抵達的速率，處理數據流中每條記錄的時間必須短且固定；(2)因為不可能有時間重新訪問歷史數據，建立的處理模型中每個數據最多掃描一次；(3)無論處理模型面對的數據量多少，必須使用固定大小的內存空間；(4)當數據的概念漂移發生，任何時候處理都能及時更新，同時仍然包含沒有過期的歷史信息。
許多流挖掘技術，特別是使用統計方法的流挖掘技術，概率密度函數(PDF)是主要的數據模型。由於先驗知識的局限性，實際應用中流數據概率密度函數的形式(例如，高斯分布，泊松分布)是不確定的，事先不能得知。一般可以使用不帶任何假設僅從樣本本身出發研究數據分布特徵的非參數估計方法來估計概率密度函數，其中核密度估計是已有高效的非參數估計技術。核密度估計的質量嚴重依賴帶寬，而不同的核函數對整體估計質量影響有限。
對應n個給定的樣本點和Q個在數據區域內均勻分布的查詢點，標準核密度估計公式的計算代價為ο(nQ)，對數據流而言過於高昂。為了計算每個查詢點的概率密度值(或者說查詢點的數量Q是固定的)，降低計算複雜度的唯一出路是找到樣本的替代物，也就是壓縮n。與此同時，替代物佔用的存儲空間必須顯著小於樣本本身需要佔用的存儲空間。遵循上述思路，核密度估計技術主要分為基於網格(GKDE)和基於聚類的兩類方法(CKDE)。
基於網格的核密度估計也稱為分箱核密度估計，生成遠小於樣本數量的若干均勻排列的空間網格，其中非空網格數量為G，將所有映射到網格的樣本數據匯聚於網格內某點，利用該點的位置和數據量權重唯一地表徵映射到該網格的樣本集合。網格策略使得密度估計計算複雜度降低為ο(GQ)，空間複雜度為ο(G)。常用的分箱規則包含簡單分箱和線性分箱。比較基於網格中心的簡單分箱規則和線性分箱規則，李存華等提出的基於網格內樣本重心的簡單分箱規則(BKDE-GGC)是更合理的選擇，這種規則沒有邏輯數據點產生，並且分箱誤差的數量級為ο(δ4)，δ代表固定設置的空間網格寬度且δ→0。由於δ→0意味著非空網格的數量G仍然很大，所以直接對數據流應用網格密度估計不是明智的選擇。
基於聚類的核密度估計執行核合併以維持固定數量的存儲空間，其主要思想是獲得可以表徵全體樣本統計特徵的有限的合併核。許敏等介紹了MMCKDE，一種基於優化技術的聚類核密度估計算法。根據採用的優化策略，每次核合併的誤差被減少到局部極小。然而，當不同時間序列的樣本集形成的聚類優化核的數量到達內存上限，擁有最短Kullback-Leilber距離的兩個聚類優化核必須被再次合併以確保內存不會溢出，這些操作不可避免地累積了合併誤差，且不能證明誤差收斂。另一方面，MMCKDE沒有提供多變量模型，不能應用於各個維度的核帶寬取不同值的多維聚類優化核密度估計。
技術實現要素：
本發明主要是解決現有數據流密度估計技術所存在的計算精度和處理速度難以平衡的不足，提供一種既有較快處理速度，也有較高的計算精度的實時數據流核密度估計方法。
本發明針對上述技術問題主要是通過下述技術方案得以解決的：一種基於網格和聚類優化的實時數據流核密度估計方法，包括以下步驟：
A、網格預處理過程：將樣本數據所在d維實數空間Rd的每個維度進行等寬劃分，從而將Rd劃分為若干依次相鄰且互不相交的超方體網格的集合。
B、在線網格維護過程：建立先進先出的在線隊列，連續地在隊列尾部接收新數據，更新對應網格的特徵向量，判斷該網格是否進化為密度網格；同時在隊列頭部丟棄歷史數據，更新對應網格的特徵向量，判斷該網格是否退化為稀疏網格。在網格特徵向量的基礎上建立網格六元組，將原始數據流樣本合併為網格重心點，以提高計算效率。核合併在網格內進行，避免了不可控的累計誤差。根據新增和丟棄的樣本數據動態維護密度網格集合。
C、離線聚類過程：每隔固定時間間隔gap進入並發處理的離線階段，該時間間隔的最小值大於處理一次K-means聚類、核參數優化和查詢點密度估計等開銷的時間之和，主要由算法的執行效率和實際應用需要的查詢點分布數量決定。利用權重K-means算法對網格重心點進行聚類，該過程由兩個階段實現。第一階段以兩點間歐幾裡德距離最短為原則將G個網格重心點聚類到m個聚類中心，第二階段根據每個聚類集合包含的網格元素的權重和空間位置重新計算聚類的重心點。算法在兩個階段之間來回迭代執行，直到在聚類分配上沒有進一步的變化為止。
D、離線優化過程：利用多變量MMCKDE算法(M-MMCKDE)對聚類後的網格進行優化。M-MMCKDE使用一個新的聚類優化核替代權重K-means算法得到的每個聚類中全部的網格重心核，目標是兩者之間距離的極小化。這樣操作使得後續查詢點核密度估計的計算複雜度從ο(GQ)降低為ο(mQ)。通過反覆調用求取聚類優化核係數、高斯核帶寬和聚類點的迭代公式，將網格置於合適的聚類中，縮小網格重心核與聚類優化核之間的距離，聚類優化核可以漸次逼近全體網格重心核。得到的聚類優化核作為查詢點核密度估計的輸入。
E、離線核密度估計過程：計算m個聚類優化核對查詢點核密度的累計，得到最終的數據流核密度估計的結果。
作為優選，所述步驟A中，採用簡單分箱規則將樣本數據所在d維實數空間Rd劃分為網格集合式中，gj＝(j1,…,ji,…,jd)代表網格序號,即gj表示第j個網格，ji表示第j個網格中的第i個維度，δ＝(δ1,…,δi,…,δd)代表網格寬度，即δi表示網格的第i個維度的寬度，Zd為d維整數空間。
作為優選，所述步驟B中，在每個數據到達時刻，新數據進入隊列尾部，該數據對應的網格的特徵向量被刷新。同時，丟棄隊列頭部的歷史數據，該數據對應的網格的特徵向量被刷新。t時刻進入隊列的d維樣本數據V可以表示為：
V＝[v1,…,vi,…,vd,t]
vi表示樣本數據V中的第i維的值，d維網格的數據映射規則由以下簡單分箱函數族確定：
上式表明樣本數據V以權值Wgj(V,δ)映射到網格gj。
當隊列尾部增加新數據被映射到相應網格中時，則對該網格的特徵向量進行更新，更新操作如下：
其中為映射到網格gj的數據量，是映射到該網格的全體數據的第i維線性和，是映射到該網格的全體數據的第i維平方和。
當隊列頭部丟棄歷史數據被映射到相應網格中時，則對該網格的特徵向量進行更新，更新操作如下：
映射到網格的全體數據的均值和方差可以由特徵向量計算得到：
式中為網格gj第i維數據的均值，是網格gj第i維數據的方差。
密度網格的判斷條件為其中α為網格的數據量(網格密度)，修正係數ξ∈(0,1)，n是在線隊列長度，G為非空網格的數量。反之，當該網格為稀疏網格。密度網絡集合為離線階段的權重K-means聚類提供服務。
經過在線網格維護過程，原始數據的統計信息被保存在一個網格六元組內，即元組(α,LS,SS,g*,σ2,flag)，使得n個樣本數據被合併為G個網格重心點，以提高計算效率，避免不可控的累計誤差。flag代表網格的密度標誌。
作為優選，所述步驟C中，每隔固定時間間隔gap進入並發處理的離線階段，該時間間隔的最小值設定為大於處理一次K-means聚類、核參數優化和查詢點密度估計等花費的時間之和，主要由算法的執行效率和實際應用需要的查詢點分布數量決定。利用權重K-means算法對網格重心點進行聚類，該過程由兩階段迭代實現。令表示用於劃分到m個聚類的G個非空網格重心點的集合，從在線階段得到的密度網格集合中選取空間位置均勻分布的m個密度網格的重心點作為初始聚類的中心，Sl代表網格集合的第l個聚類。按照空間位置而不是隨機選擇初始聚類中心的目的是為了減小出現局部次優解的可能性和快速收斂。第一階段以兩點間歐氏距離最短為原則將G個網格重心點聚類到m個聚類中心，通過求取以下代價函數的最小值確定：
式中代表第gj個網格重心點到第l個聚類中心的歐式距離。
第二階段根據每個聚類集合Sl包含的網格元素的權重和空間位置重新計算m個聚類的重心點，由以下公式確定：
式中代表第gj個網格的權重(數據量)。權重K-means算法在兩個階段之間來回迭代執行，直到在聚類分配上沒有進一步的變化為止，輸出結果為
作為優選，所述步驟D中，採用高斯核作為核函數K(·)。按照時間順序從數據流中採樣的n個獨立同分布的樣本點V1,V2,…,Vn存儲於在線隊列，它們分別映射到對應的網格重心，基於聚類中網格重心的d維核密度估計由以下公式確定：
式中，m是聚類數量，Sl代表非空網格集合的第l個聚類，代表Sl中第gj個網格的權值，是第vj個網格的重心點的第k維度值，是第gj個網格在第k維的核帶寬。
多變量MMCKDE算法(M-MMCKDE)使用一個新的聚類優化核代替權重K-means算法得到的每個聚類中全部的網格重心核，使得查詢點密度估計的計算複雜度從ο(GQ)降低為ο(mQ)。對第l個聚類，使用聚類優化核代替其中全部網格重心核的總和其中hl,k是第l個聚類優化核第k維帶寬，G為高斯核。令使g(X)逼近L2準則用於評估g(X)和之間的誤差，第l個聚類優化核的最小誤差上界由以下公式確定：
根據優化理論，第l個聚類優化核的係數βl、高斯核寬hl,k和聚類點tl,k的迭代計算由以下公式確定：
令網格重心核與聚類優化核之間的距離
平方由以下公式確定：
通過反覆迭代調用求取極小值的βl，tl,k和hl,k公式，將網格置於合適的聚類中，縮小網格重心核與聚類優化核之間的距離，本地最優g(X)對應的βl，tl,k和hl,k可以漸次得到，逼近得到的g(X)作為查詢點核密度估計的輸入。
作為優選，所述步驟E中，計算m個聚類優化核對查詢點核密度的累計，得到最終的數據流核密度估計的結果，由以下公式確定：
式中，X＝(x1,…,xk,…,xd)為單個查詢點。
本發明的技術構思為：採用在線/離線雙層框架，在線過程持續維護不斷到達的數據流對象，存入先進先出隊列，隊頭和隊尾數據映射到相應的網格，進而更新網格的特徵向量，原始數據的統計信息被保存在網格六元組內。基於權重K-means的網格聚類在離線階段執行，將參與核密度估計的網格數量減少為聚類核數量。得到的聚類，其網格成員、參數βl,tl,k和hl,k根據M-MMCKDE優化策略修正以確保極小化合併網格重心核的誤差，從而得到聚類優化核，據此最終獲得查詢點的數據流核密度估計結果。
本發明帶來的實質性效果是，在線映射策略不僅保證數據流的快速接收，反映數據流的進化特徵，而且核合併過程主要是網格內數據匯聚到重心點，大量的網格間核合併只在每個離線階段發生一次，從而保證估計誤差是收斂的。使用聚類優化技術極小化網格間核合併誤差，使得估計器總體誤差和基於網格重心點的核密度估計誤差處於相同數量級，同時計算複雜度從ο(GQ)下降為ο(mQ)。所以，允許縮短離線時間間隔gap，提升執行效率。同時，空間複雜度仍然保持為ο(G)。
附圖說明
圖1為2維實數空間R2的簡單分箱網格劃分示意圖；
圖2為網格重心點示意圖；
圖3為聚類中心示意圖；
圖4為GCOKDE數據流核密度估計框圖。
具體實施方式
下面通過實施例，並結合附圖1～4，對本發明的技術方案作進一步具體的說明。
實施例：本實施例的一種基於網格和聚類優化的實時數據流核密度估計方法，包括以下步驟：
A、網格預處理過程：將樣本數據所在d維實數空間Rd的每個維度進行等寬劃分，從而將Rd劃分為若干依次相鄰且互不相交的超方體網格的集合。採用簡單分箱規則將樣本數據所在d維實數空間Rd劃分為網格集合式中，gj＝(j1,…,ji,…,jd)代表網格序號，δ＝(δ1,…,δi,…,δd)代表網格寬度，Zd為d維整數空間。2維實數空間R2的簡單分箱規則的網格劃分如圖1所示，兩個維度的網格寬度δ1和δ2不一定相等。
B、在線網格維護過程：建立先進先出的在線隊列，連續地在隊列尾部接收新數據，更新對應網格的特徵向量，判斷該網格是否進化為密度網格；同時在隊列頭部丟棄歷史數據，更新對應網格的特徵向量，判斷該網格是否退化為稀疏網格。在網格特徵向量的基礎上建立網格六元組，將原始數據流樣本合併為網格重心點。根據新增和丟棄的樣本數據動態維護密度網格集合。
在每個數據到達時刻，新數據進入隊列尾部，該數據對應的網格的特徵向量被刷新。同時，丟棄隊列頭部的歷史數據，該數據對應的網格的特徵向量被刷新。t時刻進入隊列的d維樣本數據V可以表示為：
V＝[v1,…,vi,…,vd,t]
vi表示樣本數據V中的第i維的值，d維網格的數據映射規則由以下簡單分箱函數族確定：
上式表明樣本數據V以權值Wgj(V,δ)映射到網格gj。
當隊列尾部增加新數據被映射到相應網格中時，則對該網格的特徵向量進行更新，更新操作如下：
其中αgj為映射到網格gj的數據量，LSgj,i是映射到該網格的全體數據的第i維線性和，SSgj,i是映射到該網格的全體數據的第i維平方和。
當隊列頭部丟棄歷史數據被映射到相應網格中時，則對該網格的特徵向量進行更新，更新操作如下：
映射到網格的全體數據的均值和方差可以由特徵向量計算得到：
式中為網格gj第i維數據的均值，是網格gj第i維數據的方差。
密度網格的判斷條件為其中α為網格的數據量(網格密度)，修正係數ξ∈(0,1)，n是在線隊列長度，G為非空網格的數量。反之，當該網格為稀疏網格。根據新增和丟棄的樣本數據動態維護密度網格集合，存儲在一棵高度平衡的紅黑樹中。密度網絡集合為離線階段的權重K-means聚類提供服務。
經過在線網格維護過程，原始數據的統計信息被保存在一個網格六元組內，即元組(α,LS,SS,g*,σ2,flag)，使得n個樣本數據被合併為G個網格重心點，以提高計算效率，避免不可控的累計誤差。圖2為網格重心點示意圖，a1、a2、b1和b2網格的數據重心即數據均值點分別為和flag代表網格的密度標誌，1為密度網格，0為稀疏網格。
李存華等推導了標準核密度估計和基於網格重心的核密度估計之間的MISE(均方積分誤差)上界為：
上式表明MISE量級為ο(δ4)。當δ→0，該誤差被有效控制遠小於(標準核密度估計與真實數據流密度之間的MISE)，說明基於網格重心的核密度估計精度較高且誤差收斂。如果真實分布不是高偏和超峰分布且處理的樣本數量n＜104，網格寬度經驗值為0.05至0.15。
C、離線聚類過程：每隔固定時間間隔gap進入並發處理的離線階段，該時間間隔的最小值設定為大於處理一次K-means聚類、核參數優化和查詢點密度估計等花費的時間之和，主要由算法的執行效率和實際應用需要的查詢點分布數量決定。利用權重K-means算法對網格重心點進行聚類，該過程由兩階段迭代實現。令表示用於劃分到m個聚類的G個非空網格重心點的集合，從在線階段得到的密度網格集合中選取空間位置均勻分布的m個密度網格的重心點作為初始聚類的中心，Sl代表網格集合的第l個聚類。按照空間位置而不是隨機選擇初始聚類中心的目的是為了減小出現局部次優解的可能性和快速收斂。m經驗值取為數據流分布峰數的2～3倍，一般情況下m≤50。第一階段以兩點間歐氏距離最短為原則將G個網格重心點聚類到m個聚類中心，通過求取以下代價函數的最小值確定：
式中代表第gj個網格重心點到第l個聚類中心的歐式距離。
第二階段根據每個聚類集合Sl包含的網格元素的權重和空間位置重新計算m個聚類的中心，由以下公式確定：
式中代表第gj個網格的權重(數據量)。權重K-means算法在兩個階段之間來回迭代執行，直到在聚類分配上沒有進一步的變化為止，輸出結果為圖3為聚類中心示意圖，聚類集合Sl包含網格a1、a2、b1和b2，聚類中心由這些網格的重心點和的均值決定。
D、離線優化過程：利用M-MMCKDE算法對聚類後的網格進行優化。M-MMCKDE使用一個新的聚類優化核代替權重K-means算法得到的每個聚類中全部的網格重心核，目標是兩者之間誤差的極小化。即將原有的G個網格重心核劃分為m個子塊{S1,S2,…,Sm}，每個子塊用一個聚類優化核來近似估計網格重心核中相近的若干核的總和。如圖4離線階段所示，假設m＝3，這3個聚類優化核分別對應3、4、4個相近的網格重心核。據此操作使得後續查詢點核密度估計的計算複雜度從ο(GQ)降低為ο(mQ)。通過反覆調用求取聚類優化核係數、高斯核帶寬和聚類點的迭代公式，將網格置於合適的聚類中，縮小網格重心核與聚類優化核之間的距離，聚類優化核可以漸次逼近全體網格重心核。得到的聚類優化核作為查詢點核密度估計的輸入。
由於高斯核的光滑性，使得採用高斯核作為核函數的密度估計網格分箱規則對於偏差沒有顯著影響。因此，採用高斯核作為核函數K(·)。按照時間順序從數據流中採樣的n個獨立同分布的樣本點V1,V2,…,Vn存儲於在線隊列，它們分別映射到對應的網格的重心點，基於聚類中網格重心的d維核密度估計由以下公式確定：
式中，m是聚類數量，Sl代表非空網格集合的第l個聚類，代表Sl中第gj個網格的權值，是第gj個網格的重心點的第k維度值，是第gj個網格在第k維的核帶寬。對第l個聚類，分塊近似聚類使用聚類優化核代替其中全部網格重心核的總和其中hl,k是第l個聚類優化核第k維帶寬，G亦為高斯核。令使g(X)逼近L2準則用於評估g(X)和之間的誤差，以使誤差達到最小，第l個聚類優化核的最小誤差上界由以下公式確定：
使用公式化簡上式，得到：
目標是求解第l個聚類優化核的係數βl、高斯核寬hl,k和聚類點tl,k的優化迭代公式。將βl看作變量，令得出：
將式(2)代入式(1)，得出：
令則：
令則：
分塊近似聚類與最近核距離聚類是等價的，即在使用聚類優化核代替所有網格重心核時，到某個聚類中心最近的網格重心核就被聚為那一類，與權重K-means算法思路一致。令網格重心核與聚類優化核之間的距離平方由以下公式確定：
通過反覆迭代調用求取的βl，tl,k和hl,k公式，將網格置於合適的聚類中，縮小網格重心核與聚類優化核之間的距離，本地最優g(X)對應的βl，tl,k和hl,k可以漸次得到，逼近具體步驟由算法1描述：
算法1.M-MMCKDE算法
輸入：權重K-means得到的聚類集合及全體非空網格的重心核
輸出：聚類優化核
令初始核距離誤差ζ＝1010。以下步驟11～15，依次遍歷每個聚類核集合。
步驟11，為聚類核參數賦初值，即
步驟12，根據式(4)迭代計算tl,k的值，直到相鄰兩次計算的絕對值差值小於0.0001。
步驟13，根據式(5)迭代計算的值，直到相鄰兩次計算的絕對值差值小於0.0001。
步驟14，檢查步驟12和步驟13迭代的次數，只要任意1個步驟的迭代次數超過1次，返回步驟12繼續執行。
步驟15，根據式(2)計算βl的值。
步驟16，計算上述步驟11～15獲得的的聚類誤差。對每個輸入組合根據式(6)計算與每個聚類中心點之間的距離。將歸類到距離最近的那一類，並記下誤差令計算ζnew與ζ絕對值之差，如果大於0.001ζnew，則將ζnew賦值給ζ，返回步驟11。否則結束，得到最終的聚類優化核模型：
網格重心核的帶寬由Scott規則確定：
其中是第k維Scott核帶寬，σk是在線隊列n個數據樣本第k維的標準差，d為總維數。
E、離線核密度估計過程：計算m個聚類優化核對查詢點核密度的累計，得到最終的數據流核密度估計的結果，由以下公式確定：
式中，X＝(x1,…,xd)為單個查詢點。
利用高斯函數的3σ規則，在計算每個聚類優化核對查詢點的影響時，只需要計算核中心tl周圍3倍hl範圍內的查詢點即可，大幅減少查詢點密度計算的負載。具體步驟由算法2描述：
算法2.KDE算法
輸入：全體查詢點集合。
輸出：全體查詢點密度估計值。
步驟21，所有查詢點的密度賦初值為0。
步驟22，遍歷m個聚類優化核，搜索核中心周圍3倍核帶寬範圍內的查詢點，累加該核對相應查詢點的密度估計，最終得到全體查詢點密度估計值。
GCOKDE算法融合了網格、聚類和優化技術以增強數據流密度估計，圖4展示了整體框架。隨時間抵達的樣本順序進入時間隊列，該隊列長度n，先進先出。每一時刻隊列頭和尾中樣本對應網格的特徵向量將會被刷新。換言之，隊列尾部存儲最新樣本，對應的網格累積相應的特徵向量。同時，隊列頭部保存了在下一個時刻即將丟棄的歷史樣本，該樣本的信息會從其對應網格的特徵向量中清除。在線階段上述處理保證了網格中存有樣本的動態統計信息。當達到時間間隔點，離線階段處理並發啟動，相鄰網格間核合併和優化操作被觸發。整體步驟由算法3描述：
算法3.GCOKDE算法
輸入：數據流樣本序列V＝{V1,V2,…,Vi,…}，參數δ,n,gap,ξ。
輸出：所有查詢點的密度。
步驟31，將新抵達的數據Vnew＝(vnew,1,vnew,2,…,vnew,d)插入隊列尾部，並映射到對應的網格，更新網格六元組。如果將該網格置入密度網格集合。
步驟32，刪除隊列頭部數據，。更新該數據對應的網格六元組。如果該網格是密度網格並且將其從密度網格集合移除，返回步驟31，等待下一個數據到達時刻。
步驟3，如果離線計算時間gap到，並發調用權重K-means得到初步的聚類優化核，隨後調用M-MMCKDE得到聚類優化核，最後調用KDE算法得到所有查詢點的密度。
以下為本方案中使用到的一些定義說明：
定義1(簡單分箱規則):將d維實數空間Rd的每個維度進行等寬劃分，從而將Rd劃分為若干依次相鄰且互不相交的超方體網格的集合。劃分的依據為分箱函數族式中，gj＝(j1,…,ji,…,jd)代表網格序號，δ＝(δ1,…,δi,…,δd)代表網格寬度，Zd為d維整數空間。圖1為2維實數空間R2的簡單分箱規則的網格劃分。
定義2(網格特徵向量):描述落入網格中數據的統計特徵，可以累加計算。其中α為映射到網格的數據權重，LS是映射到網格的數據的線性和，SS是映射到網格的數據的平方和。
定義3(網格重心點):指網格中全體數據的均值點，其中各維度的均值計算公式為式中，為網格gj第i維數據的位置，為網格gj第i維數據的線性和，為網格gj的數據量權值。圖2為網格重心點示意圖。
定義4(在線網格維護時間)：指處理每個數據流樣本的時間片，與數據流到達的頻率相關。由數據接收、網格映射和標記密度網格等時間開銷組成，這些步驟可以在下一個樣本到達之前的常數時間內結束。由於該常數時間非常短，因此與算法的執行效率無關。
定義5(MISE)：指均方積分誤差，用作評估估計質量，如下定義：
式中，指ρ密度估計技術,X1,…XQ是Q個查詢點。
定義6(離線計算間隔時間gap):兩個相鄰離線計算間隔點之間的時間片，與算法的執行效率有關。該時間片的最小值必須大於處理一次權重K-means聚類、核參數優化和查詢點密度估計等時間開銷之和。
定義7(聚類中心):指聚類中全體網格重心的均值點，其中各維度的均值計算公式為式中，為第l個聚類第i維位置，為隸屬於聚類l的網格gj第i維數據的均值，為聚類l的數據權重。圖3為聚類中心示意圖。
定義8(查詢點):指核密度估計查詢點，由人為選取的在Rd空間各維度等間隔排列的坐標點構成，計算這些查詢點的核密度估計值得到實時數據流密度估計的最終結果。
定義9(單維標準核密度估計):對從真實密度f中採樣的n個獨立同分布(i.i.d)的樣本點v1,v2,…,vn，帶寬h，核函數K(·)，單維標準核密度估計公式定義如下:
式中，核函數K(·)滿足以下條件：
K(s)≥0,K(s)＝K(-s),∫K(s)ds＝1，∫sK(s)ds＝0,∫s2K(s)ds＜∞
定義10(d維積核核密度估計)：對從真實密度f中採樣的n個獨立同分布(i.i.d)的樣本點V1,V2,…,Vn，帶寬向量h＝(h1,…,hd)，積核函數d維積核核密度估計公式定義如下:
式中，X＝(x1…xd)是d維查詢點,vi,k是第i個樣本的k維度值,hk是帶寬的k維度正值。
定義11(高斯核):核函數採用高斯函數，即
定義12(基於聚類中網格重心的d維核密度估計)：從在線數據映射得到的網格重心點出發，基於聚類的d維核密度估計公式為
式中，m是聚類數量，Sl代表非空網格集合的第l個聚類，代表Sl中第gj個網格的權值，是第gj個網格在第k維的數據均值，是第gj個網格在第k維的核帶寬。
定義13(聚類優化核)：用經過聚類優化過程的形如的核代替聚類中全部網格重心核的總和稱為聚類優化核。
定理1：令分塊近似聚類核密度估計函數基於聚類中網格重心的核密度估計函數則兩者間L2準則的最小誤差上界由以下公式確定：
證明：原始在線隊列中樣本數據量n不影響計算結果，不妨令ng(X)代替g(X)，代替則L2準則定義的兩者間最小誤差為
通過使用柯西不等式可得：
上式表明聚類後的總誤差的上界，由每個聚類核誤差上界之和組成，即由於各組成部分的解變量相互獨立，因此優化上界可以轉化為優化其各組成部分，即
本文中所描述的具體實施例僅僅是對本發明精神作舉例說明。本發明所屬技術領域的技術人員可以對所描述的具體實施例做各種各樣的修改或補充或採用類似的方式替代，但並不會偏離本發明的精神或者超越所附權利要求書所定義的範圍。
儘管本文較多地使用了網格、聚類、優化等術語，但並不排除使用其它術語的可能性。使用這些術語僅僅是為了更方便地描述和解釋本發明的本質；把它們解釋成任何一種附加的限制都是與本發明精神相違背的。