• / 9
  • 下載費用:30 金幣  

面向不確定數據的閉序列挖掘方法.pdf

摘要
申請專利號:

CN201510315008.1

申請日:

2015.06.09

公開號:

CN104915419A

公開日:

2015.09.16

當前法律狀態:

撤回

有效性:

無權

法律詳情: 發明專利申請公布后的視為撤回IPC(主分類):G06F 17/30申請公布日:20150916|||實質審查的生效IPC(主分類):G06F 17/30申請日:20150609|||公開
IPC分類號: G06F17/30 主分類號: G06F17/30
申請人: 西北工業大學
發明人: 尤濤; 杜承烈; 王川文; 張利軍; 徐偉
地址: 710072陜西省西安市友誼西路127號
優先權:
專利代理機構: 西北工業大學專利中心61204 代理人: 王鮮凱
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201510315008.1

授權公告號:

||||||

法律狀態公告日:

2018.08.31|||2015.10.14|||2015.09.16

法律狀態類型:

發明專利申請公布后的視為撤回|||實質審查的生效|||公開

摘要

本發明公開了一種面向不確定數據的閉序列挖掘方法,用于解決現有面向不確定數據的閉序列挖掘方法精度差的技術問題。技術方案是首先將不確定數據成功地轉換為確定數據的序列挖掘,并從中剪枝掉那些非閉序列,再加上“概率頻繁”性質檢查過程中的剪枝技術,從而精確高效地挖掘出概率頻繁閉序列。

權利要求書

權利要求書
1.  一種面向不確定數據的閉序列挖掘方法,其特征在于包括以下步驟:
步驟一、生成頻繁序列FS的子集或者頻繁閉合序列FCS的超集頻繁閉合候選項FCC,保存在相應的內存當中;
剪枝的過程,首先通過執行i-拓展和s-拓展,遞歸的生成候選項并且進行支持度檢測,返回頻繁閉合候選集的FCC的一部分用p來進行表示,對生成的p序列進行i拓展和s拓展,在每次拓展之前,采用CheckAvoidable方法來判斷p序列是否需要被裁剪掉;
采用CheckAvoidable方法找出p=<a ej>和p’=<a ei ej>序列,即如果每次找到a序列后存在ej這樣的序列形式,序列中間肯定會存在ei項,這時能夠避免拓展這樣的p序列;
為了找到這種形式的序列,定義了兩種形式:l(s,p)和I(Dp)
l(s,p)是序列s對于p序列的所有剩余項數目綜合;
I(Dp)是對于整個數據庫來說,所有序列si(i=1,2,...,n)對于p序列的所有l(si,p)數目的總和;
如果存在p≤p',且I(Dp)=I(Dp’),則能夠判斷p和p’序列滿足上文假設的形式,能夠避免對于p序列的拓展;
利用后剪枝的方法,消除頻繁閉合候選項中所有的非閉合序列,最終獲得只含有頻繁閉合序列;
步驟二、由步驟一得到從不確定數據中挖掘出來所有的閉合序列,從所有的閉合序列中過濾掉非概率頻繁序列;
首先,計算一長度序列的頻繁概率,生成閉序列;然后基于序列的s-拓展和i-拓展理論,計算所有閉項集子集的概率頻繁,利用卷積的方法得到項集的頻次分布特征;最后,在序列生成的過程中,使用剪枝方法加快項集的生長過程。

說明書

說明書面向不確定數據的閉序列挖掘方法
技術領域
本發明涉及一種閉序列挖掘方法,特別是涉及一種面向不確定數據的閉序列挖掘方法。
背景技術
面向不確定數據的頻繁模式挖掘方法主要可分為三類:
1)期望計算法。
針對不確定數據的頻繁項集挖掘方法主要包括:基于傳統Aprior方法改造的U-Aprior方法、U-Aprior的剪枝算法、樹結構方法以及挖掘用戶期望概率項集的方法。
在確定數據流挖掘方法FP-stream基礎上,文獻“Leung C K S,Brajczuk D A.Efficient algorithms for mining constrained frequent patterns from uncertain data[C]//Proceedings of the 1st ACM SIGKDD Workshop on Knowledge Discovery from Uncertain Data.ACM,2009:9-18.”和“Leung C K S,Hao B.Mining of frequent itemsets from streams of uncertain data[C]//Data Engineering,2009.ICDE'09.IEEE 25th International Conference on.IEEE,2009:1663-1670.”提出了兩種不確定數據流頻繁項集挖掘方法:UF-streaming和SUF-growth方法。兩種方法的相同之處都是對每個數據項增加概率屬性,當窗口滑動時,帶有概率的數據項不斷更新到頻繁項集樹中,并通過計算期望支持度確定頻繁項集。而它們的區別是UF-streaming方法進行了剪枝。隨著窗口的滑動,兩方法均需占用大量存儲空間,而且處理速度較慢。
2)頻次分布計算法。
文獻“Zhang Q,Li F,Yi K.Finding frequent items in probabilistic data[C]//Proceedings of the 2008 ACM SIGMOD international conference on Management of data.ACM,2008:819-832.”提出了通過頻次分布計算支持度的方式來定義頻繁項,由于充分考慮了項集發生的分布特性,能夠得到更精確的頻繁項。DP(Dynamic Programming-based apriori algorithm)算法和DC(Divide-and-Conquer-based apriori algorithm)算法是目前基于頻次分布挖掘頻繁項集的代表算法。同樣由于頻次分布函數精確計算代價很大,故均采用一些剪枝方法。DC算法采用卷積技術,其算法復雜度較DP算法低。
Is-UFI算法將頻次分布計算方式引入到數據流環境中頻繁項的挖掘,算法采用理 論最大值模型預測未來基本窗口的期望支持度上界,再進行近似計算概率上界,并以此為依據對數據項進行動態過濾;最后對過濾后的數據項進行頻繁特性檢查;算法中采用了舊數據的卷積運算結果來提高計算效率。但是,上界計算中采用近似算法,容易導致精度的下降。
3)近似算法。
頻次分布計算復雜度高的特點催生了近似頻次分布計算方面的研究。其中,PDUApriori算法采用泊松分布近似頻次分布函數;NDUApriori和NDUH-Mine算法采用正態分布近似頻次分布函數。PDUApriori算法只能得出哪些是概率頻繁項集,而不能得出具體的概率值;NDUApriori算法在稠密大量數據庫中有很好的性能,但是在稀疏情況下是不可行的;NDUH-Mine算法在稀疏大量數據庫中比NDUApriori算法挖掘效率高。然而,無論哪種近似算法都只適用于數據規模較大的情況。
發明內容
為了克服現有面向不確定數據的閉序列挖掘方法精度差的不足,本發明提供一種面向不確定數據的閉序列挖掘方法。該方法首先將不確定數據成功地轉換為確定數據的序列挖掘,并從中剪枝掉那些非閉序列,再加上“概率頻繁”性質檢查過程中的剪枝技術,從而可以精確高效地挖掘概率頻繁閉序列。
本發明解決其技術問題所采用的技術方案是:一種面向不確定數據的閉序列挖掘方法,其特點是采用以下步驟:
步驟一、生成頻繁序列FS的子集或者頻繁閉合序列FCS的超集頻繁閉合候選項FCC,保存在相應的內存當中。
剪枝的過程,首先通過執行i-拓展和s-拓展,遞歸的生成候選項并且進行支持度檢測,返回頻繁閉合候選集的FCC的一部分用p來進行表示,對生成的p序列進行i拓展和s拓展,在每次拓展之前,采用CheckAvoidable方法來判斷p序列是否需要被裁剪掉。
采用CheckAvoidable方法找出p=<a ej>和p′=<a ei ej>序列,即如果每次找到a序列后存在ej這樣的序列形式,序列中間肯定會存在ei項,這時能夠避免拓展這樣的p序列。
為了找到這種形式的序列,定義了兩種形式:l(s,p)和I(Dp)
l(s,p)是序列s對于p序列的所有剩余項數目綜合。
I(Dp)是對于整個數據庫來說,所有序列si(i=1,2,...,n)對于p序列的所有l(si,p)數目的總和。
如果存在p≤p′,且I(Dp)=I(Dp′),則能夠判斷p和p’序列滿足上文假設的形式,能夠避免對于p序列的拓展。
利用后剪枝的方法,消除頻繁閉合候選項中所有的非閉合序列,最終獲得只含有頻繁閉合序列。
步驟二、由步驟一得到從不確定數據中挖掘出來所有的閉合序列,從所有的閉合序列中過濾掉非概率頻繁序列。
首先,計算一長度序列的頻繁概率,生成閉序列。然后基于序列的s-拓展和i-拓展理論,計算所有閉項集子集的概率頻繁,利用卷積的方法得到項集的頻次分布特征。最后,在序列生成的過程中,使用剪枝方法加快項集的生長過程。
本發明的有益效果是:該方法首先將不確定數據成功地轉換為確定數據的序列挖掘,并從中剪枝掉那些非閉序列,再加上“概率頻繁”性質檢查過程中的剪枝技術,從而精確高效地挖掘出概率頻繁閉序列。
下面結合附圖和具體實施方式對本發明作詳細說明。
附圖說明
圖1是本發明面向不確定數據的閉序列挖掘方法的流程圖。
圖2是本發明面向不確定數據的閉序列挖掘方法實施例圖。
具體實施方式
參照圖1-2。本發明面向不確定數據的閉序列挖掘方法涉及如下概念定義:
序列與支持度:令I={x1,x2,...,xm}為不同項集合,定義一個I的非空子集X(項或序列),一個序列S=<I1,I2,...,In>且Ii∈I,由此序列的長度可以定義為I在事務數據庫中的發生次數t稱為支持度,即support(X)。
頻繁序列:序列S是否為的頻繁的條件是S的支持度大于給定的支持度閾值minsup。
閉序列:S為閉序列的條件是不存在S的超集S’有support(S)=support(S′)。
可能世界模型是從不確定性數據中演化出很多確定的數據實例,成為可能世界實例。每一個可能世界實例是由確定的事務構成。不確定序列S在ti發生的概率為 P(I∈ti),此概率可以產生兩個可能世界實例,一個實例是S存在ti中,另一個實例是S不存在于ti中。各元組的任意合法組合均構成一個可能世界實例PWi。不確定事務互相獨立,則P(PWj)等于實例內的元組概率乘積和實例外的元組概率乘積:
P(PWj)=Πt∈l(Πx∈tP(x∈t)*Πx∈t(1-P(x∈t))),
且所有的可能世界實例的發生概率之和為1。
頻繁概率:給定支持度閾值min_sup,序列S的頻繁概率表示為PrF(S)。
PrF(S)=Pr{support(S)≥min-sup}
概率頻繁序列:給定支持度閾值min_sup、概率頻繁閾值pft,序列S是概率頻繁項集的條件是X的頻繁概率大于給定閾值。
Pr{support(S)≥min_sup}=PrF(S)>pft
閉概率:序列S是閉項集的概率表示為PrC(S),是存在閉序列S的所有可能世界的概率總和。
頻繁閉概率:序列S的頻繁閉概率表示為PrFC(S),是存在頻繁閉序列S的所有可能世界的概率總和。
概率頻繁閉序列:給出一個概率閉頻繁閾值pfct,存在序列S是概率頻繁閉序列的條件是S的頻繁閉概率大于給定閾值。
Pr{S is frequent closed itemset}=PrFC(S)>pfct
本發明面向不確定數據的閉序列挖掘方法具體步驟如下:
步驟一、生成頻繁序列FS的子集或者頻繁閉合序列FCS的超集頻繁閉合候選項FCC,保存在相應的內存當中。
剪枝的過程,首先通過執行i-拓展和s-拓展,遞歸的生成候選項并且進行支持度檢測,返回頻繁閉合候選集的FCC的一部分用p來進行表示,對生成的p序列進行i拓展和s拓展,在每次拓展之前,采用CheckAvoidable方法來判斷p序列是否需要被裁剪掉。
采用CheckAvoidable方法找出p=<a ej>和p′=<a ei ej>序列,即如果每次找到a序列后存在ej這樣的序列形式,序列中間肯定會存在ei項,這時能夠避免拓展這樣的p序列。
為了找到這種形式的序列,定義了兩種形式:l(s,p)和I(Dp)
l(s,p)是序列s對于p序列的所有剩余項數目綜合。
I(Dp)是對于整個數據庫來說,所有序列si(i=1,2,...,n)對于p序列的所有l(si,p)數目的總和。
如果存在p≤p′,且I(Dp)=I(Dp′),則能夠判斷p和p’序列滿足上文假設的形式,能夠避免對于p序列的拓展。
利用后剪枝的方法,消除頻繁閉合候選項中所有的非閉合序列,最終獲得只含有頻繁閉合序列。
步驟二、由步驟一得到從不確定數據中挖掘出來所有的閉合序列,從所有的閉合序列中過濾掉非概率頻繁序列。
首先,計算一長度序列的頻繁概率,生成閉序列。然后基于序列的s-拓展和i-拓展理論,計算所有閉項集子集的概率頻繁,利用卷積的方法得到項集的頻次分布特征。最后,在序列生成的過程中,使用剪枝方法加快項集的生長過程。
在傳感器網絡中頻繁閉項集挖掘在環境監測、關聯規則挖掘等領域有非常重要的應用。例如在溫度監測系統中某溫度值頻繁出現就會被認為是異常情況從而報警。由于傳感器自身的限制檢測的記錄是不確定的每一個監控記錄都會附加概率信息表示該記錄的可信程度。以表1為例,每行事務數據表示某傳感器記錄值及其概率。在傳感器數據中挖掘的頻繁閉序列可以得知傳感數據的一般模式,以便于異常情況的監測等。參照圖1的方法流程,挖掘概率頻繁閉序列。
表1不確定數據表

首先挖掘不確定數據對應的確定數據中的閉序列:按照閉序列的定義,可得到閉序列集合FCS={<(a)>,<(a)(ab)>}。
其次進行概率頻繁閉序列的過濾。本發明知道忽略概率的條件下,不確定數據中的閉序列的子集是等價于確定數據中的閉序列的。基于本發明的第一步,得到從不確定 數據中挖掘出來所有的閉序列。接著,從所有的閉序列中過濾掉一些非概率頻繁序列。首先,計算一長度序列的頻繁概率{{a},fp:0.834},{{b},fp:0.54}生成閉序列。然后,基于序列的s-拓展和i-拓展理論,計算所有閉序列子集的概率頻繁{<(a)(a)>,fp:0.54,fcp:0},{<(a)(b)>,fp:0.54,fcp:0},{<(aa)>,fp:0,fcp:0},{<(ab)>,fp:0.54,fcp:0}。特別的是,為了快速地計算單項序列的的概率頻繁,利用卷積的計算方式得到項集的頻次分布特征。最后,在序列生成的過程中,使用合理的剪枝技術將加快項集的生長過程。
最終獲得兩個概率頻繁閉序列{<(a)>,fcp:0.834},{<(a)(ab)>,fcp:0.54},它們的頻繁閉概率可以通過卷積方法計算;在結束所有的以{a}為前綴的搜索之后,對其它前綴繼續進行檢查。當可以停止任何序列的生長,也就是說,整個搜索列舉過程結束了。最后可以得到結果集:{<(a)>,fcp:0.834},{<(a)(ab)>,fcp:0.54}}。

關 鍵 詞:
面向 不確定 數據 序列 挖掘 方法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:面向不確定數據的閉序列挖掘方法.pdf
鏈接地址:http://www.rgyfuv.icu/p-6373505.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
山东11选5中奖结果走势图