国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

多維序列模式挖掘算法分析

2014-07-22 01:07:10妍,劉
關(guān)鍵詞:赤峰投影閾值

鄒 妍,劉 燕

(赤峰學(xué)院 計(jì)算機(jī)與信息工程學(xué)院,內(nèi)蒙古 赤峰 024000)

多維序列模式挖掘算法分析

鄒 妍,劉 燕

(赤峰學(xué)院 計(jì)算機(jī)與信息工程學(xué)院,內(nèi)蒙古 赤峰 024000)

多維序列模式挖掘是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重要分支.首先給出了多維序列模式挖掘的相關(guān)定義;其次對(duì)典型的多維序列模式挖掘算法進(jìn)行了總體歸納,并對(duì)在此基礎(chǔ)上發(fā)展起來(lái)的幾種多維序列模式挖掘算法的改良性能進(jìn)行了分析;最后展望其未來(lái)發(fā)展方向.

數(shù)據(jù)挖掘;多維序列模式;挖掘算法

1 引言

數(shù)據(jù)挖掘作為知識(shí)發(fā)現(xiàn)的核心步驟,旨在從海量數(shù)據(jù)中提取有效的、潛在有用的、易于理解的知識(shí).序列模式挖掘是數(shù)據(jù)挖掘中非常重要的一個(gè)研究領(lǐng)域,最早是由R.Agrawal和R.Srikant在針對(duì)超市中購(gòu)物籃數(shù)據(jù)的分析提出來(lái)的[1].這類模式有著廣泛的應(yīng)用,如客戶購(gòu)買行為模式的分析、Web訪問模式的預(yù)測(cè)、疾病診斷、自然災(zāi)害預(yù)測(cè)、DNA序列分析等.多維序列模式挖掘是在序列模式挖掘基礎(chǔ)上考慮了其它一些維信息,像在顧客購(gòu)買行為分析中考慮到顧客的年齡、性別等信息,這樣的模式融合了更多的信息,應(yīng)用價(jià)值更高.經(jīng)過(guò)多年的發(fā)展,對(duì)多維序列模式的研究取得了比較大的進(jìn)步,研究者們提出了很多性能良好的算法.本文首先對(duì)三種經(jīng)典多維序列模式挖掘算法進(jìn)行總體歸納,接著對(duì)在這三種經(jīng)典算法基礎(chǔ)上發(fā)展起來(lái)的Seq-mdp算法、MSP算法及基于單基2維概念格的多維序列模式挖掘算法(不妨稱之為TDCL-SB)進(jìn)行了分析總結(jié).最后對(duì)未來(lái)的研究重點(diǎn)進(jìn)行了展望.

2 多維序列模式挖掘相關(guān)定義

多維序列模式是從序列模式發(fā)展來(lái)的,是在序列模式一維挖掘的基礎(chǔ)上考慮了多維因素,使挖掘出的序列模式融合了更多的信息,具有更高的應(yīng)用價(jià)值[2].多維序列數(shù)據(jù)庫(kù)具有如下模式(RID,A1,…, Am,S),其中RID作為主鍵(Primary key).A1,…,Am是維,S是數(shù)據(jù)序列域.以*作為元符號(hào)(meta-symbol)表示不屬于維A1,…,Am域的值.一個(gè)多維序列可表示為p=(a1,…,am,s),其中ai∈(Ai∪{*})(1≤i≤m),s是一個(gè)序列.

表1 多維序列數(shù)據(jù)庫(kù)實(shí)例

定義1對(duì)于多維序列p=(a1,…,am,s)和數(shù)據(jù)庫(kù)元組t=(x1,…,xm,si),當(dāng)且僅當(dāng)ai=xi或ai=*(1≤i≤m),并且s?si時(shí),稱t包含p.在多維序列數(shù)據(jù)庫(kù)S中,包含p的元組個(gè)數(shù)稱為p的支持?jǐn)?shù),記為support(p).給定最小支持度閾值minsup,如果support(p)≥minsup,則稱p為多維序列模式.

定義2多維序列模式p=(a1,…,am,s)中的多維信息M=(a1,…,am)稱為多維模式(multi-dimensional patterns或MD-patterns).若a1,…,am中有n個(gè)(n≤m)不是*,則稱M是一個(gè)n-維模式.設(shè)有i-維模式Mi=(a1,…,am)和j-維模式Mj=(b1,…,bm),其中,若對(duì)于所有不為*的ak(1≤k≤m)一定有ak=bk,則稱Mi是Mj的一個(gè)子模式(sub-pattern),而Mj是Mi的一個(gè)父模式(super-pattern).

多維序列模式挖掘的任務(wù)就是從多維序列模式數(shù)據(jù)庫(kù)中尋找出所有的滿足最小支持度的多維序列模式.一個(gè)多維序列數(shù)據(jù)庫(kù)實(shí)例如表1所示,它記錄了顧客的購(gòu)買歷史及相關(guān)屬性.Tid為序列號(hào),包含3個(gè)維,消費(fèi)群體、城市和年齡.假定A,B,…,H為顧客所購(gòu)買的項(xiàng)目.從表1可以看出,多維序列P=(*,赤峰,*,)被特集(1,商人,赤峰,中年,<(BD)CBA>),(2,自由職業(yè)者,赤峰,老年,<(BF) (CE)(FG)>)和(3,商人,赤峰,中年,<(AH)ABF>)所包含.P的支持度為3,如果給定的最小支持?jǐn)?shù)為2,則P是一個(gè)多維序列模式.

3 多維序列模式挖掘算法分析

3.1 三種經(jīng)典多維序列模式挖掘算法

文獻(xiàn)[2]提出了三種經(jīng)典的多維序列模式挖掘算法:UniSeq,Seq-Dim和Dim-Seq.總體上,可以將多維序列模式挖掘算法劃分為兩類:一類是將多維分析方法和序列模式挖掘算法相結(jié)合的方法;另一類是先將多維信息集成到序列中,再對(duì)新集成的序列進(jìn)行挖掘.Seq-Dim和Dim-Seq屬于第一類,U-niSeq屬于后一類.

雖然,Seq-Dim和Dim-Seq屬于同一類算法,但是它們也有區(qū)別,關(guān)鍵在于處理步驟的順序不同.Seq-Dim算法的挖掘過(guò)程具有明確的目的性,先挖掘原始的序列模式,然后再利用BUC(Bottom-UP Computation)[3]算法挖掘序列投影數(shù)據(jù)庫(kù)的多維信息模式.由于在挖掘維度較高的多維模式時(shí),BUC算法的效率要高于PreFixSpan算法[4](該算法是Uniseq所采用的多維序列模式挖掘算法),因此,Seq-Dim算法在挖掘高維度的多維序列模式時(shí)更具優(yōu)勢(shì).

而Dim-Seq算法則是先挖掘多維信息模式,再生成相應(yīng)的多維模式投影數(shù)據(jù)庫(kù)來(lái)挖掘序列模式.其缺點(diǎn)是顯而易見的,首先,在第一個(gè)步驟中產(chǎn)生的多維信息模式并不能產(chǎn)生多維序列模式,這就造成了大量的浪費(fèi).其次,該算法沒有對(duì)序列模式進(jìn)行優(yōu)化,當(dāng)出現(xiàn)高維度的情況時(shí),該算法的執(zhí)行開銷會(huì)劇增.

UniSeq算法的基本思想是先把多維信息合并到序列數(shù)據(jù)庫(kù)中,再對(duì)新集成的序列數(shù)據(jù)庫(kù)進(jìn)行挖掘,最后利用經(jīng)典序列模式挖掘算法PreFixSpan對(duì)新的序列數(shù)據(jù)庫(kù)進(jìn)行挖掘.該算法的優(yōu)點(diǎn)是將所有的多維信息集成到序列數(shù)據(jù)庫(kù)中,容易實(shí)現(xiàn)和理解.且利用PreFixSpan算法,省去了在轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)過(guò)程及挖掘過(guò)程中的資源消耗.該算法適合于序列維度較低的情況.

3.2 Seq-mdp算法

從對(duì)三種經(jīng)典多維序列模式挖掘算法的分析中可以看出,Seq-Dim算法是較高效的一種算法.但該算法有缺點(diǎn),由于在挖掘多維模式時(shí)要多次掃描投影數(shù)據(jù)庫(kù),因此在維度高、數(shù)據(jù)量大時(shí),時(shí)間開銷也大.因此,研究者在文獻(xiàn)[5]中提出了一種基于連接的多維序列模式挖掘算法(以下稱之為Seq-mdp).

Seq-mdp算法與Seq-Dim算法的相似之處在于:也是先挖掘一般序列模式,再對(duì)每個(gè)序列模式生成該模式的維信息投影數(shù)據(jù)庫(kù),然后再在投影數(shù)據(jù)庫(kù)中挖掘多維模式,從而得到多維序列模式.

與Seq-Dim算法相比,改進(jìn)的地方在于:挖掘多維模式時(shí)采用一種以空間換取時(shí)間的策略,減少了挖掘多維模式的時(shí)間.但是,由于需要空間記錄頻繁項(xiàng)的相關(guān)信息用于后續(xù)的連接,因而在空間上開銷較大.

從Seq-mdp算法的描述可以看出,只需掃描一次投影數(shù)據(jù)庫(kù)即可得到所有的多維模式.該算法主要是通過(guò)記錄支持每個(gè)頻繁1-項(xiàng)集的元組及其屬性的方法,所記錄的這些內(nèi)容以備后續(xù)連接之用.在掃描投影數(shù)據(jù)庫(kù)時(shí),得到頻繁1-項(xiàng)集及上述相關(guān)信息,由頻繁(k-1)-項(xiàng)集(其中,k>1)做連接生成頻繁k-項(xiàng)集,再通過(guò)頻繁k-項(xiàng)集中的頻繁項(xiàng)就可以得到一個(gè)k-維模式,由此得到所有的k維模式.該算法減少了掃描投影數(shù)據(jù)庫(kù)的次數(shù),只對(duì)不斷減小的頻繁(k-1)-項(xiàng)集掃描,在時(shí)間復(fù)雜度方面明顯優(yōu)于Seq-Dim算法.

3.3 MSP算法

文獻(xiàn)[6]通過(guò)設(shè)置閾值及對(duì)比模式類與序列項(xiàng)的方法提出了多維序列模式挖掘算法MSP.

MSP算法給出了規(guī)則的支持度及規(guī)則的確信度、帶有最小支持度閾值的頻繁規(guī)則、序列模式支持度閾值、兩序列的相異度、相似序列、多維序列規(guī)則及模式類的相關(guān)定義.算法包括三個(gè)步驟:通過(guò)設(shè)置序列模式的支持度閾值、序列相異度閾值及屬性的支持度閾值,挖掘數(shù)據(jù)集中的最大頻繁模式,求出各模式類所包含的屬性,根據(jù)屬性的支持度閾值確定哪些屬性用于生成多維規(guī)則的前件;比較數(shù)據(jù)中各序列項(xiàng)序列與各模式類的包含與相似關(guān)系;按照一定的規(guī)則抽取與各模式類相關(guān)的屬性,進(jìn)而對(duì)規(guī)則進(jìn)行相應(yīng)的化簡(jiǎn),給出以屬性為前件、模式類為后件的多維序列規(guī)則為形式的多維序列模式挖掘結(jié)果.

通過(guò)與文獻(xiàn)[7]提出的基于數(shù)據(jù)特性的多維序列模式挖掘算法MSRC在特點(diǎn)及運(yùn)行時(shí)間上的比較,可以看出在規(guī)則冗余方面有了改進(jìn),化簡(jiǎn)的規(guī)則能更好的反映屬性與序列項(xiàng)序列之間的關(guān)系,能挖掘出更有意義的多維序列模式;另外,在時(shí)間復(fù)雜度上MSP算法更具優(yōu)勢(shì),該算法更有效.且該算法可以應(yīng)用到空間多維序列及多關(guān)系多維序列模式的挖掘上,具有較好的可擴(kuò)展性.

3.4 TDCL-SB

文獻(xiàn)[8]在多維概念格數(shù)據(jù)模型的基礎(chǔ)上,提出了多維序列模式的增量挖掘算法TDCL-SB.多維概念格是針對(duì)多維序列模式挖掘應(yīng)用而提出的新的數(shù)據(jù)結(jié)構(gòu),是對(duì)概念格和有序概念格的泛化.文獻(xiàn)[7]提出的TDCL-SB算法通過(guò)增量式構(gòu)建單基2維概念格來(lái)發(fā)現(xiàn)多維序列模式.有了多維格這種新的數(shù)據(jù)結(jié)構(gòu),使得整個(gè)挖掘過(guò)程變得高效,無(wú)論是有序信息維,還是無(wú)序信息維,其處理都是在多維格結(jié)構(gòu)上進(jìn)行的,而無(wú)需像傳統(tǒng)算法那樣針對(duì)不同的數(shù)據(jù)結(jié)構(gòu)采用不同的處理策略,另外,該算法僅需掃描一次數(shù)據(jù)庫(kù),并具有較好的增量特性.TDCL-SB算法在某銀行信用卡客戶的交易數(shù)據(jù)集上作了實(shí)際驗(yàn)證,實(shí)驗(yàn)結(jié)果表明,該算法具有以下優(yōu)點(diǎn):

(1)采用統(tǒng)一的數(shù)據(jù)模型實(shí)現(xiàn)一般序列模式與關(guān)聯(lián)模式的高效同步挖掘;

(2)算法具有增量特性,適用于數(shù)據(jù)集更新頻繁或用戶無(wú)法預(yù)先確定最小支持度約束范圍的應(yīng)用場(chǎng)合;

(3)算法生成的是具有實(shí)際應(yīng)用價(jià)值的最大頻繁序列模式.

4 總結(jié)

自多維序列模式挖掘的概念及經(jīng)典算法提出以來(lái),經(jīng)過(guò)近些年的發(fā)展,多維序列模式挖掘研究取得了較大的進(jìn)展,但仍然存在一些問題,比如與相關(guān)領(lǐng)域知識(shí)的結(jié)合不夠,針對(duì)海量數(shù)據(jù)時(shí)間開銷大、算法效率不高等.這些都是下一步需要解決的問題.多維序列模式挖掘有著廣闊的應(yīng)用前景,如何進(jìn)一步提高算法的挖掘性能,以及如何加入一些時(shí)間和分類等約束,是有待于進(jìn)一步研究的問題.

〔1〕R.Agrawal,R.Srikant.M ining Sequential Patterns [C].In: Proceeding of the list International Conference on Data Engineering.TaiPei,1995: 3-14.

〔2〕Pinto H,Han J,Pei J,et al.M ulti-dimensional sequential pattern m ining[C]//Proc.of athe 10th International Conference on Information and Know ledge M anagement.Atlanta,New York:ACM Press,2001:81-88.

〔3〕K.Beyer,R.Ramakrishnan.Botton-up computation of sparse and iceberg cubes[C].In:Proc. 1999ACM-SIGMODInt.Conf.Management of Data(SIGMOD’99),Philadelphia,PA,1999:359-370.

〔4〕Jian Pei,Jiawei Han,Behzad M ortazavi-Asi,HelenPinto.PrefixSpan:M ining Sequential Patterns Efficiently by Prefix-Projected Pattern[C]. IEEE,2001.

〔5〕肖仁財(cái).序列模式挖掘算法研究與實(shí)現(xiàn)[D].江蘇大學(xué),2007.17-30.

〔6〕李廣原,楊炳儒,等.多維序列模式挖掘算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2011,32(7):2378-2379.

〔7〕Lionel Savary,Karine Zeitouni.M ining multidimensional sequential rules:a characterization based approach[C].IEEE MCD05,2005:99-102.

〔8〕金陽(yáng),左萬(wàn)利.多維概念格與多維序列模式的增量挖掘[J].計(jì)算機(jī)研究與發(fā)展,2007,44(11):1818-1824.

TP311.13

A

1673-260X(2014)04-0034-03

內(nèi)蒙古自治區(qū)自然科學(xué)基金項(xiàng)目資助(2011MS0914)

猜你喜歡
赤峰投影閾值
赤峰學(xué)院學(xué)生書法作品
赤峰學(xué)院教師書法作品
赤峰家育種豬生態(tài)科技集團(tuán)有限公司
解變分不等式的一種二次投影算法
基于最大相關(guān)熵的簇稀疏仿射投影算法
小波閾值去噪在深小孔鉆削聲發(fā)射信號(hào)處理中的應(yīng)用
找投影
找投影
基于自適應(yīng)閾值和連通域的隧道裂縫提取
比值遙感蝕變信息提取及閾值確定(插圖)
河北遙感(2017年2期)2017-08-07 14:49:00
通海县| 阿图什市| 南京市| 杭州市| 嘉义县| 津市市| 中阳县| 达孜县| 呼伦贝尔市| 榕江县| 沁源县| 临海市| 宁阳县| 东阿县| 自治县| 密云县| 涞源县| 柳林县| 中阳县| 偏关县| 固阳县| 兰西县| 马鞍山市| 连云港市| 寿阳县| 玉溪市| 郓城县| 三河市| 安阳市| 河曲县| 临高县| 英超| 枝江市| 融水| 东安县| 西贡区| 梅河口市| 宁阳县| 仪征市| 漳浦县| 望江县|