粗糙集的規(guī)則獲取方法在遠(yuǎn)程教育算法中的實現(xiàn)研究

楊慧 丁正生

【摘 要】

粗糙集理論被廣泛應(yīng)用于不確定環(huán)境下不確定或不相容數(shù)據(jù)的信息處理和規(guī)則獲取。本文研究了基于粗糙集的規(guī)則獲取方法，結(jié)合線性搜索和排序方法，實現(xiàn)了遠(yuǎn)程教育算法DLA（Distance Learning Algorithm），對現(xiàn)代遠(yuǎn)程教學(xué)實踐有普遍的指導(dǎo)意義。

【關(guān)鍵詞】 粗糙集；規(guī)則獲取；屬性約簡；遠(yuǎn)程教育算法；識別指數(shù)

【中圖分類號】 G40-057 【文獻(xiàn)標(biāo)識碼】 A 【文章編號】 1009—458x（2015）08—0053—05

一、簡介

計算機(jī)和網(wǎng)絡(luò)技術(shù)的普及，為教育事業(yè)提供了更加優(yōu)越的硬件和軟件，計算機(jī)和網(wǎng)絡(luò)技術(shù)正逐步應(yīng)用和滲透到以教師講授為基礎(chǔ)的傳統(tǒng)課堂上，并潛移默化地改變著互動性低的傳統(tǒng)教學(xué)模式，逐步形成了依附于互聯(lián)網(wǎng)技術(shù)的開放式、互動式教學(xué)模式，即遠(yuǎn)程教育模式?，F(xiàn)代遠(yuǎn)程教育的開展和普及，是實現(xiàn)終身學(xué)習(xí)的重要途徑。

粗糙集（Rough Sets）理論是1982年最先由波蘭數(shù)學(xué)家Z. Pawlak提出的一種分析數(shù)據(jù)的數(shù)學(xué)理論和方法，被廣泛應(yīng)用于處理不確定、不精確性問題和不相容數(shù)據(jù)。粗糙集理論將知識看作是關(guān)于論域的劃分， 并根據(jù)近世代數(shù)學(xué)中的等價關(guān)系來分析和研究知識，模糊性和不確定性的概念也是在知識分類的基礎(chǔ)上定義的。自粗糙集理論被提出后，其逐步滲透到人工智能、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)和模式識別等研究領(lǐng)域 [1][2][3]。

遠(yuǎn)程教育已成為改革傳統(tǒng)教育模式的動力和有效手段，也是教育改革的研究重點(diǎn)[4]。針對目前遠(yuǎn)程教育中個性化教學(xué)水平較低的問題，有學(xué)者提出了一種基于粗糙集的Web學(xué)習(xí)者聚類算法，并應(yīng)用粗糙集的約簡方法解決了學(xué)習(xí)者特征數(shù)據(jù)中的屬性冗余問題，但對由不相關(guān)屬性（冗余屬性）引起的誤導(dǎo)現(xiàn)象十分敏感[5]。聚類算法為遠(yuǎn)程教育中學(xué)生的個性特征及學(xué)習(xí)狀態(tài)評估提供了一種有效的評價手段，可以根據(jù)聚類分析結(jié)果給出針對性的輔導(dǎo)與學(xué)習(xí)策略。傳統(tǒng)的K均值聚類算法在初始聚類中心選取上具有隨機(jī)性，且聚類具有不確定性和時間復(fù)雜度較高的缺點(diǎn)[6]。利用網(wǎng)格聚類的思想對K均值聚類算法進(jìn)行改進(jìn)，可以克服K值隨機(jī)性帶來的不確定性以及傳統(tǒng)網(wǎng)格聚類方法造成的簇丟失缺陷。

遠(yuǎn)程教育的推廣過程和研究過程，依然面臨著很多挑戰(zhàn)。一方面，遠(yuǎn)程學(xué)習(xí)者海量的在線測驗數(shù)據(jù)需要處理；另一方面，現(xiàn)有的課程教授模式使在線學(xué)生和教育者之間缺少聯(lián)系和信息回饋的問題越來越凸顯。針對這兩個問題，很自然地可以聯(lián)想到粗糙集理論中很重要的研究領(lǐng)域——數(shù)據(jù)約簡和規(guī)則獲取。在包含海量數(shù)據(jù)的信息系統(tǒng)中，很多屬性信息對于規(guī)則的提取都是多余的，如果能將冗余的屬性和信息刪除，則信息系統(tǒng)的潛在知識清晰度和運(yùn)行效率都可以得到大幅提高；而粗糙集理論中的數(shù)據(jù)約簡可以將原始信息表的冗余數(shù)據(jù)和信息通過給定的算法消去，得到一個約簡，然后從這個約簡后的信息系統(tǒng)中提取有效的決策規(guī)則[7][8]。因此，可以用粗糙集的規(guī)則獲取方法，解決遠(yuǎn)程教育的上述兩個問題。針對這兩個問題，本文重點(diǎn)研究了如何用結(jié)合粗糙集理論的決策樹來建立一個約簡信息表，剔除冗余信息，得到?jīng)Q策規(guī)則，進(jìn)一步研究遠(yuǎn)程教育算法DLA[9]的實現(xiàn)，可以讓通過遠(yuǎn)程教育進(jìn)行網(wǎng)上學(xué)習(xí)者評估課程的重點(diǎn)章節(jié)，教育者也能對課程內(nèi)容安排做相應(yīng)的調(diào)整。

二、粗糙集的基本概念

粗糙集是一種處理含糊和不確定性問題的數(shù)學(xué)工具[10]。給定一個有不同屬性的對象集為[U=x1，x2，…，xn]的信息表，可以分別按照條件屬性、決策屬性進(jìn)行分類。每一個基于決策屬性的等價類定義了一個概念。我們使用[Des（Xi）]來表示等價類[Xi]的描述，即描述屬性集[Xi]的屬性值集合。

[Y]是一個概念，定義其下近似[Y]和上近似[Y]如下：

[Y=e∈Ue∈Xi且Xi?Y]

[Y][=e∈UE∈Xi且Xi Y≠?]

如果一個元素屬于[Y]-[Y]，則不能確定它是否在[Y]中，因此引入一個[Y]的判別式指標(biāo)的概念來度量[U]中的這個元素屬于[Y]的程度[11]，其定義如下：

[αQ1（Y）=1-Y-YU]

對于給定的信息表，并不是所有的屬性都是分類所必需的，條件屬性存在一個最小子集，得到這個最小子集的過程就是一個計算約簡的過程。

設(shè)[S=（U，A）]是一個信息系統(tǒng)，其中[U]為對象集，[U=x1，x2，…，xn]，[A]為屬性集，[A=a1，a2，…，ap]，對[a∈A]，如果[IND（A-a）=IND（A）]，則稱屬性[a]在[A]中是不必要的（多余的），否則稱屬性[a]在[A]中是必要的。

若每個屬性[a∈A]在[A]中都是必要的，則稱屬性集[A]是獨(dú)立的，否則稱它為依賴的，可以對其約簡。在本文中應(yīng)用了相對約簡的方法[12]。

給定[P]和[Q]為[U]中的等價關(guān)系，定義[Q]的[P]正域[posp（Q）]如下：

[posp（Q）=X∈U/QPX]

由定義可以看出，[Q]的[P]正域是由所有的根據(jù)分類[U]/[P]的信息被準(zhǔn)確地分到關(guān)系[Q]的等價類中去的對象組成的集合。針對決策信息系統(tǒng)，重點(diǎn)研究條件屬性關(guān)于決策屬性的正域。

三、遠(yuǎn)程教育算法DLA

遠(yuǎn)程教育算法DLA在評估某一個課程的各部分內(nèi)容的重要性方面，著重于一個概念，即[Des（Y）=Fail]，即想要找出是什么導(dǎo)致了在線學(xué)生不能通過考試，從而為教學(xué)雙方提供及時和有效的反饋，將粗糙集的屬性約簡融入算法中，可歸納為以下5步：

1. 對決策表中的原始數(shù)據(jù)進(jìn)行預(yù)處理；

2. 利用粗糙集算法，進(jìn)行屬性約簡，得到條件屬性關(guān)于決策屬性的約簡；

3. 初始化變量，只要條件屬性的個數(shù)不為零，那么進(jìn)行下一步；

4. 執(zhí)行當(dāng)型循環(huán)。在當(dāng)型循環(huán)中先計算條件屬性的判別式指標(biāo)，將最高的指標(biāo)值存入結(jié)果，且這個條件屬性從條件屬性集中移去。之后，輸出決定性的或非決定性的決策規(guī)則，從而決定一個新的論域。照此循環(huán)下去，直到新的論域變成空集，則執(zhí)行下一步；

5. 輸出所有決定性和非決定性的決策規(guī)則[13][14]。

四、遠(yuǎn)程教育算法DLA的實現(xiàn)

WebCT（Web Course Tools）[15]是由加拿大英屬哥倫比亞大學(xué)的計算機(jī)科學(xué)系為高校開發(fā)的異步課程傳遞及管理系統(tǒng)，包括一系列可以自動與課程內(nèi)容緊密集成的強(qiáng)大學(xué)習(xí)工具。 學(xué)生做作業(yè)、進(jìn)行小測驗和期末考試都在互聯(lián)網(wǎng)上進(jìn)行。 如果某個學(xué)生未通過期末考試，需要進(jìn)行重修，此時，學(xué)生會關(guān)心哪些章節(jié)比較薄弱，在下一輪重修中應(yīng)該將主要精力放在哪些內(nèi)容上，課程教授者也可以據(jù)此調(diào)整課程內(nèi)容。 本文以利用WebCT系統(tǒng)進(jìn)行某一門課程學(xué)習(xí)的數(shù)據(jù)庫作為實例， 研究粗糙集的屬性約簡和規(guī)則獲取算法如何在遠(yuǎn)程教育算法DLA中實現(xiàn)，從而輔助教學(xué)雙方更有效地進(jìn)行遠(yuǎn)程教學(xué)和學(xué)習(xí)。 數(shù)據(jù)庫見表1，其中有145名學(xué)生、6次小測驗和1次期末考試。

利用粗糙集理論，將數(shù)據(jù)庫中各次小測驗成績作為條件屬性，將期末考試成績作為決策屬性，可以先對屬性進(jìn)行約簡，找出決策屬性的關(guān)鍵條件屬性， 即對期末成績起決定作用的小測驗， 進(jìn)而得到小測驗所對應(yīng)的相關(guān)章節(jié)即為學(xué)生學(xué)習(xí)的重點(diǎn)。 最后由屬性約簡后的數(shù)據(jù)表導(dǎo)出所有的決策規(guī)則，為新學(xué)生的學(xué)習(xí)提供反饋指導(dǎo)的同時，課程教授者也可以相應(yīng)調(diào)整教學(xué)資源。以下為利用粗糙集對DLA算法實現(xiàn)的過程：

1. 對信息表進(jìn)行預(yù)處理，學(xué)生關(guān)心這門功課是否及格，因此可以把表1進(jìn)行如下處理：用P表示Pass， 即成績大于等于60分；F表示Fail， 即成績低于60分。將情況相同的學(xué)生歸為一類，由此得到一個簡單表（表2）。將原有的145條記錄分成了八類，表中的學(xué)生總?cè)藬?shù)變成了113，另外29名在每次小測驗都通過的學(xué)生，期末成績邏輯上應(yīng)該是Pass，3名在每次小測驗中都沒有通過的學(xué)生，他們的期末成績邏輯上應(yīng)該是Fail， 因此不做考慮。

2. 約簡。以各次小測驗成績?yōu)闂l件屬性，以期末成績?yōu)闆Q策屬性，進(jìn)行屬性約簡，本質(zhì)上是要剔除掉對于決策屬性為冗余的條件屬性。 為了實現(xiàn)這一步，用粗糙集理論結(jié)合線性搜索和排序方法來完成。 以表2為例，所有屬性的集合

[R=Q1，Q2，Q3，Q4，Q5，Q6，F(xiàn)inal]

[R]的正域為[POSR（F）=e1，e2，e3，e4，e5，e6，e7，e8]

為了計算[R]關(guān)于[Final]的約簡，需要研究[R]是否是[F-]獨(dú)立的。 使用當(dāng)型循環(huán)分別移去[Q1]、[Q2]、[Q3]、[Q4]、[Q5]和[Q6]來檢驗其正域，如果每次小測驗的正域不等于期末考試的正域，我們保留這個條件屬性，以下是部分運(yùn)算結(jié)果：

[POSR-Q1（F）=e1，e2，e3，e4，e5，e6，e7，e8=POSR（F）]

[U/IND（R-Q1）=e1，e7，e2，e3，e4，e5，e6，e8]

……

[U/IND（R-Q6）=e1，e7，e8，e2，e3，e4，e5，e6]

[POSR-Q6（F）=e1，e6，e7，e8≠POSR（F）]

由以上運(yùn)算可以得出結(jié)論：[e3]、[e5]、[e6]是不可少的，因為其正域不等于[Final]的正域。 由此，信息表簡化為表3。

3. 找出決策規(guī)則。 根據(jù)約簡后的信息表，可以看出：

論域：[U=e1，e2，e3，e4，e5，e6，e7，e8]

失敗范疇：[Y=e2，e3，e5，e6]

基于[Quiz3]的不可識別類是：

[Y1=e1，e6，e7，e8] [Des（Y1）=Quiz=P]

[Y2=e2，e3，e4，e5] [Des（Y2）=Quiz=F]

下近似[Y=] 上近似[Y=e1，e6，e7，e8，e2，e3，e4，e5]

識別指標(biāo)：[αQ3=1-Y-YU=0.00]

同樣，計算[Q5，Q6]的[α]指數(shù)，可以得到表4。

可以看出，[Quiz6]的識別值最高。也就是說，它最能決定一個成員是在范疇[Y]中的。因此，得到如下決策規(guī)則：

[Rule 1：Quiz6=F?Final=F]

從而以[Q6]為根節(jié)點(diǎn)的決策樹[16]為：

[Q6]

[e1：P；e4：P；e7：P] [e2：F；e3：F；e5：F；e6：F；e8：F]

基于決策樹，[Q6]取[F]值的新的約簡表為表5。

不難看出[Q6]和[Q3]，具有較高的識別指數(shù)，因此得到第2條規(guī)則：

[Rule2：Quiz6=F，Quiz3=F?Final=F]

其對應(yīng)的決策樹如下所示：

[Q6]

[e1：P；e4：P；e7：P] [e2：F；e3：F；e5：F；e6：F；e8：F]

[Q3]

[e6：F；e8：P] [e2：F；e3：F；e5：F]

運(yùn)用相同的方法可以得到：

[Rule3：Quiz6=F，Quiz5=F?Final=F]

以上的約簡過程得出了3條決策規(guī)則。為了度量以上決策規(guī)則的可信度，引入分類強(qiáng)度[17]的概念對規(guī)則的可信度進(jìn)行度量，可以用以下公式來計算：

[W=規(guī)則所覆蓋的正例子規(guī)則所覆蓋的例子（既包含正的，也包含負(fù)的）]

為了實現(xiàn)最后一步計算，再一次利用線性搜索，各規(guī)則的強(qiáng)度計算如表7。

表7 決策規(guī)則強(qiáng)度值表

[Rules＼&強(qiáng)度值W＼&[Rule1：Quiz6=F?Final=F]＼&56.52%＼&[Rule2：Quiz6=F，Quiz3=F?Final=F]＼&100.0%＼&[Rule3：Quiz6=F，Quiz5=F?Final=F]＼&100.0%＼&]

表7可以解釋，如果一個在線學(xué)習(xí)的學(xué)生在小測驗[Quiz6]中沒有通過，那么該學(xué)生期末考試將有56.52%的可能不能通過；如果一個學(xué)生在[Quiz6]和[Quiz3]中都沒有通過考試，那么該學(xué)生100%不能通過期末考試。 利用粗糙集理論進(jìn)行數(shù)據(jù)約簡，并獲得決策規(guī)則的過程，可以通過對以往在線學(xué)習(xí)的學(xué)生的表現(xiàn)分析，為后來學(xué)習(xí)同一門網(wǎng)絡(luò)課程的學(xué)生提供指導(dǎo)。

基于粗糙集的規(guī)則獲取算法比WZY算法[18]更適用于WebCT遠(yuǎn)程教育系統(tǒng)， 二者的區(qū)別在于WZY算法不會輸出非決定性規(guī)則，如本文中的[Rule1]， 而本文基于粗糙集的規(guī)則獲取算法， 決定性規(guī)則和非決定性規(guī)則都會輸出。 這些規(guī)則能告訴學(xué)生在線學(xué)習(xí)的重點(diǎn)章節(jié)。 此外，WebCT只關(guān)心決策屬性的一個概念，即Fail，WZY算法則覆蓋多個概念，因此計算起來復(fù)雜度較基于粗糙集的規(guī)則獲取算法更高。

最后，針對算法的擴(kuò)展性問題，基于粗糙集理論給出增量規(guī)則獲取算法的步驟：

1. 當(dāng)有新樣本加入時，首先檢查它們是否與已有的規(guī)則集相容，是否能被已有規(guī)則集包含。如果相容且被包含，則規(guī)則集無須修正；如果相容但不被包含，則直接將新樣本加入規(guī)則樣本表，并用本文的算法約簡帶通配符的決策表；如果不相容，則轉(zhuǎn)入下一步。

2. 在規(guī)則樣本表里找到導(dǎo)致不相容的規(guī)則樣本及其對應(yīng)的實驗樣本的序號，將這些實驗樣本數(shù)據(jù)從原始決策表中取出來代替該規(guī)則樣本，然后結(jié)合新加入的實驗樣表，得到帶通配符的決策表，最后再利用本文的方法再次約簡這個決策表。

利用已有的規(guī)則獲取算法，將實驗樣本合并后提取為規(guī)則樣本，以此代替原始決策表中的海量數(shù)據(jù)，并借助通配符進(jìn)行約簡，可以大大減少待約簡的數(shù)據(jù)規(guī)模，提高了規(guī)則修正的效率。

五、 結(jié)論

本文通過運(yùn)用粗糙集實現(xiàn)遠(yuǎn)程教育算法，對遠(yuǎn)程教育學(xué)習(xí)過程中的冗余數(shù)據(jù)進(jìn)行了約簡，獲取了決策規(guī)則，并利用可信度對規(guī)則的強(qiáng)度進(jìn)行了度量，克服了遠(yuǎn)程教育系統(tǒng)WebCT的信息反饋缺失問題。 一方面，參加遠(yuǎn)程教育的學(xué)習(xí)者根據(jù)歷史經(jīng)驗，重點(diǎn)學(xué)習(xí)某一門課程的關(guān)鍵章節(jié)；另一方面，也可以讓教育者就某些重要部分，對網(wǎng)站上的課程安排、教學(xué)內(nèi)容設(shè)計等做出相應(yīng)的調(diào)整，使網(wǎng)上的資源更加適應(yīng)學(xué)習(xí)的要求，也更能反映出某門在線課程的重點(diǎn)和難點(diǎn)。 文中的結(jié)論不僅適用于互聯(lián)網(wǎng)上的遠(yuǎn)程教學(xué)，也適用于實際教學(xué)中，能給教師提供直接的教學(xué)反饋。

與傳統(tǒng)的規(guī)則獲取算法不同，本文的規(guī)則獲取算法，在數(shù)據(jù)庫更新時，無須在原有的數(shù)據(jù)庫內(nèi)部重新進(jìn)行屬性約簡及規(guī)則獲取，在減少待約簡的數(shù)據(jù)規(guī)模的同時，提高了規(guī)則修正的效率。 然而，針對原有決策表中含有不完全數(shù)據(jù)或者沖突樣本的情形，如何對文中算法進(jìn)行改進(jìn)，有待進(jìn)一步研究。

[參考文獻(xiàn)]

[1][12] 張文修. 粗糙集理論與方法[M]. 北京：科學(xué)出版社，2001.

[2][7][10] 植小三，印勇，黃楊帆. 基于粗糙集理論的一種數(shù)據(jù)約簡算法[J]. 云南民族學(xué)院學(xué)報（自然科學(xué)版），2003，12（2）：86-88.

[3][8][11] 艾麗軍，占傳杰，熊鎮(zhèn)山. 基于Rough集實現(xiàn)判定樹歸納分類算法的簡化[J]. 鹽城工學(xué)院學(xué)報（自然科學(xué)版），2004，17（3）：86-88：30-33.

[4] 溫泉，江美英，覃俊. 遠(yuǎn)程教育中基于粗糙集的聚類算法[J]. 中南民族大學(xué)學(xué)報（自然科學(xué)版），2007，26（1）：84-88.

[5] 張德洪. 遠(yuǎn)程教育系統(tǒng)設(shè)計中的自動組卷算法研究[J]. 赤峰學(xué)院學(xué)報，2010，26（12）：45-47.

[6] 張曉芳. 聚類分析算法在遠(yuǎn)程教育系統(tǒng)中的應(yīng)用研究[J]. 科技通報，2013，29（4）：106-109.

[9][15] Hongyan Geng and Maguire. A Rough Set Methodology to Support Learner Self-Assessment in Web-Based Distance Education， Rough sets， fuzzy sets， data mining， and granular computing ： 9th international conference， Berlin ； New York ： Springer， 2003.

[13][18] A. H. Liang， B. Maguire， and J. Johnson. Rough Set Based WebCT Learning. Proceeding of the 1st International conference on Web-Age Information Management， Shanghai， P. R. China， June 21-23， 2000. Springer-Verlag LNCS 1846.

[14] S.K.M. Wong， W.Ziarko， and R.L.Ye. Comparison of rough-set and statistical methods in inductive learning . International Journal of Man-Machine Studies， 1986， 24：52-72.

[16] 翟俊海，翟夢堯，李勝杰. 基于相容粗糙集技術(shù)的連續(xù)值屬性決策樹歸納[J]. 計算機(jī)科學(xué)，2012，39（11）：183-186.

[17] Yao Yu， Fu Zhong-liang， Zhao Xiang-hui，Cheng Wen-fang. Combining Classifier based on Decision Tree. 2009 WASE International Conference on information Engineering. 2009： 37-40.

收稿日期：2014-10-15

定稿日期：2015-05-13

作者簡介：楊慧，在讀博士，講師；丁正生，教授。西安科技大學(xué)（710054）。

責(zé)任編輯 日 新