馮丹露 李進(jìn)金,2 李招文 周銀鳳 楊桃麗

知識(shí)空間理論(Knowledge Space Theory, KST)[1-3]為開發(fā)基于計(jì)算機(jī)化的知識(shí)評(píng)估系統(tǒng)提供一個(gè)重要的數(shù)學(xué)心理框架.KST的核心概念是知識(shí)狀態(tài)和知識(shí)結(jié)構(gòu).個(gè)體的知識(shí)狀態(tài)K是在理想狀態(tài)下能夠正確回答的特定知識(shí)領(lǐng)域Q中的問題構(gòu)成的集合.理想狀態(tài)是指學(xué)生沒有出現(xiàn)粗心致錯(cuò)和幸運(yùn)蒙對(duì)的情況.知識(shí)結(jié)構(gòu)(Q,K)是在總體中可以觀察到的所有知識(shí)狀態(tài)構(gòu)成的集合.知識(shí)結(jié)構(gòu)至少包含?和Q,通常直接使用K表示知識(shí)結(jié)構(gòu).

如何構(gòu)建知識(shí)結(jié)構(gòu)是KST的研究熱點(diǎn)之一.最初,KST是在純粹的行為視角下發(fā)展起來的.此時(shí),獲取知識(shí)結(jié)構(gòu)的方法主要有基于問詢專家的Query[4-6]和Ps-Query[6].這兩種方法只考慮專家的判斷,忽視不同個(gè)體可能具有不同的潛在認(rèn)知能力.另外,這兩種方法要求個(gè)體對(duì)問題的解答要么完全正確要么完全錯(cuò)誤,最終只能給出個(gè)體的解答成績(jī),無法更深層次地評(píng)估個(gè)體的認(rèn)知能力.

KST在引入技能的概念[7]后,超越單純的行為解釋,為構(gòu)建知識(shí)結(jié)構(gòu)提供認(rèn)知解釋的可能性.技能代表潛在的認(rèn)知能力,每個(gè)技能都可視為一種方法、策略或能力,個(gè)體可以使用技能解決一組問題.在KST中,給定一個(gè)技能領(lǐng)域S,將技能與問題的特定關(guān)系表示成一個(gè)技能映射.Doignon[7]給出技能映射在析取模型和合取模型下誘導(dǎo)知識(shí)結(jié)構(gòu)的方法.基于技能映射,一些學(xué)者將KST與形式概念分析(Formal Concept Analysis, FCA)[8]結(jié)合,給出獲取知識(shí)結(jié)構(gòu)的不同方法.

FCA[8]是進(jìn)行知識(shí)表示和數(shù)據(jù)處理的重要工具.FCA通過對(duì)象和屬性的特定關(guān)系,建立概念格,將知識(shí)可視化[9].Rusch等[10]提出知識(shí)背景的概念,給出由知識(shí)背景構(gòu)建知識(shí)結(jié)構(gòu)的方法,首次建立KST和FCA之間的聯(lián)系,為研究KST提供一個(gè)新的途徑.Spoto等[11]將KST運(yùn)用到心理學(xué)中,借助FCA的表征形式,開發(fā)一種有效的適應(yīng)性心理評(píng)估工具.李進(jìn)金等[12]給出在形式背景中由知識(shí)基獲取知識(shí)結(jié)構(gòu)的方法.周銀鳳等[13]和Zhou等[14]基于形式背景的概念,建立技能函數(shù)和多尺度形式背景的關(guān)系,分別給出基于技能映射和技能函數(shù)構(gòu)建知識(shí)結(jié)構(gòu)的不同方法.上述方法借助概念獲取的思想,但只能單純獲得知識(shí)結(jié)構(gòu),無法直接獲得每個(gè)知識(shí)狀態(tài)對(duì)應(yīng)的技能掌握情況.另外,周銀鳳等[15]借助面向?qū)ο?屬性)概念,進(jìn)一步討論技能函數(shù)下個(gè)體的表現(xiàn)水平和能力水平的一一對(duì)應(yīng)條件,但如需建立唯一的對(duì)應(yīng)關(guān)系,還需改進(jìn)條件.

在獲取知識(shí)結(jié)構(gòu)的過程中,某些技能可能是冗余的.約簡(jiǎn)冗余技能,獲得極小技能映射,既不影響生成原有的知識(shí)結(jié)構(gòu),還能更快地獲取知識(shí)結(jié)構(gòu).為此,Doignon[7]提出極小技能映射的概念.Xu等[16]借助粗糙集屬性約簡(jiǎn)的思想,獲取極小技能集.Düntsch等[17]研究技能多映射的極小技能多映射.周銀鳳等[13]提出技能背景的概念,給出一種技能約簡(jiǎn)方法.但現(xiàn)有的技能約簡(jiǎn)方法只能對(duì)整個(gè)技能進(jìn)行約簡(jiǎn).

通過上述方法獲取的知識(shí)結(jié)構(gòu)是在理想狀態(tài)下的所有知識(shí)狀態(tài)構(gòu)成的集合.在真實(shí)測(cè)試過程中,個(gè)體在解決某個(gè)問題時(shí)可能處于一種不理想的狀態(tài),即可能存在個(gè)體實(shí)際能解決某個(gè)問題,但由于粗心錯(cuò)誤導(dǎo)致該問題沒有解決,或存在個(gè)體實(shí)際沒有能力解決某個(gè)問題,但由于個(gè)體的幸運(yùn)猜測(cè)而解決該問題,導(dǎo)致得到的知識(shí)狀態(tài)和知識(shí)結(jié)構(gòu)不符合知識(shí)之間的邏輯性.因此,如何獲得準(zhǔn)確的知識(shí)狀態(tài)和知識(shí)結(jié)構(gòu)受到學(xué)者的關(guān)注[18-20].為了更準(zhǔn)確地評(píng)估個(gè)體的行為表現(xiàn)層次與真實(shí)認(rèn)知能力的一致性,將基本局部獨(dú)立模型[18]引入KST中.

基本局部獨(dú)立模型是對(duì)個(gè)體真實(shí)存在但未知的知識(shí)狀態(tài)與個(gè)體在測(cè)評(píng)中的反應(yīng)模式進(jìn)行區(qū)分的概率模型.它將粗心錯(cuò)誤和幸運(yùn)猜測(cè)概率視為錯(cuò)誤率,從概率的角度評(píng)估一個(gè)知識(shí)結(jié)構(gòu)對(duì)數(shù)據(jù)的擬合性.目前,基本局部獨(dú)立模型已應(yīng)用于許多不同的環(huán)境中[18-20]但將基本局部獨(dú)立模型應(yīng)用于前級(jí)(For-ward-Graded)知識(shí)結(jié)構(gòu)和后級(jí)(Backward-Graded)知識(shí)結(jié)構(gòu)中會(huì)呈現(xiàn)不可識(shí)別的問題.事實(shí)上,若知識(shí)結(jié)構(gòu)在某個(gè)問題處是前級(jí)的,說明知識(shí)結(jié)構(gòu)對(duì)這個(gè)問題的幸運(yùn)猜測(cè)恰好為0.若知識(shí)結(jié)構(gòu)在某個(gè)問題處是后級(jí)的,說明知識(shí)結(jié)構(gòu)對(duì)這個(gè)問題的粗心誤差恰好為0.因此,近年來,前級(jí)(后級(jí))知識(shí)結(jié)構(gòu)得到學(xué)者們的特別關(guān)注[21-25].Spoto等[21]給出技能映射在析取模型和合取模型下誘導(dǎo)的知識(shí)結(jié)構(gòu)是前級(jí)和后級(jí)的充分條件.Spoto等[25]在充分條件的基礎(chǔ)上進(jìn)一步給出必要條件,并給出技能映射在析取模型和合取模型下誘導(dǎo)的知識(shí)結(jié)構(gòu)是后級(jí)和前級(jí)的充要條件.

上述對(duì)知識(shí)結(jié)構(gòu)的獲取、技能約簡(jiǎn)和前級(jí)(后級(jí))知識(shí)結(jié)構(gòu)的研究均是在技能映射下討論的.對(duì)于技能映射,個(gè)體想要解決某個(gè)問題必須要完全掌握某些技能,否則將無法解決這個(gè)問題,但個(gè)體學(xué)習(xí)技能的過程是循序漸進(jìn)的.由于個(gè)體的接受水平和認(rèn)知能力是有差異的,在相同的學(xué)習(xí)環(huán)境中,不同個(gè)體能達(dá)到的技能熟練程度是不同的.因此,Sun等[26]提出模糊技能映射的概念,表示解決不同的問題需要的技能熟練程度不同,并給出模糊技能映射在析取模型、合取模型和能力模型下誘導(dǎo)知識(shí)結(jié)構(gòu),以及保持知識(shí)結(jié)構(gòu)不變,進(jìn)行技能約簡(jiǎn)的方法.模糊技能映射更能體現(xiàn)個(gè)體的認(rèn)知水平差異和個(gè)性化能力,然而模糊技能映射誘導(dǎo)前級(jí)知識(shí)結(jié)構(gòu)或后級(jí)知識(shí)結(jié)構(gòu)的條件尚未得到研究.因此,討論如何快速獲取模糊技能映射下誘導(dǎo)的知識(shí)結(jié)構(gòu),以及給出快速判斷模糊技能映射誘導(dǎo)的知識(shí)結(jié)構(gòu)是前級(jí)和后級(jí)的條件具有重要意義.

受到FCA和KST之間聯(lián)系的啟發(fā),本文將模糊概念格思想[27-33]引入基于模糊技能映射的KST中.首先,引入模糊技能背景的概念,建立模糊技能映射和模糊技能背景的對(duì)應(yīng)關(guān)系.構(gòu)造一對(duì)算子,生成模糊技能概念格.模糊技能概念格的外延集和內(nèi)涵集分別對(duì)應(yīng)模糊技能映射在合取模型下誘導(dǎo)的簡(jiǎn)單閉包空間和每個(gè)知識(shí)狀態(tài)對(duì)應(yīng)的最小技能熟練程度.因此,模糊概念格可用于評(píng)估個(gè)體的認(rèn)知水平和指導(dǎo)進(jìn)一步的學(xué)習(xí).然后,提出技能層約簡(jiǎn)的概念,建立模糊技能背景與標(biāo)記技能背景的特定關(guān)系,對(duì)技能層進(jìn)行約簡(jiǎn),并設(shè)計(jì)技能層約簡(jiǎn)的算法.另外,基于模糊技能背景,討論簡(jiǎn)單閉包空間是前級(jí)和后級(jí)的充要條件,并給出相應(yīng)的算法.最后,在5個(gè)數(shù)據(jù)集上的數(shù)值實(shí)驗(yàn)驗(yàn)證本文算法的有效性.

1 基礎(chǔ)知識(shí)

本節(jié)回顧模糊形式概念分析與模糊技能映射的一些基本概念和性質(zhì).

1.1 模糊形式概念分析

定義1[34]三元組(U,A,I)稱為一個(gè)形式背景,其中U={x1,x2,…,xn}為對(duì)象集,A={a1,a2,…,am} 為屬性集,I?U×A為U和A之間的二元關(guān)系.若(x,a)∈I,稱對(duì)象x具有屬性a;若(x,a)?I,稱對(duì)象x不具有屬性a.

定義2[34]設(shè)(U,A,I)為形式背景,對(duì)X?U和B?A,分別定義運(yùn)算:

X↓={a∈A|?x∈X,(x,a)∈I},

B↑={x∈U|?a∈B,(x,a)∈I}.

若

X=B↑,B=X↓,

稱(X,B)為一個(gè)概念,其中,X為概念的外延,B為概念的內(nèi)涵.L(U,A,I)表示(U,A,I)的全體概念.

定義3[34]設(shè)(U,A,I)為形式背景,對(duì)

?(X1,B1)∈L(U,A,I),(X2,B2)∈L(U,A,I),

定義偏序關(guān)系:

(X1,B1)≤(X2,B2)?X1?X2?B2?B1.

另外,在L(U,A,I)上定義

(X1,B1)∨(X2,B2)=((X1∪X2)↓↑,B1∩B2),

(X1,B1)∧(X2,B2)=(X1∩X2,(B1∪B2)↑↓),

則(L(U,A,I),∨,∧)為完備格,稱L(U,A,I)為(U,A,I)的概念格.

設(shè)U為一個(gè)有限非空集,P(U)表示U的所有子集構(gòu)成的集合,F(U)表示U的所有模糊子集構(gòu)成的集合.

定義4[35]設(shè)P、Q為兩個(gè)有序集,給定映射

φ∶P→Q,ψ∶Q→P.

若映射對(duì)(φ,ψ)滿足

φ(p)≤q?p≥ψ(q),

稱(φ,ψ)為P和Q之間的反序伽羅瓦連接.

定義5[36]設(shè)P、Q為兩個(gè)有序集,給定映射

φ∶P→Q,ψ∶Q→P.

若映射對(duì)(φ,ψ)滿足

φ(p)≤q?p≤ψ(q),

稱(φ,ψ)為P和Q之間的單調(diào)伽羅瓦連接.

h∶P(U)→F(A),k∶F(A)→P(U)

如下:

1.2 模糊技能映射

技能可以反映個(gè)體潛在的認(rèn)知能力,個(gè)體掌握一個(gè)技能的過程是循序漸進(jìn)的.因此,不同個(gè)體在同一時(shí)刻對(duì)技能的掌握程度可能是不同的.為了更好地評(píng)估個(gè)體對(duì)技能的掌握情況,Sun等[26]提出模糊技能映射的概念,對(duì)不同問題賦予不同的技能熟練程度,個(gè)體掌握技能的程度決定其能否解決相應(yīng)的問題.

設(shè)S為非空技能集,

定義7[26]三元組(Q,S,τ)稱為一個(gè)模糊技能映射,其中Q={q1,q2,…,qn}為非空問題集,S={s1,s2,…,sm}為非空技能集,τ為從Q到F(S)?的映射.對(duì)q∈Q,記τq=τ(q)表示分配給問題q的所有模糊技能子集.τq(s)≠0表示解決問題q至少需要掌握技能s的程度.若τq(s)=0,表示問題q的求解與技能s無關(guān).

合取模型表示個(gè)體至少需要達(dá)到解決問題q所需的每個(gè)技能的最小技能熟練程度.Sun等[26]將合取模型下誘導(dǎo)相同知識(shí)狀態(tài)的所有模糊技能集視為等價(jià)的,進(jìn)而對(duì)F(S)內(nèi)的模糊技能集進(jìn)行分類.因此,模糊技能映射(Q,S,τ)在合取模型下由F(S)內(nèi)所有模糊技能集的等價(jià)類誘導(dǎo)的知識(shí)狀態(tài)構(gòu)成的集族K是一個(gè)知識(shí)結(jié)構(gòu).

引理1[26]設(shè)(Q,S,τ)為模糊技能映射,K為(Q,S,τ)在合取模型下誘導(dǎo)的知識(shí)結(jié)構(gòu),則K是一個(gè)簡(jiǎn)單閉包空間.

定義9[26]設(shè)(Q,K)為簡(jiǎn)單閉包空間.若存在一個(gè)子集族K′?K,使得對(duì)?K∈K,都存在一個(gè)子集族A?K′,使得K=∩A成立,則稱K′為K的交式生成組.

交式生成組是能交成簡(jiǎn)單閉包空間的極小知識(shí)狀態(tài)構(gòu)成的集族.若求得極小交式生成組,則可求得簡(jiǎn)單閉包空間.

2 模糊技能背景

在模糊形式背景中,對(duì)象與屬性之間存在模糊二元關(guān)系,而模糊技能映射建立了解決問題與所需掌握技能程度的關(guān)系,故可從模糊形式背景的角度思考與模糊技能映射相關(guān)的一些問題.

顯然有

即模糊技能背景與模糊技能映射具有一一對(duì)應(yīng)的關(guān)系.故本文將模糊技能映射誘導(dǎo)的知識(shí)結(jié)構(gòu)統(tǒng)一稱為模糊技能背景誘導(dǎo)的知識(shí)結(jié)構(gòu).

技能可以反映個(gè)體不可觀測(cè)的認(rèn)知能力,不同個(gè)體的潛在認(rèn)知能力是不同的.KST觀察個(gè)體對(duì)問題的解決情況,評(píng)估個(gè)體潛在的認(rèn)知能力水平,進(jìn)而指導(dǎo)個(gè)體下一步的學(xué)習(xí).因此,獲得個(gè)體的知識(shí)狀態(tài)與對(duì)應(yīng)的技能掌握情況對(duì)評(píng)估個(gè)體知識(shí)和指導(dǎo)下一步的技能學(xué)習(xí)具有重要意義.

Sun等[26]給出模糊技能映射在合取模型下誘導(dǎo)簡(jiǎn)單閉包空間的方法,但只能獲得知識(shí)狀態(tài),不能同時(shí)獲得該知識(shí)狀態(tài)對(duì)應(yīng)的技能掌握情況.而通過概念格,可將對(duì)象集和屬性集的某些特定關(guān)系通過概念的內(nèi)涵和外延進(jìn)行反映.基于該思想,本文構(gòu)造一對(duì)算子,通過其對(duì)應(yīng)的概念反映知識(shí)狀態(tài)和技能掌握情況的關(guān)系,直接得到技能評(píng)估和學(xué)習(xí)路徑圖.考慮到模糊技能映射在合取模型下誘導(dǎo)的知識(shí)結(jié)構(gòu)的特點(diǎn),基于模糊技能背景構(gòu)造如下2個(gè)算子.

f∶P(Q)→ F(S),g∶F(S)→P(Q)

如下:

因此定義

反之,假設(shè)個(gè)體解決的問題集為B,則個(gè)體至少已達(dá)到解決B中所有問題所需的最小技能熟練程度.因此定義

另外,F(S)上的運(yùn)算定義如下[37]:

根據(jù)定義的映射f°g,可得如下性質(zhì)1.

B1?B2?f(B1)?f(B2);

因此,對(duì)?s∈S,有

同理可證

B1?B2?f(B1)?f(B2).

故對(duì)?s∈S,有

從而

此外,因?yàn)閷?duì)?q∈B,s∈S,有

故q∈g°f(B),從而

B?g°f(B).

又因?yàn)?/p>

B?g°f(B),

又因?yàn)?/p>

再證4).由2)有

B?g°f(B),

又由1)可得

f(B)?f°g°f(B).

因?yàn)?/p>

故

f°g°f(B)?f(B).

從而

f°g°f(B)=f(B).

同理可證

最后證5).對(duì)

滿足對(duì)?i∈J,s∈S,有

于是對(duì)?s∈S,有

成立,故

從而

反之,對(duì)

滿足對(duì)?s∈S,有

于是對(duì)?i∈J,s∈S,有

成立,故

從而

綜上可得

下證

由

可證.

證畢

根據(jù)定義5,性質(zhì)1中3)說明映射對(duì)(f,g)形成(P(Q),?)和(F(S),?)之間的單調(diào)伽羅瓦連接.根據(jù)文獻(xiàn)[38],假設(shè)(f,g)形成集合X和Y之間的單調(diào)伽羅瓦連接.對(duì)映射對(duì)(h,k),若對(duì)?A∈2X,B∈2Y,有

h(A)=Yf(A),k(B)=g(YB)

成立,則(h,k)是一個(gè)反序伽羅瓦連接,即通過該過程可建立反序伽羅瓦連接和單調(diào)伽羅瓦連接的雙射.顯然,本文定義的映射f°g與定義6定義的映射h°k不符合這種雙射關(guān)系.

定義偏序關(guān)系:

有

證明由性質(zhì)1中4)、5),有

{(g°f(q),f(q))|q∈Q}

中的某些模糊技能概念的上確界表示.

證明對(duì)

滿足存在i,使得對(duì)?s∈S,有

成立.因此,對(duì)?s∈S,有

故

從而

證畢

成立,則

當(dāng)且僅當(dāng)

證明先證充分性.轉(zhuǎn)證

顯然只需再證

由性質(zhì)1中4)、5),有

又因?yàn)?/p>

所以

從而,有

再證必要性.由推論2,只需再證

對(duì)

滿足對(duì)?s∈S,有

成立,又由性質(zhì)1中4),有

f°g°f(B)=f(B),

故

所以對(duì)?s∈S,有

另外,由性質(zhì)1中5),對(duì)?s∈S,顯然有

故

又因?yàn)?/p>

所以

即

故

從而

證畢

成立.由

可得對(duì)?q∈B,s∈S,有

綜上,有

證畢

注意到F(S)中的模糊集是無限的,但在KST中,模糊技能映射是給定的,故在本文中,基于模糊技能映射限制F(S).對(duì)s∈S,記

對(duì)

例1設(shè)

Q={q1,q2,q3,q4,q5},S={s1,s2,s3,s4,s5},

給定模糊技能映射(Q,S,τ),其中

圖1 模糊技能概念L格

表1 模糊技能背景

{?,{q2},{q4},{q3,q4},{q4,q5},{q1,q4,q5},

{q2,q4,q5},{q3,q4,q5},{q1,q2,q4,q5},

{q1,q3,q4,q5},{q2,q3,q4,q5},Q}.

念集T

輸出模糊技能概念集T

step 1 令P=?,T=?.

step 2 對(duì)?q∈Q,計(jì)算f(q).

step 4 對(duì)?X′∈P,計(jì)算g(X′),獲得

step 5 輸出模糊技能概念集T.

在算法1中,step 2、step 3的時(shí)間復(fù)雜度最大為O(|2Q|),step 4的時(shí)間復(fù)雜度最大為O(|P||S|),故算法1的時(shí)間復(fù)雜度最大為

O(|2Q|+(|P||S|)).

3 技能層約簡(jiǎn)

在KST中,技能約簡(jiǎn)是在保持知識(shí)結(jié)構(gòu)不變的前提下,刪除冗余技能.技能約簡(jiǎn)能更簡(jiǎn)潔地表示問題與技能之間的關(guān)系,從而有效提高生成知識(shí)結(jié)構(gòu)的效率.Sun等[26]給出模糊技能映射下的技能約簡(jiǎn)的方法,但在模糊技能映射的背景下,不一定需要?jiǎng)h除整個(gè)技能才能保持生成的知識(shí)結(jié)構(gòu)不變.因此,本文提出技能層約簡(jiǎn)的概念,拓展KST的技能約簡(jiǎn)概念,減少生成簡(jiǎn)單必包空間的時(shí)間.

為技能s在Q中的技能層集.x∈W(s)稱為技能s的一個(gè)技能層.

1)存在q∈Q,s∈S′,有

成立,

2)?q∈Q,s∈S′,有

成立,

若對(duì)q∈Q,s∈S′,有

成立,則稱x為技能s的可約簡(jiǎn)技能層.

顯然,對(duì)于任意技能s∈S的最小技能層∧W(s),已經(jīng)不存在小于它的技能層,故任意技能s∈S的最小技能層∧W(s)都不是可約簡(jiǎn)技能層.另外,對(duì)每個(gè)技能s∈S,若至少存在一個(gè)x∈W(s)且x≠∧W(s),使得x不是技能s的可約簡(jiǎn)技能層,則有S′=S.

稱為標(biāo)記技能集,?sx∈SX稱為一個(gè)標(biāo)記技能,I?Q×SX定義為:對(duì)?q∈Q,s∈S,x∈W(s),有

定義17建立模糊技能背景和標(biāo)記技能背景的轉(zhuǎn)換關(guān)系,顯然有如下推論.

對(duì)q∈Q,s∈S,若對(duì)?x∈W(s),有(q,sx)∈I成立,則

對(duì)于標(biāo)記技能背景(Q,SX,I),將每個(gè)標(biāo)記技能sx∈SX視為形式背景的一個(gè)屬性,通過定義2的映射↑°↓確定的概念格稱為標(biāo)記技能概念格,記為L(zhǎng)(Q,SX,I).另外,記LQ(Q,SX,I)表示L(Q,SX,I)的所有外延構(gòu)成的集族.

證明先證

設(shè)存在B?Q,使得B∈LQ(Q,SX,I)成立,則存在T?SX,使B=T↑成立.對(duì)?s∈S,

T(s)={x∈W(s)|sx∈T}.

另外,對(duì)?s∈S,令

下證

設(shè)q∈B=T↑,則對(duì)?sx∈T,有(q,sx)∈I,等價(jià)于對(duì)?s∈S和x∈T(s),有

等價(jià)于對(duì)?s∈S,有

故

從而

再證

令

下證B=T↑.對(duì)

滿足對(duì)?s∈S,有

等價(jià)于對(duì)?s∈S,x∈T(s),有

等價(jià)于對(duì)?sx∈T,有(q,sx)∈I,故

從而B=T↑.

證畢

則其通過對(duì)應(yīng)關(guān)系

確定的概念格同構(gòu).

證明由定理3,映射f°g和↑°↓在2Q上得到的概念格同構(gòu),則其通過對(duì)應(yīng)關(guān)系

確定的概念格同構(gòu).只需再證

先證

對(duì)

因?yàn)?/p>

故對(duì)?q∈B,s∈S,x∈W(s),有

又因?yàn)?/p>

從而sx∈B↓.

再證

假設(shè)存在s∈S,x∈W(s),使

又因?yàn)?/p>

證畢

由于對(duì)?s∈S,當(dāng)x=∨W(s)時(shí),對(duì)?q∈Q,都有

恒成立,即對(duì)?q∈Q,s∈S,都有

(q,s∨W(s))∈I?I(q,s∨W(s))=1

恒成立.根據(jù)↑°↓的定義,?s∈S,s∨W(s)都會(huì)出現(xiàn)在標(biāo)記技能概念格L(Q,SX,I)的每個(gè)概念的內(nèi)涵中.因此,為了簡(jiǎn)便表示,在標(biāo)記技能概念格L(Q,SX,I)中,除外延{?}對(duì)應(yīng)的內(nèi)涵以外,其它所有外延對(duì)應(yīng)的內(nèi)涵中的s∨W(s),?s∈S都忽略不寫.

圖2 標(biāo)記技能概念格L(Q,SX,I)

表2 標(biāo)記技能背景(Q,SX,I)

sx*=(sx)*={q∈Q|(q,sx)∈I}

證明對(duì)于標(biāo)記技能背景(Q,SX,I),因?yàn)?/p>

LQ(Q,SX,I)={T↑|?T?SX,T=T↑↓},

且對(duì)于任意一個(gè)標(biāo)記技能集T?SX,都有

故{sx*|sx∈SX}為L(zhǎng)Q(Q,SX,I)的一個(gè)交式生成組.

證畢

保持LQ(Q,SX,I)不變的標(biāo)記技能約簡(jiǎn)等價(jià)于保持LQ(Q,SX,I)的交式生成組不變的標(biāo)記技能約簡(jiǎn).對(duì)?s∈S,

若x=∨W(s),因?yàn)閷?duì)于?s∈S,q∈Q,都有

(q,s∨W(s))∈I,

即對(duì)于?s∈S,有

s∨W(s)*=Q

SX={sx|s∈S,x∈W(s)且x≠∨W(s)}.

另外,對(duì)sx∈SX,若存在t∈S{s},y∈W(t),使得sx*=ty*,說明標(biāo)記技能sx和ty提供誘導(dǎo)簡(jiǎn)單閉包空間LQ(Q,SX,I)的作用是一樣的.因此,對(duì)sx∈SX,記

[sx]={ty∈SX|sx*=ty*}

表示標(biāo)記技能sx的等價(jià)類.

下面將極小標(biāo)記技能背景轉(zhuǎn)化成一個(gè)新的模糊技能背景,使其對(duì)應(yīng)生成概念格同構(gòu).

記

S1={s∈S|X1(s)≠?},

滿足

x′>∨{x∈X1(s)|(q,sx)?I1},

且不存在x″∈W(s),使得

x′>x″>∨{x∈X1(s)|(q,sx)?I1}

成立.另外,對(duì)q∈Q,s∈S,若對(duì)?x∈X1(s),有(q,sx)∈I1成立,則

則

1)存在q∈Q,s∈S1,有

成立;

2)?q∈Q,s∈S1,有

成立.

P(s)={x1,x2,…xn} ?X(s).

假設(shè)

sP={sx|x∈P(s)}

為s對(duì)應(yīng)的所有可約簡(jiǎn)標(biāo)記技能構(gòu)成的集合,若

P(s)={x1,x2,…xn}=X(s),

即n=|X(s)|,則s?S1.另外,假設(shè)對(duì)?s′∈S1{s},都有|P(s′)|=0,則由定義19,顯然對(duì)?q∈Q,有

由

顯然不存在對(duì)?s′∈S1{s},都滿足n=|X(s′)|的情形.因此,只需再討論

P(s)={x1,x2,…,xn}?X(s), 1≤n<|X(s)|

的情形.下證對(duì)該技能s,滿足對(duì)?q∈Q,有

令

Y=(X(s)P(s))∪{∨W(s)},

顯然有1≤|Y|<|X(s)|.令

則對(duì)?q∈M,x∈X(s),有(q,sx)∈I.因此,對(duì)?q∈M,y∈Y,有(q,sy)∈I1,則由定義19,對(duì)?q∈M,有

成立.從而,對(duì)?q∈M,有

將?xi∈X(s),i=1,2,…,|X(s)|,從小到大排序,假設(shè)

x1<…

成立.對(duì)?q∈Q{M},存在xi∈X(s),i∈{1,2,…,|X(s)|},有(q,sxi)?I,且?j=i+1,i+2,…,|W(s)|,有(q,sxj)∈I.由定義17的轉(zhuǎn)換關(guān)系,對(duì)?q∈Q{M},有

成立.假設(shè)sxi為一個(gè)可約簡(jiǎn)標(biāo)記技能,且

xi=∧X(s),

則由定義19,對(duì)?q∈Q{M},有

從而,對(duì)?q∈Q{M},有

假設(shè)sxi為一個(gè)可約簡(jiǎn)標(biāo)記技能,且

xi≠∧X(s),

記

則由定義19,對(duì)?q∈Q{M},有

從而,對(duì)?q∈Q{M},有

綜上,對(duì)該技能s,存在q∈Q,有

且對(duì)?q∈Q,有

又因?yàn)閷?duì)?s″∈S1{s},有上述類似結(jié)論成立,故1)和2)成立.

證畢

由定理5和定義15,顯然有如下推論.

對(duì)?xi∈W(s),i=1,2,…,m,1≤m≤|W(s)|,假設(shè)

x1<…

成立.若sxu(xu≠xm)為一個(gè)可約簡(jiǎn)標(biāo)記技能,則xv為s的一個(gè)可約簡(jiǎn)技能層.

證明先證充分性.假設(shè)(q,sx)?I1,由定義19,有

證畢

證明先證

T(s)={x∈X1(s)|sx∈T}.

另外,對(duì)?s∈S1,令

下證

由定理6,對(duì)?q∈Q,s∈S1,滿足對(duì)?sx∈T,有(q,sx)∈I1,等價(jià)于對(duì)?x∈T(s),有

等價(jià)于

故

{q∈Q|?sx∈T,(q,sx)∈I1}=

T↑=B,

從而

再證

成立.對(duì)?s∈S1,存在T(s)?X1(s),滿足

令

等價(jià)于對(duì)?x∈T(s),有

等價(jià)于對(duì)sx∈T,有(q,sx)∈I1,故

從而

證畢

證明由定理5,只需再證

由定理3有

由定義18有

又由定理7,有

故

即

證畢

若對(duì)s∈S,滿足對(duì)?x∈X(s),sx都是可約簡(jiǎn)標(biāo)記技能,則s為一個(gè)可約簡(jiǎn)技能.

證明對(duì)s∈S,滿足對(duì)?x∈X(s),都有sx可約簡(jiǎn)標(biāo)記技能,則s?S1,故s∈S{S1}為一個(gè)可約簡(jiǎn)技能.

證畢

step 1 由

得到標(biāo)記技能背景(Q,SX,I).

step 2 對(duì)?sx∈SX,計(jì)算

{sx*|sx∈SX},A={[sx]|sx∈SX}.

step 3 在A中的每個(gè)元素[sx]中各取出一個(gè)代表元,組成一個(gè)新的標(biāo)記技能集SX′.

step 4 從{sx*|sx∈SX}找出{sx*|sx∈SX′},并計(jì)算

B= {[sx]|?sx∈SX′,|[sx]|>1}.

step 5 令C=?,E=?,F=?,R=?.

step 6 將{sx*|sx∈SX′}的sx*按照|sx*|從小到大排序,若|sx*|相等,則隨機(jī)排序.

step 7 對(duì)?sx∈SX′,若找到一個(gè)

成立,則C←C∪{sx}.

step 8 令D=SX′C.對(duì)?sx∈D,若[sx]∈B,則E←E∪[sx],否則F←F∪{sx}.

step 9 對(duì)E中的每個(gè)元素各取一個(gè)代表元進(jìn)行組合,所有可能的組合構(gòu)成一個(gè)集合族G.

step 10 對(duì)E′∈G,令

step 13 遍歷G中元素,重復(fù)step 10～step 12,可獲得所有的極小技能層模糊技能背景及其對(duì)應(yīng)的可約簡(jiǎn)技能層和可約簡(jiǎn)技能.

對(duì)于算法2,step 2～step 4的時(shí)間復(fù)雜度最大為O(|SX|),step 6～step 13的時(shí)間復(fù)雜度最大為O(|SX||G|),故算法2的時(shí)間復(fù)雜度最大為O(|SX||G|).

SX={sx|?s∈S,x∈W(s)且x≠∨W(s)}.

1)由

[sx]={ty∈SX|sx*=ty*},

可得

因此,標(biāo)記技能的所有等價(jià)類構(gòu)成的集合如下所示:

2)從A中每個(gè)元素中任取一個(gè)代表元,組成一個(gè)新的標(biāo)記技能集SX′.假設(shè)

3)由于

故

4)由于

故

為SX的可約簡(jiǎn)標(biāo)記技能集.

表3 極小標(biāo)記技能背景

表4 極小標(biāo)記技能背景

表5 極小技能層模糊技能背景

表6 極小技能層模糊技能背景

4 前級(jí)(后級(jí))簡(jiǎn)單必包空間的充要條件

第2節(jié)通過模糊技能概念格獲得簡(jiǎn)單閉包空間,第3節(jié)經(jīng)過技能層約簡(jiǎn)提高獲取簡(jiǎn)單閉包空間的效率,但將基本局部獨(dú)立模型應(yīng)用于前級(jí)簡(jiǎn)單閉包空間和后級(jí)簡(jiǎn)單閉包空間將呈現(xiàn)出不可識(shí)別的問題,導(dǎo)致無法評(píng)估個(gè)體的行為表現(xiàn)層次與真實(shí)認(rèn)知能力的一致性.因此,為了避免出現(xiàn)不可識(shí)別的問題,下面給出判斷模糊技能映射誘導(dǎo)前級(jí)(后級(jí))簡(jiǎn)單閉包空間的充要條件.在充要條件的前提下,只需判定模糊技能背景滿足某些條件,就可以確定誘導(dǎo)的簡(jiǎn)單閉包空間在某些問題中是否是前級(jí)的或后級(jí)的.

2)對(duì)?K?Q{q1,p},滿足對(duì)?s∈S,若

則

證明先證充分性.假設(shè)存在p∈Q{q1},對(duì)?s∈S,有

成立,則存在

使得

成立.另外,因?yàn)間(?)=?∈K,故

因此,有

?∪{q1}?K.

從而K在q1處不是前級(jí)的.故條件1)是必要的.對(duì)K?Q{q1,p},假設(shè)存在p∈Q{q1},使得存在

滿足對(duì)?s∈S,有

且對(duì)

存在s∈S,有

成立.另外,假設(shè)K?Q{q1,p}非空,且存在s∈S,有

K∪{q1} ?K.

從而K在q1處不是前級(jí)的.故條件2)是必要的.

再證必要性.假設(shè)K在q1∈Q處不是前級(jí)的,則存在K∈K且q1?K,使得

K∪{q1}?K

成立.因此,存在

有

且存在s∈S,有

因?yàn)閷?duì)?p∈Q{q1},存在s∈S,有

故存在

滿足

又因?yàn)?/p>

K∪{q1}?K,

由定理1可得,對(duì)

有

成立,并且存在s∈S,有

與條件2)矛盾.

證畢

注意到,在條件2)中,對(duì)q1∈Q,p∈Q{q1},滿足對(duì)?s∈S,有

成立的K是很多的,故為了更快地判定條件2)是否成立,對(duì)滿足條件2)的前提條件的那些K進(jìn)行限制.

不成立.

成立.

成立,故2)成立.

證畢

對(duì)q1∈Q,存在

p=q4∈Q{q1},

使得對(duì)?s∈S,有

成立,故不滿足條件1).故K在q1處不是前級(jí)的.

對(duì)q2∈Q,容易驗(yàn)證對(duì)?p∈Q{q2},都滿足條件1).下面對(duì)每個(gè)p∈Q{q2}逐個(gè)驗(yàn)證條件2).容易驗(yàn)證,當(dāng)p=q1和p=q3時(shí),不滿足條件2)的前提.對(duì)

p=q4∈Q{q2},

容易驗(yàn)證,對(duì)

?K?Q{q2,q4},

條件2)均成立.對(duì)

p=q5∈Q{q2},

存在

K={q4}?Q{q2,q5},

使得對(duì)?s∈S,有

成立.但存在s3∈S,有

成立,故不滿足條件2).因此,K在q2處不是前級(jí)的.

類似可驗(yàn)證K在q3,q4,q5處均不是前級(jí)的.

證明先證充分性.已知Q∈K,因?yàn)镵在問題q1∈Q處是后級(jí)的,故

Q{q1}∈K.

因此,存在

有

成立.但q1?Q{q1},所以存在s∈S,有

假設(shè)對(duì)?s∈S,存在p∈Q{q1},有

則存在s∈S,有

再證必要性.對(duì)?K∈K,滿足存在

有

下證K{q1}∈K,即證對(duì)

有

成立.先證

假設(shè){q1}?K,則

K{q1}=K.

因此,對(duì)?s∈S,有

故

從而

成立.假設(shè){q1}∈K,則對(duì)?q∈K{q1},滿足對(duì)?s∈S,有

綜上,有

成立.

證畢

對(duì)q1∈Q,存在s1,對(duì)?p∈Q{q1},滿足

故K在q1處是后級(jí)的.類似可驗(yàn)證K在q2,q3處均是后級(jí)的.對(duì)q4∈Q,不存在s∈S,使得對(duì)?p∈Q{q4},有

成立.故K在q4處不是后級(jí)的.類似,易得K在q5處不是后級(jí)的.

算法3獲取前級(jí)問題集和后級(jí)問題集

輸出前級(jí)問題集和后級(jí)問題集

step 1 令FGS=?.對(duì)每個(gè)q∈Q,執(zhí)行如下步驟.

step 1.1 對(duì)?p∈Q{q},如果不存在s∈S,滿足

則返回step 1,否則執(zhí)行step 1.2.

step 1.2 對(duì)每個(gè)p∈Q{q},執(zhí)行step 1.3.

成立,則

FGS←FGS∪{q},

否則返回step 1.

step 2 令BGS=?.

step 3 對(duì)?s∈S,遍歷Q中的所有問題q,若只存在唯一一個(gè)q,使得

成立,則

BGS←BGS∪{q}.

step 4 輸出前級(jí)問題集和后級(jí)問題集.

對(duì)于算法3,step 1的時(shí)間復(fù)雜度最大為

O(|Q|(|Q|-1)|S|),

step 3的時(shí)間復(fù)雜度最大為O(|Q||S|),故算法3的時(shí)間復(fù)雜度最大為

O(|Q|(|Q|-1)|S|).

5 數(shù)值實(shí)驗(yàn)及結(jié)果分析

本節(jié)在5個(gè)UCI數(shù)據(jù)上驗(yàn)證算法1～算法3的有效性.實(shí)驗(yàn)環(huán)境如下:Windows 10及Intel(R)Core(TM)i7-9700UCPU @3.00 GHz,16.0 GB內(nèi)存.數(shù)值實(shí)驗(yàn)所用軟件為Python 3.8.

5.1 實(shí)驗(yàn)數(shù)據(jù)集

對(duì)于標(biāo)準(zhǔn)化后的數(shù)據(jù)集,存在大部分?jǐn)?shù)據(jù)集技能對(duì)應(yīng)的熟練程度過小或過細(xì)的問題,導(dǎo)致生成知識(shí)結(jié)構(gòu)的過程過于繁雜,并且在實(shí)際教育背景中,對(duì)技能熟練程度劃分過小或過細(xì)會(huì)嚴(yán)格占用個(gè)體測(cè)試以及技能評(píng)估的時(shí)間.因此,為了更貼切KST的教育背景,將標(biāo)準(zhǔn)化后的信息值保留一位小數(shù),并根據(jù)不同的數(shù)據(jù)特點(diǎn),將Soybean、Stone Flakes、Daily、Fires數(shù)據(jù)集上分別小于等于0.4、0.6、0.6、0.5的信息值都替換成0,并使用

表示模糊技能背景中所有技能的技能層集的基數(shù)總和.數(shù)據(jù)預(yù)處理后的具體信息如表7所示.

表7 實(shí)驗(yàn)數(shù)據(jù)集

5.2 實(shí)驗(yàn)結(jié)果

為了簡(jiǎn)潔表示文獻(xiàn)[26]的算法,使用算法A表示文獻(xiàn)[26]中生成簡(jiǎn)單閉包空間的方法,使用算法B表示文獻(xiàn)[26]中保持簡(jiǎn)單閉包空間不變,獲取極小技能集M和冗余技能集R的方法(SR=M).注意到由算法B得到的冗余技能集與技能的順序有關(guān),所以冗余技能集不唯一.若要得到所有的冗余技能集,需要對(duì)整個(gè)技能集S進(jìn)行全排列,重復(fù)執(zhí)行算法B.考慮到算法對(duì)比的需要,對(duì)于算法B,本文不考慮對(duì)技能集S進(jìn)行全排列,只考慮技能集S的原始順序這一種情形,此時(shí)技能約簡(jiǎn)的結(jié)果是唯一的.

表8 算法2和算法B約簡(jiǎn)結(jié)果與運(yùn)行時(shí)間對(duì)比

注意到由算法2得到的可約簡(jiǎn)技能層模糊技能背景不是唯一的,故對(duì)應(yīng)的可約簡(jiǎn)技能層和可約簡(jiǎn)技能也不唯一.因此,表8的第2列只給出運(yùn)行算法2得到的第一個(gè)可約簡(jiǎn)技能層模糊技能背景對(duì)應(yīng)的可約簡(jiǎn)技能層和可約簡(jiǎn)技能.表中算法2的運(yùn)行時(shí)間是獲取所有可約簡(jiǎn)技能層模糊技能背景的時(shí)間.通過表8可以發(fā)現(xiàn),兩種算法的約簡(jiǎn)結(jié)果是不同的,并且算法2的運(yùn)行時(shí)間遠(yuǎn)小于算法B.算法B只對(duì)技能集S的原始順序執(zhí)行一次,由此說明算法2的有效性.

另外,對(duì)于算法B約簡(jiǎn)后得到的極小技能集,再次運(yùn)用算法A生成簡(jiǎn)單閉包空間K.所得結(jié)果如表9所示,其中,|K|表示簡(jiǎn)單閉包空間K中的知識(shí)狀態(tài)個(gè)數(shù),最后一行的求和表示對(duì)算法運(yùn)行時(shí)間的求和.

表9 約簡(jiǎn)前后獲取簡(jiǎn)單閉包空間的運(yùn)行時(shí)間

圖3 算法1和算法A的運(yùn)行時(shí)間隨|K|的變化

表10 簡(jiǎn)單閉包空間的前級(jí)(后級(jí))問題集

6 結(jié) 束 語

本文基于模糊形式概念分析研究模糊技能映射.首先,基于構(gòu)造的算子計(jì)算模糊技能概念格,通過外延集族獲得模糊技能映射在合取模型下誘導(dǎo)的簡(jiǎn)單閉包空間,通過內(nèi)涵集族獲得每個(gè)知識(shí)狀態(tài)對(duì)應(yīng)的最小技能熟練程度.再基于模糊技能背景,提出技能層約簡(jiǎn)的概念,使生成知識(shí)結(jié)構(gòu)的效率更高.然后,給出模糊技能映射誘導(dǎo)的簡(jiǎn)單閉包空間是前級(jí)和后級(jí)的充要條件.最后,在5個(gè)UCI數(shù)據(jù)集中驗(yàn)證本文算法的有效性.本文建立模糊形式概念分析與知識(shí)空間理論的一些聯(lián)系,為研究知識(shí)空間理論提供另一種途徑.今后將進(jìn)一步考慮模糊技能映射在其它模型(析取模型和能力模型)下的技能層約簡(jiǎn)以及尋找前級(jí)和后級(jí)知識(shí)結(jié)構(gòu)的充要條件.另外,后續(xù)研究將考慮模糊技能映射下的技能評(píng)估和路徑選擇問題.