[發(fā)明專利]一種高效的流數(shù)據(jù)模式挖掘方法

有效

• 申請?zhí)枺?/td>: 201811304324.9
• 申請日: 2018-11-03
• 公開（公告）號: CN109558424B
• 公開（公告）日: 2023-04-18
• 發(fā)明（設(shè)計）人: 周水庚;陳金勇;嚴傳續(xù);劉朝斌;陳勇
• 申請（專利權(quán)）人: 復(fù)旦大學(xué)
• 主分類號: G06F16/2455
• 分類號: G06F16/2455;G06F18/241;G06F18/23
• 代理公司: 上海正旦專利代理有限公司 31200
• 代理人: 陸飛;陸尤

1.一種高效的流數(shù)據(jù)模式挖掘方法，其特征在于，以最小化驗證誤差為聚類劃分標(biāo)準(zhǔn)，通過兩個步驟找出流數(shù)據(jù)中的隱藏模型：稱其為驗證誤差最小化方法；具體步驟如下：

(1)序列聚類；基于增強動態(tài)規(guī)劃方法，找出將數(shù)據(jù)流劃分為多個連續(xù)數(shù)據(jù)段的最優(yōu)劃分，即：使驗證誤差最小的劃分；其中，每個數(shù)據(jù)段是流數(shù)據(jù)的一個連續(xù)片段，對應(yīng)著一個模型生成的一個實例；

(2)迭代聚類；基于類似于EM算法的方法，迭代聚類算法，不斷地對序列聚類劃分的數(shù)據(jù)段進行再聚類，在每個聚類上訓(xùn)練模型，直至收斂，得到流數(shù)據(jù)中的所有隱藏模型；

其中，采用驗證誤差來作為聚類劃分標(biāo)準(zhǔn)，其目標(biāo)函數(shù)為：

其中，m＝1+|{(d_i,d_i+1)|d_i∈D_j,d_i+1∈D_k,j≠k}|，為數(shù)據(jù)段個數(shù)；δ≥0是一個調(diào)整數(shù)據(jù)段個數(shù)的規(guī)范化參數(shù)；

式(1)中，P為數(shù)據(jù)集D＝{d₁,...,d_n}的一個不相交的聚類，即令為類D_i的模型；為模型在數(shù)據(jù)集D_i上的誤差，定義為目標(biāo)是找到令公式(1)最小化的P。

2.根據(jù)權(quán)利要求1所述的高效的流數(shù)據(jù)模式挖掘方法，其特征在于，步驟(1)所述序列聚類的流程為：

令D_i,j表示從d_i到d_j的子序列，令P_i,j是使得式(1)最小的最優(yōu)劃分；序列聚類的目標(biāo)是找到P_1,n，即使得整個序列的VEM最小的劃分；對此問題，采用動態(tài)規(guī)劃求解；假設(shè)已知道D_1,j和D_j+1,n的最優(yōu)序列聚類為P_1,j和P_j+1,n(1≤jn)，求整個序列的聚類P_1,n；結(jié)果有兩種情況：整個序列為最優(yōu)聚類，或者P_1,j與P_j+1,n的所有子序列聚類構(gòu)成最優(yōu)聚類；接下來只需求和的最小值對應(yīng)的劃分，即為最優(yōu)序列聚類結(jié)果；

依據(jù)廣覆蓋和多樣性的原則，預(yù)選部分數(shù)據(jù)序列，稱之為樞紐段，并在樞紐段上計算出相應(yīng)的數(shù)據(jù)模型，稱之為候選模型；選擇γ和p兩個參數(shù)控制樞紐段的生成；γ控制k層樞紐段為k-1層樞紐段長度的多少倍，控制樞紐段長度的多樣性，p為同層相鄰樞紐段首尾數(shù)據(jù)標(biāo)號之差，控制樞紐段相互交疊程度；每個樞紐段的候選模型為表示第k層第i個模型；接下來，對于任意數(shù)據(jù)序列D_i,j，為其指派一個最接近于目標(biāo)模型的候選模型H(D_i,j)；H(D_i,j)是包含在D_i,j中最長樞紐段上的模型，如果有多個符合此條件的樞紐段，則選擇最后一個樞紐段上的模型；

模型指派后，將式(1)中所有段上學(xué)得的模型替換為對應(yīng)的備選模型H(D_i,j)，新的目標(biāo)函數(shù)為：

找式(2)下的最優(yōu)劃分，就是找使Q*(P_1,n)最小的最優(yōu)劃分P_1,n；候選模型有k層，按照問題規(guī)模和層次逐步求解子問題；為描述方便，下面用Q*_i表示Q*(P_1,i)，目標(biāo)是求Q*_n；

如果給定數(shù)據(jù)段的指派模型在層次k上，則將對應(yīng)的劃分記為用表示層次k上的最后一個候選模型；用表示劃分的誤差，則有：

于是，將求解Q*_n的問題轉(zhuǎn)化為求解對任意i,k求解子問題Q*_i,下面說明怎樣找出使達到最小的劃分注意到最后一個數(shù)據(jù)段的指派模型在k層上，分以下兩種情形進行討論：

(1)當(dāng)時，最后一個數(shù)據(jù)段的指定模型是固定的，因此僅需在最后一個數(shù)據(jù)段后面加一條數(shù)據(jù)d_i，根據(jù)由下式求得：

(2)當(dāng)時，需要找到使達到最小的最后一個數(shù)據(jù)段的起始位置，這個位置x的范圍在i′一直到最左端位置i-b_k+1之間，且有因此，通過在P_1,x-1添加一個新的數(shù)據(jù)段D_x,i得到此時的根據(jù)由下式求得：

3.根據(jù)權(quán)利要求2所述的高效的流數(shù)據(jù)模式挖掘方法，其特征在于，步驟(2)所述迭代聚類的流程為：

由序列聚類算法輸出的每個數(shù)據(jù)段表示隱藏模型的一個快照，一個模型可能有多個快照；迭代聚類的目標(biāo)是將這些快照聚類到不同模型下；將該問題的目標(biāo)進行如下形式化：給定數(shù)據(jù)段序列P＝{D₁,...,D_m}，找到一個數(shù)據(jù)段序列的劃分使下式的劃分誤差達到最小：

為求解上述問題，基于期望最大化方法的工作原理，設(shè)計迭代聚類算法，在線性時間內(nèi)求出使Q(T)達到最小的近似解，算法具體過程如下：

維護一個模型集初始時為空；然后交替執(zhí)行賦值步和更新步，直到收斂，賦值步賦給每個數(shù)據(jù)段最有可能的模型，更新步基于賦值步的輸出結(jié)果重新學(xué)習(xí)每個模型：

(1)賦值步；從中賦給每個數(shù)據(jù)段D_i在其上具有最小驗證誤差的模型；在初始階段，是空的，先在所有數(shù)據(jù)段D_i上學(xué)得一個模型對每個數(shù)據(jù)段D_i，從中找到使驗證誤差ε(O,D_i)最小的模型O，并把D_i賦給模型O；如果O不在中則將其加入其中；

(2)更新步；更新中的模型，從現(xiàn)有模型M_i中用所有賦給這個模型的數(shù)據(jù)段學(xué)得新模型用新模型取代舊模型，為保證收斂性，只有新模型的驗證誤差遠比舊模型小時才用新模型，否則保留舊模型，丟棄新模型；如果在賦值步有模型沒有數(shù)據(jù)段賦給它，這個模型從模型集中剔除。