模式矩陣的FP-DMMFI并行算法在教師科研素養(yǎng)挖掘中的應(yīng)用

徐儒

長(zhǎng)江師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院 重慶 408000

0 引言

數(shù)據(jù)挖掘(DataMining)是為了解決“數(shù)據(jù)豐富，知識(shí)貧乏”狀況應(yīng)運(yùn)而生的，是從海量數(shù)據(jù)中獲取知識(shí)的可靠技術(shù)。將數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則分析方法應(yīng)用于教師科研素養(yǎng)分析，能發(fā)現(xiàn)影響教師素養(yǎng)各因子之間的相關(guān)性。通過(guò)收集、加工和處理教師的科研信息統(tǒng)計(jì)表，分析特定群體或個(gè)體的知識(shí)結(jié)構(gòu)、年齡階段、興趣愛(ài)好等，從而確定出教師群體或個(gè)體的科研習(xí)慣、科研特征，科研傾向和興趣偏好，進(jìn)而對(duì)相應(yīng)群體或個(gè)體的未來(lái)發(fā)展趨勢(shì)做出判斷，找出影響科研素養(yǎng)各因子之間隱藏的內(nèi)在關(guān)聯(lián)。

1 模式矩陣的并行頻繁項(xiàng)集挖掘算法：FP-DMMFI

雖然FP-growth與Appriori算法相比，極大地提高了挖掘的效能，但在構(gòu)造一顆新的 FP-tree時(shí)需要掃描兩次數(shù)據(jù)庫(kù)；當(dāng)事務(wù)數(shù)據(jù)庫(kù)中有新數(shù)據(jù)加入時(shí)，原來(lái)發(fā)現(xiàn)的頻繁項(xiàng)集可能不再是頻繁的，這時(shí)，每重新建立一次FP-tree都要同時(shí)把新舊數(shù)據(jù)掃描兩次；同時(shí)，當(dāng)支持度閾值發(fā)生變化時(shí)，需要重新建立FP-tree，這種情況數(shù)據(jù)的規(guī)模越大，開(kāi)銷就越大。針對(duì)以上存在的不足，本文提出了一種基于模式矩陣的并行頻繁項(xiàng)集挖掘算法 - FP-DMMFI(frequent pattern array for distribution mining maximal frequent itemsets)算法。

1.1 FP-DMMFI算法

FP-DMMFI算法主要將挖掘數(shù)據(jù)映射成矩陣后通過(guò)并行處理的方式來(lái)完成頻繁項(xiàng)集的挖掘工作。基本思路是：采取分治策略，首先將提供頻繁項(xiàng)的數(shù)據(jù)庫(kù)壓縮到矩陣T中，但仍然保留項(xiàng)集關(guān)聯(lián)信息，同時(shí)獲取頻繁項(xiàng)的支持度計(jì)數(shù)的向量ω，由矩陣T和ω生產(chǎn)模式矩陣P，然后并行完成頻繁項(xiàng)集的挖掘工作。

FP-DMMFI通過(guò)一次掃描數(shù)據(jù)庫(kù)將事務(wù)和項(xiàng)集關(guān)聯(lián)信息映射成矩陣，之后無(wú)需再做掃描數(shù)據(jù)庫(kù)的操作，直接通過(guò)矩陣運(yùn)算就可以挖掘出頻繁項(xiàng)集。并行FP-array模式矩陣算法的挖掘過(guò)程主要包含三個(gè)步驟，分別是構(gòu)造模式矩陣、FPMax最大頻繁模式挖掘和生成關(guān)聯(lián)規(guī)則。

1.2 構(gòu)造FP-array

定義1：向量ω表示數(shù)據(jù)庫(kù)D中各項(xiàng)的支持度計(jì)數(shù)。ω =[ω1,ω2,…ωn]。ωi表示第i個(gè)項(xiàng)在D中的支持度計(jì)數(shù)。

定義2：T[n][m]表示與D一一對(duì)應(yīng)的映射矩陣，T[i]表示與D相對(duì)應(yīng)的第i個(gè)事務(wù)，Tij表示第j個(gè)項(xiàng)在第i次事務(wù)中的出現(xiàn)與否，如出現(xiàn)則xij=1，否則xij=0(即xij∈{0,1}，i≤n，j≤m)。

掃描數(shù)據(jù)庫(kù)，獲取數(shù)據(jù)庫(kù)的事務(wù)數(shù)和項(xiàng)數(shù)。假設(shè)D中含有m個(gè)事務(wù)，所有事務(wù)共涉及n個(gè)項(xiàng)，則需要構(gòu)造一個(gè)n行 m列的矩陣T[n][m]。此時(shí)，稱ω的轉(zhuǎn)置向量ω-1和矩陣T組成的矩陣為模式矩陣P。

1.3 FP-Max挖掘

P壓縮寫(xiě)入了D中內(nèi)容，對(duì)于任何頻繁項(xiàng)目集X，其頻繁項(xiàng)目已經(jīng)映射到P矩陣?yán)铩Ｒ虼?，可以將求解頻繁項(xiàng)集的問(wèn)題，轉(zhuǎn)換為遞歸發(fā)現(xiàn)矩陣最長(zhǎng)頻繁模式的問(wèn)題。

通過(guò)模式矩陣 P，獲得支持頻度大于最小支持頻度的模式矩陣P1，P1表示為1-項(xiàng)模式矩陣。對(duì)P1中行元素進(jìn)行笛卡爾關(guān)系與操作，生成2-項(xiàng)模式矩陣P2，剪枝掉P2中支持頻度小于最小支持頻度的所在行，確定出模式矩陣P2。依次循環(huán)，由項(xiàng)模式Pn依次推出并產(chǎn)生矩陣Pn+1，直到Pn+1=Ф時(shí)停止，挖掘最大頻繁項(xiàng)集模式矩陣的操作結(jié)束，則Pn即為最大頻繁模式矩陣。挖掘過(guò)程為：

(1) 連接：將模式矩陣 Pn-1中的行與其余各行進(jìn)行笛卡爾與操作，得到n-項(xiàng)矩陣T；

(2) 生成模式矩陣：計(jì)算n-項(xiàng)矩陣T對(duì)應(yīng)的ω向量，將ω-1和n-項(xiàng)矩陣T組成模式矩陣Pn；

(3) 剪枝：刪除模式矩陣Pn中支持度小于最小支持頻度的所在行。

設(shè)計(jì)代碼為：

算法：并行模式矩陣挖掘 D中最大頻繁項(xiàng)目集算法(FP-DMMFI)

輸入：事務(wù)數(shù)據(jù)庫(kù)D的映射矩陣T，最小支持度閾值s

輸出：事務(wù)數(shù)據(jù)庫(kù)D的最大頻繁項(xiàng)目集MFSD

方法：

(1) 將數(shù)據(jù)庫(kù)D壓縮到矩陣T中；

(2) MFSD=Φ；//初始化最大頻繁項(xiàng)目集合；

(3) 獲取T中各對(duì)應(yīng)列的項(xiàng)的支持度計(jì)數(shù)ω，生產(chǎn)模式矩陣P；

(4) If ( P[i]中的ωi＜ s)then //剪枝小于最小支持度的項(xiàng)；

(5) Delete P[i];//刪除該行記錄；

(6) 更新P；

(7) If (P≠Φ) then；

(8) MFSD= P；

(9) P各項(xiàng)集進(jìn)行笛卡爾與運(yùn)算//挖掘最大頻繁項(xiàng)集；

(10) 跳轉(zhuǎn)到第(2)步；

(11) End；

(12) 輸出MFSD。

2 挖掘教師科研素養(yǎng)中的關(guān)聯(lián)

2.1 數(shù)據(jù)整理

我們以某高校統(tǒng)計(jì)的教師科研信息作為實(shí)例分析。數(shù)據(jù)來(lái)源于某年度所有教師的科研統(tǒng)計(jì)，有效時(shí)間段為：從1月1日起至12月30日止，共有3000余條數(shù)據(jù)記錄，分別記錄了每位教師在規(guī)定時(shí)間內(nèi)，全部論文、著作、課題和獲獎(jiǎng)四個(gè)方面的科研情況和其它相關(guān)信息。如表1所示是事務(wù)數(shù)據(jù)表中的部分字段和記錄。

由于本次是對(duì)教學(xué)科研人員的科研素養(yǎng)進(jìn)行研究，因此，最能夠體現(xiàn)科研的能力特征主要應(yīng)表現(xiàn)在論文、著作、課題和獲獎(jiǎng)這四個(gè)方面。提取最主要反映科研的能力特征的四個(gè)特征屬性值，分別對(duì)各特征屬性值進(jìn)行歸約化操作。其中將“論文”歸約為三大檢索期刊(SCI、EI、ISTP)、中文核心和普通期刊三類，且僅以排名第一作者為有效；“著作”歸約為專著和教材兩類，作者排名以主編、副主編和前三位參編有效；“課題”歸約為國(guó)家級(jí)、省市級(jí)和區(qū)縣級(jí)三類，國(guó)家級(jí)課題作者排名前五位為有效，省市級(jí)課題作者排名前三位為有效，區(qū)縣級(jí)作者排名第一為有效；”獲獎(jiǎng)” 歸約為國(guó)家級(jí)、省市級(jí)和區(qū)縣級(jí)三類，作者的有效排名與“課題”規(guī)定相一致。省略其它信息，對(duì)事務(wù)數(shù)據(jù)進(jìn)行特征提取、歸約整理。

表1 事務(wù)數(shù)據(jù)表中的部分字段和記錄

顯然，表1中的原始數(shù)據(jù)不能夠直接進(jìn)行數(shù)據(jù)挖掘。為了能夠真實(shí)地反映某一群體或個(gè)體的科研素養(yǎng)情況，便于準(zhǔn)確的進(jìn)行知識(shí)特征提取和挖掘數(shù)據(jù)關(guān)聯(lián)，我們以主要影響科研素養(yǎng)的職稱、年齡和學(xué)歷三個(gè)方面(表 2所示)，作為挖掘科研素養(yǎng)數(shù)據(jù)的判定因子，對(duì)原始數(shù)據(jù)庫(kù)中的論文、著作、課題和獲獎(jiǎng)的字段信息，進(jìn)行離散化操作，并按照論文、著作、課題和獲獎(jiǎng)的順序，依次用I12,I13,…,I22分別表示。離散后的判定因子和事務(wù)數(shù)據(jù)，如表3所示。

表2 影響因子的映射

表3 離散后的數(shù)據(jù)

2.2 構(gòu)造模式矩陣

將數(shù)據(jù)進(jìn)行歸約和離散化操作后，就可以構(gòu)造模式矩陣了。由于影響科研素養(yǎng)的判定因子不止一個(gè)，可以對(duì)各影響因子構(gòu)造不同的FP-array矩陣，進(jìn)行分別判斷，也可以將各影響因子統(tǒng)一構(gòu)造FP-array矩陣綜合判斷，所以，我們采用統(tǒng)一構(gòu)造FP-array矩陣的方式，并行完成頻繁項(xiàng)集的挖掘工作。假設(shè)最小支持度閾值為 2，剪枝掉數(shù)據(jù)庫(kù)中小于最小支持度閾值的事務(wù)記錄，將提供頻繁項(xiàng)的數(shù)據(jù)庫(kù)壓縮到矩陣T中，構(gòu)造一個(gè)m行n列的FP-array矩陣M1，并保留項(xiàng)集關(guān)聯(lián)信息。這里，我們采用了0-1矩陣的存儲(chǔ)形式，即矩陣值為0時(shí)表示與之對(duì)應(yīng)的元素為假，矩陣值為1時(shí)表示與之對(duì)應(yīng)的元素為真。矩陣中的每列代表的是剪枝后存儲(chǔ)的一條或者多條記錄。從而，構(gòu)造與數(shù)據(jù)庫(kù)保持一致的FP-array模式矩陣P (如圖1所示)。

圖1 FP-array模式矩陣

2.3 挖掘最大頻繁項(xiàng)集

通過(guò)并行求解模式矩陣 P，挖掘最大頻繁項(xiàng)集。挖掘結(jié)果為：

2.4 關(guān)聯(lián)規(guī)則生成

根據(jù)最大頻繁模式的挖掘結(jié)果，得到兩條4-項(xiàng)頻繁項(xiàng)集。從數(shù)據(jù)庫(kù)D中挖掘出所有的頻繁項(xiàng)集，就可以很容易地獲得相應(yīng)的關(guān)聯(lián)規(guī)則。通過(guò)項(xiàng)集支持頻度計(jì)算公式獲得關(guān)聯(lián)規(guī)則的信任度。則由最大頻繁項(xiàng)集產(chǎn)生的部分關(guān)聯(lián)規(guī)則如表4所示。

表4 關(guān)聯(lián)規(guī)則

如果設(shè)最小置信度閾值為60%，則規(guī)則(1)～(7)被保留，規(guī)則(8)被刪除；如果設(shè)最小置信度閾值為70%，那么僅有規(guī)則(1)、(2)和(6)，由于信任度大于最小置信度閾值而被保留下來(lái)。

同理，由3-頻繁項(xiàng)集產(chǎn)生的部分強(qiáng)關(guān)聯(lián)規(guī)則有：

(9) Conf(＜職稱:高級(jí),年齡:40-50 歲＞ =＞ ＜論文:SCI/EI/ISTP＞) = 100%

(10) Conf(＜職稱:高級(jí),年齡:40-50歲＞ =＞ ＜課題:省級(jí)＞) = 100%

(11) Conf(＜職稱:中級(jí),學(xué)歷:碩士＞=＞ ＜論文:中文核心＞) = 100%

(12) Conf(＜職稱:中級(jí),學(xué)歷:碩士＞=＞ ＜課題:省級(jí)＞) = 100%

2.5 結(jié)果分析

從關(guān)聯(lián)規(guī)則的支持度和信任度中可以看出：年齡在 40到 50歲之間、職稱結(jié)構(gòu)為高級(jí)的教師群體，偏好于在SCI/EI/ISTP刊源的高質(zhì)量學(xué)術(shù)期刊上發(fā)表專業(yè)文章，同時(shí)申請(qǐng)獲得省部級(jí)以上的科研項(xiàng)目的機(jī)率較大。高級(jí)別職稱的教師群體通常作為高校各學(xué)科領(lǐng)域的帶頭人，在教學(xué)和科研方面起著領(lǐng)頭羊的作用。經(jīng)過(guò)關(guān)聯(lián)規(guī)則的信任度和支持度可得，高級(jí)別職稱的科研素養(yǎng)還是比較高。最高學(xué)歷為碩士研究生、職稱結(jié)構(gòu)為中級(jí)的教師群體，普遍選擇將文章發(fā)表在中文核心期刊要目總覽的期刊上，同時(shí)也是申請(qǐng)省部級(jí)以上科研項(xiàng)目并獲得審批的主要群體之一。中級(jí)別職稱的教師群體作為學(xué)校的中堅(jiān)力量和第二人才梯隊(duì)，有66.667%的老師具有碩士學(xué)位、發(fā)表過(guò)中文核心期刊論文和主持過(guò)省部級(jí)課題，由此可以看出，中級(jí)職稱的科研素養(yǎng)情況處于中等偏上水平的。值得一提的是，通過(guò)對(duì)教師科研素養(yǎng)的數(shù)據(jù)挖掘，初級(jí)職稱和副高級(jí)職稱這兩個(gè)職稱系列，由于沒(méi)有特別明顯的科研成果，表現(xiàn)出科研素養(yǎng)不高的情況。值得我們思考和反省。

3 小結(jié)

通過(guò)對(duì)高校教師科研現(xiàn)狀的分析，歸約出了主要影響科研素養(yǎng)的判定因子，并用模式矩陣算法，挖掘其隱藏信息和內(nèi)在關(guān)聯(lián)。挖掘過(guò)程中，在分析Apriori和FP-tree算法的基礎(chǔ)上，提出了并行挖掘最大頻繁項(xiàng)集的FP-DMMFI算法。算法整個(gè)過(guò)程只需完整的掃描一次數(shù)據(jù)庫(kù)，將所有信息壓縮映射到矩陣中，對(duì)矩陣進(jìn)行并行處理，就能夠完成頻繁項(xiàng)集的挖掘工作。FP-DMMFI算法應(yīng)用于教師科學(xué)素養(yǎng)的數(shù)據(jù)挖掘中，挖掘結(jié)果能夠很好的為決策者提供決策參考。

[1]宋余慶,朱玉全.基于FP—tree的最大頻繁項(xiàng)目集挖掘及更新算法[J].軟件學(xué)報(bào).2003.

[2]秦亮曦,蘇永秀,劉永彬等.基于壓縮 FP-樹(shù)和數(shù)組技術(shù)的頻繁模式挖掘算法[J].計(jì)算機(jī)研究與發(fā)展.2008.

[3]劉鵬,孫莉,趙潔等.數(shù)據(jù)挖掘技術(shù)在高校人力資源管理中的應(yīng)用研究[J].計(jì)算機(jī)工程與應(yīng)用.2008.

[4]Han J Kamber.范明,孟小峰.數(shù)據(jù)挖掘:概念與技術(shù)[M].北京:機(jī)械工業(yè)出版社.2001.

[5]鄧豐義,劉震宇.基于模式矩陣的FP-growth改進(jìn)算法[J].廈門(mén)大學(xué)學(xué)報(bào).2005.

[6]朱明.數(shù)據(jù)挖掘[M].中國(guó)科學(xué)技術(shù)大學(xué)出版社.2002.