頻繁模式挖掘系統(tǒng)的設(shè)計(jì)與開發(fā)

王楠楠，劉慧婷

(安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230601)

0 引 言

頻繁模式挖掘是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重要研究方向[1-2]，研究主要包括項(xiàng)目集合、項(xiàng)目序列等各種數(shù)據(jù)中的頻繁模式挖掘[3-4]。頻繁模式挖掘得到的結(jié)果不但可以用于關(guān)聯(lián)規(guī)則、文本分類等其他數(shù)據(jù)挖掘課題，而且可以應(yīng)用于實(shí)際生活中的很多領(lǐng)域，如市場營銷、銀行、電信以及網(wǎng)絡(luò)安全等。文中介紹了利用QT5.5開發(fā)的頻繁模式挖掘系統(tǒng)。該系統(tǒng)根據(jù)內(nèi)部嵌入的算法具有三大功能：最大頻繁項(xiàng)集挖掘、頻繁閉項(xiàng)集挖掘和頻繁模式匹配。用戶可以通過可視化界面來選擇所要實(shí)現(xiàn)的相應(yīng)功能。系統(tǒng)設(shè)計(jì)的目的是方便用戶以可視化方式比較“不確定序列模式匹配”、“不確定數(shù)據(jù)流最大頻繁項(xiàng)集挖掘”和“數(shù)據(jù)流頻繁閉模式挖掘”三個(gè)模塊中所包含的不同算法在時(shí)間和空間上的優(yōu)越性。

系統(tǒng)為一集成工具，為保證算法運(yùn)行的正確性以及系統(tǒng)的健壯性，系統(tǒng)為半封裝系統(tǒng)。用戶可以按照系統(tǒng)規(guī)定的數(shù)據(jù)格式導(dǎo)入需要進(jìn)行處理的數(shù)據(jù)源，修改算法中相應(yīng)的參數(shù)，選擇某個(gè)功能中的某一種算法或者某幾種算法來執(zhí)行，然后通過圖表的方式比較算法的優(yōu)劣。

1 相關(guān)理論和工具介紹

1.1開發(fā)工具

(1)軟件。

系統(tǒng)使用QT開發(fā)而成，版本為QT Creator3.4.2 base on QT 5.5.0。QT是1991年由奇趣科技開發(fā)的一個(gè)跨平臺(tái)C++圖形用戶界面應(yīng)用程序開發(fā)框架，是面向?qū)ο蟮目蚣埽褂锰厥獾拇a生成擴(kuò)展以及一些宏，易于擴(kuò)展，允許組件編程，而且QT具有優(yōu)良的跨平臺(tái)特性，在多個(gè)操作系統(tǒng)下均可運(yùn)行[5]。

(2)開發(fā)語言。

C++是在C語言的基礎(chǔ)上開發(fā)的一種面向?qū)ο缶幊陶Z言，應(yīng)用廣泛。C++支持多種編程范式—面向?qū)ο缶幊獭⒎盒途幊毯瓦^程化編程。其常用于系統(tǒng)開發(fā)、引擎開發(fā)等領(lǐng)域，是迄今為止最受廣大程序員歡迎的編程語言之一，支持類，具有封裝、繼承、多態(tài)等特性。

1.2 系統(tǒng)實(shí)現(xiàn)算法

系統(tǒng)主要實(shí)現(xiàn)數(shù)據(jù)流頻繁閉項(xiàng)集挖掘、不確定數(shù)據(jù)流的最大頻繁項(xiàng)集挖掘和不確定數(shù)據(jù)的頻繁模式匹配。

數(shù)據(jù)流頻繁閉項(xiàng)集挖掘算法[6-7]基于數(shù)據(jù)流滑動(dòng)窗口，利用一個(gè)在內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)—封閉枚舉樹(closed enumeration tree，CET)，來維護(hù)較小的動(dòng)態(tài)候選集。類似于前綴樹，樹中的每個(gè)節(jié)點(diǎn)ni代表一個(gè)項(xiàng)集I。CET只保存頻繁閉項(xiàng)集以及頻繁閉項(xiàng)集和其余項(xiàng)集之間的邊界項(xiàng)集。一個(gè)新的事務(wù)T添加到滑動(dòng)窗口時(shí)，需要遍歷CET中跟T有關(guān)的部分。對(duì)于每個(gè)相關(guān)節(jié)點(diǎn)nI，不僅要更新它的support和tid_sum，有可能還要更新它的節(jié)點(diǎn)類型。

不確定數(shù)據(jù)流最大頻繁項(xiàng)集挖掘算法[8-9]根據(jù)數(shù)據(jù)流的特點(diǎn)以及不確定數(shù)據(jù)的產(chǎn)生原因、表現(xiàn)形式和處理模型，從節(jié)約存儲(chǔ)空間和減少搜索空間兩大切入點(diǎn)入手，基于衰減窗口實(shí)現(xiàn)最大頻繁項(xiàng)集的挖掘。算法設(shè)計(jì)了存儲(chǔ)不確定數(shù)據(jù)流概要信息的數(shù)據(jù)結(jié)構(gòu)，并提出了高效的超集檢測方法，同時(shí)采用標(biāo)記樹節(jié)點(diǎn)的方法避免超集檢測，減少了搜索時(shí)間。

不確定數(shù)據(jù)模式匹配算法[10-12]則是采用動(dòng)態(tài)規(guī)劃策略解決不確定序列中的模式匹配問題。上述幾種算法由課題組成員實(shí)現(xiàn)，該系統(tǒng)開發(fā)的目的是把這些算法集成起來，以可視化的方式把結(jié)果展現(xiàn)出來，給用戶提供一個(gè)友好的頻繁模式挖掘工具。

2 系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

2.1 系統(tǒng)模型與框架設(shè)計(jì)

系統(tǒng)結(jié)構(gòu)圖如圖1所示，其結(jié)構(gòu)分為菜單欄、功能欄和狀態(tài)欄三個(gè)部分，系統(tǒng)功能主要體現(xiàn)在功能欄[13]。功能欄包含五個(gè)模塊：算法參數(shù)修改模塊(輸入)、功能選擇模塊、結(jié)果輸出模塊、圖表分析模塊和外部文件的讀寫。算法參數(shù)修改模塊主要是對(duì)算法運(yùn)行過程中需要的關(guān)鍵參數(shù)進(jìn)行修改；功能選擇模塊則是由用戶選擇要執(zhí)行的算法或結(jié)果輸出的形式；結(jié)果輸出模塊是將算法運(yùn)行結(jié)果保存在txt文件和xls文件中方便用戶查看；圖表分析模塊將算法運(yùn)行結(jié)果以可視化的形式展現(xiàn)給用戶；外部文件讀寫則是對(duì)txt文件的讀取。

圖1 系統(tǒng)結(jié)構(gòu)

系統(tǒng)具有以下特點(diǎn)：

(1)整個(gè)系統(tǒng)三大功能包含的各個(gè)算法雖然共用一個(gè)界面，但是算法間的運(yùn)行是相互獨(dú)立的。這些算法的輸入輸出以文本文件為主，用戶可以查看輸入輸出的內(nèi)容，并可在一定條件下對(duì)輸入文件進(jìn)行修改。

(2)該系統(tǒng)可以實(shí)現(xiàn)具有同一功能的不同算法之間的性能比較，所以每次運(yùn)行系統(tǒng)時(shí)的輸入數(shù)據(jù)應(yīng)為不同的數(shù)據(jù)。算法運(yùn)行結(jié)果只能保存到系統(tǒng)運(yùn)行結(jié)束時(shí)，系統(tǒng)運(yùn)行結(jié)束后，保存結(jié)果的文件會(huì)自動(dòng)刪除，該系統(tǒng)具備清除緩存文件的功能。

(3)系統(tǒng)界面友好，簡單明了。

2.2 系統(tǒng)功能算法嵌入

系統(tǒng)界面實(shí)現(xiàn)使用的語言以C++為框架，對(duì)其進(jìn)行函數(shù)及功能上的擴(kuò)充。使用的工具是QT5.0，QT兼容C++以及C的語法規(guī)則。該工具提供design模式和代碼編寫模式，該系統(tǒng)使用的是代碼編寫模式[14-15]。系統(tǒng)界面如圖2所示，主要?jiǎng)澐譃槿龎K：菜單欄、內(nèi)容區(qū)域和狀態(tài)欄。

圖2 系統(tǒng)界面

界面中功能選擇使用的是QTableWidget控件，每個(gè)功能頁都是一個(gè)單獨(dú)的QWidget，將每個(gè)功能頁布局完成后，最后再集成到QTableWidget中。前兩個(gè)QWidget為算法功能，算法運(yùn)行后為圖表的顯示提供數(shù)據(jù)。實(shí)現(xiàn)該界面的具體流程如圖3所示。

圖3 界面實(shí)現(xiàn)流程

點(diǎn)擊界面中的按鈕實(shí)現(xiàn)相應(yīng)算法的調(diào)用使用的是QT中的信號(hào)槽機(jī)制，點(diǎn)擊按鈕后發(fā)出相應(yīng)的信號(hào)，將該信號(hào)與要實(shí)現(xiàn)的函數(shù)槽鏈接起來，即可實(shí)現(xiàn)點(diǎn)擊按鈕調(diào)用算法的功能。

connect(Object，SIGNAL(signal1)，Object2，SLOT(slot))

其中，signal為對(duì)象Object的信號(hào)；slot為對(duì)象Object2的槽。

因?yàn)椴煌惴ㄖ邪邢嗤暮瘮?shù)名和變量名，為避免算法運(yùn)行出現(xiàn)混亂導(dǎo)致程序出錯(cuò)，每個(gè)算法都是一個(gè)單獨(dú)的程序，而用戶則是在主界面點(diǎn)擊功能按鈕來調(diào)用這些程序。算法運(yùn)行成功后，系統(tǒng)會(huì)彈出反饋窗口告知用戶。

2.3 數(shù)據(jù)的輸入輸出處理

算法的輸入及輸出數(shù)據(jù)以文本文件的方式存儲(chǔ)在文檔中，因?yàn)镼T內(nèi)嵌的字符編碼模式與通常的C++編程工具不同，在讀取數(shù)據(jù)時(shí)需要將數(shù)據(jù)進(jìn)行轉(zhuǎn)換。

為了使系統(tǒng)能夠正常運(yùn)行，對(duì)算法參數(shù)的輸入限制較為嚴(yán)格，用戶只能以選擇的方式對(duì)輸入的參數(shù)進(jìn)行更改，具體由QComboBox控件實(shí)現(xiàn)，代碼如下：

acombobox=new QComboBox;

acombobox->addItem(tr("item1"));

acombobox->addItem(tr("item2"));

acombobox->addItem(tr("item3"));

其中，item1，item2，item3即為用戶可以選擇的輸入?yún)?shù)。

2.4 圖表的實(shí)現(xiàn)

系統(tǒng)中的圖表主要包含三部分：表格、柱狀圖、折線圖。其中，表格由類form實(shí)現(xiàn)，算法在運(yùn)行過程中會(huì)自動(dòng)將運(yùn)行時(shí)間輸出到緩存文件中，當(dāng)用戶選擇要查看的算法后，系統(tǒng)會(huì)自動(dòng)讀取數(shù)據(jù)，將其以表格的形式顯示出來。

折線圖與柱狀圖則分別通過類line和histogramview實(shí)現(xiàn)，其界面為上表格下圖的形式展現(xiàn)，系統(tǒng)會(huì)自動(dòng)讀取默認(rèn)數(shù)據(jù)繪圖，用戶也可以手動(dòng)選擇要繪圖的數(shù)據(jù)。表格中的數(shù)據(jù)可以修改，但不會(huì)改變其原始值。當(dāng)表格中的數(shù)據(jù)發(fā)生更改時(shí)，繪制的圖形也會(huì)發(fā)生變化，其主要由datachange函數(shù)實(shí)現(xiàn)，代碼如下：

void dataChanged(const QModelIndex &topLeft,const QModelIndex &bottomRight)

{

QAbstractItemView::dataChanged(topLeft,bottomRight);

viewport()->update();

}

3 系統(tǒng)功能演示

3.1 功能及頁面

系統(tǒng)界面中多為功能按鈕，用戶選擇要實(shí)現(xiàn)的功能，點(diǎn)擊功能按鈕即可。以最大頻繁項(xiàng)集挖掘算法為例，其界面如圖4所示。

圖4 最大頻繁項(xiàng)集挖掘功能演示圖

圖中，修改參數(shù)選項(xiàng)為兩組參數(shù)，用戶點(diǎn)擊功能按鈕，在下拉菜單中選擇要修改的值，兩項(xiàng)選擇完畢后選擇要執(zhí)行的算法，待反饋窗口出現(xiàn)后，算法即運(yùn)行成功。如果想查看結(jié)果，選擇要查看的算法，點(diǎn)擊功能按鈕即可打開結(jié)果保存文件。

3.2 功能演示

(1)首先選擇輸入?yún)?shù)：

(3)算法運(yùn)行成功，選擇要查看的內(nèi)容：

(4)選擇繪制圖形功能。該功能為將各個(gè)算法運(yùn)行多次，取平均值進(jìn)行比較，用戶可以選擇繪制折線圖或柱狀圖(默認(rèn)顯示圖形為該算法運(yùn)行時(shí)間比較，用戶可以點(diǎn)擊“文件->打開”選擇memory02.txt文件，來顯示算法內(nèi)存占用比較)，如圖5所示。

圖5 算法運(yùn)行結(jié)果

(5)表格繪制功能。選擇相應(yīng)的算法，即可繪制表格(該功能為對(duì)每一個(gè)輸入數(shù)據(jù)的運(yùn)行狀況進(jìn)行比較)。該系統(tǒng)部分算法提供修改輸入數(shù)據(jù)，修改內(nèi)容格式必須與原內(nèi)容格式相同，否則算法將運(yùn)行出錯(cuò)。算法在選擇參數(shù)時(shí)，必須選擇確定的值，不可不選，否則算法無法正常運(yùn)行。表格輸出結(jié)果如圖6所示。

圖6 表格輸出結(jié)果

4 結(jié)束語

文中頻繁模式挖掘系統(tǒng)為一算法集成工具，為用戶提供一個(gè)可視化界面，點(diǎn)擊按鈕即可實(shí)現(xiàn)相應(yīng)的功能。系統(tǒng)在提供算法功能的同時(shí)也提供了繪制圖表的功能，圖表功能主要是為了實(shí)現(xiàn)算法性能的可視化比較，通過多次運(yùn)行同一算法取平均值，用戶可以選擇使用折線圖與柱狀圖顯示。為了使系統(tǒng)能夠良好運(yùn)行，對(duì)算法的輸入做了嚴(yán)格的限制，只允許用戶修改部分參數(shù)。因?yàn)橄到y(tǒng)的主要功能為實(shí)現(xiàn)算法性能的可視化比較，所以在運(yùn)行各個(gè)窗口下的算法時(shí)，必須全部運(yùn)行，以防止繪圖數(shù)據(jù)的錯(cuò)亂。

系統(tǒng)運(yùn)行的算法的輸入格式是固定的，當(dāng)用戶更改輸入格式時(shí)會(huì)使系統(tǒng)無法運(yùn)行。要使系統(tǒng)可以運(yùn)行更加復(fù)雜的算法，需要對(duì)集成方法進(jìn)行改進(jìn)，使系統(tǒng)的運(yùn)行與算法的執(zhí)行分離。這將是下一步的改進(jìn)方向。

[1] 白川平.多數(shù)據(jù)流的頻繁模式挖掘算法研究[J].寧夏師范學(xué)院學(xué)報(bào),2014,35(3):86-89.

[2] AGRAWAL R,SRIKANT R.Fast algorithms for mining association rules[C]//Proceedings of the 20th international conference on very large databases.San Francisco,CA,USA:Morgan Kaufmann Publishers Inc.,1994:487-499.

[3] 戰(zhàn)立強(qiáng).頻繁模式挖掘算法研究[D].哈爾濱:哈爾濱工程大學(xué),2007.

[4] 馬海兵.頻繁模式挖掘相關(guān)技術(shù)研究[D].上海:復(fù)旦大學(xué),2005.

[5] 陸文周.QT5開發(fā)及實(shí)例[M].北京：電子工業(yè)出版社，2015.

[6] CHI Y,WANG H,YU P S,et al.Moment:maintaining closed frequent itemsets over a stream sliding window[C]//Proceedings of fourth IEEE international conference on data mining.[s.l.]:IEEE,2004:59-66.

[7] 徐玉生.頻繁模式挖掘算法與剪枝策略研究[D].蘭州:蘭州大學(xué)，2008.

[8] 湯克明.不確定數(shù)據(jù)流中頻繁數(shù)據(jù)挖掘研究[D].南京:南京航空航天大學(xué)，2012.

[9] 劉慧婷,候明利,趙 鵬,等.不確定數(shù)據(jù)流最大頻繁項(xiàng)集挖掘算法研究[J].計(jì)算機(jī)工程與應(yīng)用,2016,52(19):72-77.

[10] LI Yuxuan,BAILEY J,KULIK L,et al.Efficient matching of substrings in uncertain sequences[C]//Proceedings of the 14th SIAM international conference on data mining.Philadelphia,Pennsylvania,USA:[s.n.],2014:767-775.

[11] ZHAO Zhou,YAN Da,NG W.Mining probabilistically frequent sequential patterns in large uncertain databases[J].IEEE Transactions on Knowledge and Data Engineering,2014,26(5):1171-1184.

[12] GE Tingjian,LI Zheng.Approximate substring matching over uncertain strings[J].Proceedings of the VLDB Endowment,2011,4(11):772-782.

[13] 陳暢偉.基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘可視化系統(tǒng)的實(shí)現(xiàn)[D].武漢:武漢理工大學(xué),2004.

[14] 戴 巍,霍 亞,馬尚昌,等.Qt下基于組件的嵌入式軟件框架設(shè)計(jì)及實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用，2016，36:257-261.

[15] 賀 青,李鵬飛.基于Qt的電腦橫機(jī)上位機(jī)的設(shè)計(jì)[J].微型機(jī)與應(yīng)用，2012，31(19):14-17.