王琳燕

(福州職業(yè)技術(shù)學(xué)院計(jì)算機(jī)系，福建福州350003)

1 問(wèn)題的提出

每個(gè)學(xué)期末，各校通常都要組織學(xué)生對(duì)每位任課教師的教學(xué)效果做出評(píng)價(jià)。我校使用的教學(xué)評(píng)價(jià)系統(tǒng)的樣例數(shù)據(jù)如表1所示。該評(píng)價(jià)結(jié)果既能作為教師考核的依據(jù)，也能作為教師進(jìn)行教學(xué)改革的重要參考。

作為一名教師，如果明確表中哪些關(guān)鍵因素決定教學(xué)評(píng)價(jià)結(jié)果，進(jìn)行教學(xué)改革就會(huì)有的放矢，達(dá)到更好的教學(xué)效果。表1中評(píng)價(jià)項(xiàng)目較多，如何從中找出決定教學(xué)評(píng)價(jià)效果的關(guān)鍵因素呢?本文利用粗糙集理論中的屬性約簡(jiǎn)技術(shù)較為簡(jiǎn)單地解決了這個(gè)特征選取問(wèn)題。

表1 教學(xué)評(píng)價(jià)系統(tǒng)的樣例數(shù)據(jù)

2 粗糙集中基于差別矩陣的屬性約簡(jiǎn)方法

粗糙集理論于1982年由Pawlak Z提出［1］，它是一種處理模糊和不確定性知識(shí)的數(shù)學(xué)工具［2］。屬性約簡(jiǎn)是粗糙集理論中的一個(gè)重要研究課題。所謂屬性約簡(jiǎn)，就是在保持知識(shí)庫(kù)分類或決策能力不變的條件下刪除其中不相關(guān)或不重要的知識(shí)，求得知識(shí)的最小表達(dá)和知識(shí)的各種不同顆粒層次［3］。為了后續(xù)敘述方便，下面給出幾個(gè)相關(guān)概念。

定義1 考慮一個(gè)信息系統(tǒng)L=(U，Q，Vq，F(xiàn)q)，q∈Q，其中U={x1，x2，…，xn}是論域，Q是屬性集合，Vq為屬性取值，F(xiàn)q是U×Q→Vq的映射。屬性集合 Q通常分為條件屬性C={C1，C2，…，Cr}和決策屬性集D。每一個(gè)屬性子集P∈Q決定了一個(gè)二元不可區(qū)分關(guān)系IND(P):IND(P)={(x，y)∈U×U |a∈P，F(xiàn)q(x，a)=Fq(y，a)}。關(guān)系IND(P)構(gòu)成了U的一個(gè)劃分，用U/IND(P)表示。

定義2 令R為一族等價(jià)關(guān)系，P∈R，如果IND(R)=IND(R－{P})，則稱P為R中不必要的，否則稱P為R中必要的。如果每一個(gè)P∈R都為R中必要的，則稱R為獨(dú)立的。

定義3 設(shè)U是一個(gè)論域，R、P為定義在 U上的2個(gè)等價(jià)關(guān)系簇，且R?P，如果滿足:①IND(P)=IND(R);②R是獨(dú)立的，稱R是P的一個(gè)約簡(jiǎn)。

定義4 所有屬性約簡(jiǎn)的交集成為核。

Hu等人根據(jù) Skowron差別矩陣［4］提出一種基于屬性重要性的啟發(fā)式屬性約簡(jiǎn)算法［5］。其基本思想是將信息系統(tǒng)中所有相關(guān)屬性的區(qū)分信息都濃縮進(jìn)一個(gè)矩陣中，通過(guò)差別矩陣可以方便地得到信息系統(tǒng)中的屬性核。Hu在文獻(xiàn)［6］中提出利用改進(jìn)的差別矩陣求核，其中改進(jìn)的差別矩陣的定義如式(1):

Hu認(rèn)為當(dāng)且僅當(dāng) 某個(gè) mij為單個(gè)屬性時(shí)，該屬性屬于核。有學(xué)者在文獻(xiàn)［7］中指出了Hu中差別矩陣的求核缺陷，提出新的差別矩陣定義并加以證明。具體差別矩陣的定義M={m'ij}如式(2):

其中d(xi)表示 U中所有與 xi在關(guān)系IND(C)下是等價(jià)的元素相應(yīng)的決策屬性值構(gòu)成的集合的基數(shù)。

差別矩陣在求屬性約簡(jiǎn)過(guò)程中最大缺點(diǎn)為對(duì)空間要求過(guò)大，文獻(xiàn)［8］中提出的部分差別矩陣可以減少差別矩陣存儲(chǔ)上的空間復(fù)雜度，但在處理屬性重要度方面有一定的缺陷，本文采用的屬性約簡(jiǎn)算法在文獻(xiàn)［8］的基礎(chǔ)上做了一點(diǎn)改進(jìn)。

3 教學(xué)評(píng)價(jià)系統(tǒng)的特征選取過(guò)程

3.1 特征選取設(shè)計(jì)總體方案

本文采用的特征選取方案如圖1所示。該方案的流程是:首先將教學(xué)評(píng)價(jià)系統(tǒng)中與評(píng)價(jià)結(jié)果有關(guān)的數(shù)據(jù)用二維表的方式提取出來(lái)，去除重復(fù)數(shù)據(jù)后對(duì)數(shù)據(jù)表進(jìn)行離散化處理，然后運(yùn)用一種屬性約簡(jiǎn)算法進(jìn)行特征選取，最后得到一個(gè)屬性約簡(jiǎn)子集，也就是教學(xué)評(píng)價(jià)系統(tǒng)中決定教學(xué)評(píng)價(jià)效果的關(guān)鍵因素。

圖1 設(shè)計(jì)方案

3.2 去除重復(fù)數(shù)據(jù)和離散化處理

為了方便數(shù)據(jù)的處理，用C1，C2，C3，……分別表示教學(xué)內(nèi)容、語(yǔ)言表達(dá)、教學(xué)課件等評(píng)價(jià)項(xiàng)目，用D表示評(píng)價(jià)結(jié)果。對(duì)表1中的數(shù)據(jù)進(jìn)行數(shù)值化處理。各項(xiàng)評(píng)價(jià)指標(biāo)中分別用1、2、3表示好、中、差。評(píng)價(jià)結(jié)果中用1、2、3分別表示滿意、基本滿意、不滿意，并將表1中的第5條重復(fù)數(shù)據(jù)去除，經(jīng)過(guò)以上處理，表1中的數(shù)據(jù)就被整理成表2的數(shù)據(jù)。

表2 處理后的樣例數(shù)據(jù)

需要說(shuō)明的是如果有的學(xué)校教學(xué)評(píng)價(jià)項(xiàng)目采用打分的方式，則在這一步要做離散化處理。比如90-100分用1表示，80-90分用2表示等，同樣也可以處理成類似于表2的數(shù)據(jù)。

3.3 改進(jìn)的基于差別矩陣的屬性約簡(jiǎn)算法的實(shí)現(xiàn)

本文采用的屬性約簡(jiǎn)算法的流程如圖2所示。

圖2 屬性約簡(jiǎn)算法流程圖

1)差別矩陣的定義及求核。本文采用文獻(xiàn)［7］的差別矩陣求核。根據(jù)式(1)和(2)的定義，表2數(shù)據(jù)對(duì)應(yīng)的差別矩陣如表3所示。在表3中根據(jù)公式(1)求得核為C1。

表3 教學(xué)評(píng)價(jià)數(shù)據(jù)的差別矩陣

2)簡(jiǎn)化差別矩陣。設(shè)屬性約簡(jiǎn)集合R= {核}，將差別矩陣中包含核C1的元素置為空集。這個(gè)步驟與文獻(xiàn)［8］中提出的部分差別矩陣的思路是一致的。簡(jiǎn)化后的差別矩陣如表4所示。

表4 簡(jiǎn)化后的差別矩陣

3)按照屬性的重要性依次將屬性添加到約簡(jiǎn)集R中，然后繼續(xù)簡(jiǎn)化差別矩陣直到差別矩陣全部元素都為空則算法停止。

用屬性在差別矩陣中出現(xiàn)的頻率f作為屬性重要性的衡量標(biāo)準(zhǔn)，找出f最高的那個(gè)屬性。文獻(xiàn)［8］中對(duì)f取值相同的屬性隨機(jī)選取一個(gè)，但這樣的選擇具有一定的盲目性。在差別矩陣中，如果某個(gè)矩陣元素包含的屬性個(gè)數(shù)越少，則這個(gè)矩陣元素一定更為精辟且更為重要。因此，將包含該屬性的所有矩陣元素的長(zhǎng)度的累加和s作為輔助屬性重要性的衡量標(biāo)準(zhǔn)，對(duì)于f相同的屬性，根據(jù)f/s得到商g。根據(jù)g值從大到小的順序?qū)⑦@些f相同的屬性放入一個(gè)隊(duì)列。

4)從隊(duì)列中取出一個(gè)屬性a加入R。

5)由于屬性a已經(jīng)加入屬性約簡(jiǎn)集，可以繼續(xù)簡(jiǎn)化差別矩陣，將矩陣中包含a的元素全部置為空。

6)若矩陣全部元素都為空，則算法停止。

7)查看隊(duì)列中是否還有元素，如果有則轉(zhuǎn)入步驟4，否則進(jìn)入步驟3。

3.4 實(shí)驗(yàn)結(jié)果和分析

為了驗(yàn)證算法，將計(jì)算機(jī)系2012年教學(xué)評(píng)價(jià)數(shù)據(jù)作為測(cè)試數(shù)據(jù)，運(yùn)用以上算法最后求得屬性約簡(jiǎn)為 C1，C3。也就是說(shuō)通過(guò)屬性約簡(jiǎn)算法，可以在眾多的評(píng)價(jià)因子中找出教學(xué)內(nèi)容和教學(xué)課件是決定教學(xué)效果的重要因素，減少了今后做進(jìn)一步數(shù)據(jù)挖掘的數(shù)據(jù)運(yùn)算量。該算法的時(shí)間復(fù)雜度為:O(|C|2|U|2)。

3.5 對(duì)空間復(fù)雜度的改進(jìn)

差別矩陣對(duì)空間要求很大，本文采用的算法在步驟2上對(duì)差別矩陣進(jìn)行簡(jiǎn)化，另外由于差別矩陣是對(duì)稱矩陣，在存儲(chǔ)時(shí)只需存儲(chǔ)上半矩陣，這樣能使空間復(fù)雜度減少一半。

4 結(jié)論

本文利用差別矩陣的特性，采用改進(jìn)的屬性約簡(jiǎn)算法，得到教學(xué)評(píng)價(jià)系統(tǒng)中決定教學(xué)效果的關(guān)鍵因素，并解決了空間復(fù)雜度的問(wèn)題。本文中提到的算法也可以比較簡(jiǎn)單地解決其他類似的屬性約簡(jiǎn)的實(shí)際問(wèn)題。

［1］ Pawlak Z.Rough sets［J］.International Journal of Information and Computer Sciences，1982，11(5): 341－356.

［2］ 張文修，吳偉志，梁吉業(yè)，等.粗糙集理論與方法［M］.北京:科學(xué)出版社，2001:11.

［3］ 王柯，朱啟兵.一種基于差別矩陣的啟發(fā)式屬性約簡(jiǎn)算法［J］.計(jì)算機(jī)工程與科學(xué)，2008，30 (6):73－75.

［4］ 蒙韌，徐章艷，楊炳儒.一個(gè)計(jì)算Skowron差別矩陣核的新算法［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47(1):159－161.

［5］ 楊傳健，葛浩，汪志圣.基于粗糙集的屬性約簡(jiǎn)方法研究綜述［J］.計(jì)算機(jī)應(yīng)用研究，2012，29 (1):16－20.

［6］ Hu Xiaohua，N Cercone.Learning in relational databases:a rough set approach［J］.Computational Intelligence，1995，11(2):323－337.

［7］ 葉東毅，陳昭炯.一個(gè)新的差別矩陣及其求核方法［J］.電子學(xué)報(bào)，2002，30(7):1086－1088.

［8］ 徐一新，葉東毅.知識(shí)約簡(jiǎn)的差別矩陣啟發(fā)式算法［J］.福州大學(xué)學(xué)報(bào)(自然科學(xué)版)，2000，28 (3):121－123.