王琳燕

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

1 問題的提出

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

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

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

2 粗糙集中基于差別矩陣的屬性約簡方法

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

定義1 考慮一個信息系統(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。每一個屬性子集P∈Q決定了一個二元不可區(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的一個劃分，用U/IND(P)表示。

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

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

定義4 所有屬性約簡的交集成為核。

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

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

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

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

3 教學(xué)評價系統(tǒng)的特征選取過程

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

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

圖1 設(shè)計方案

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

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

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

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

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

本文采用的屬性約簡算法的流程如圖2所示。

圖2 屬性約簡算法流程圖

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

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

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

表4 簡化后的差別矩陣

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

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

4)從隊列中取出一個屬性a加入R。

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

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

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

3.4 實驗結(jié)果和分析

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

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

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

4 結(jié)論

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

［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ā)式屬性約簡算法［J］.計算機工程與科學(xué)，2008，30 (6):73－75.

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

［5］ 楊傳健，葛浩，汪志圣.基于粗糙集的屬性約簡方法研究綜述［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］ 葉東毅，陳昭炯.一個新的差別矩陣及其求核方法［J］.電子學(xué)報，2002，30(7):1086－1088.

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