概念格在查詢課程的系統中的應用

摘要:概念格是數據分析理論中的一種有力工具。針對查詢課程系統這類問題，利用概念間的相似度構造加權的概念格，從而給出一種方法來解決查詢過程中關鍵詞的輸入順序問題，并結合實例說明了這種方法的有效性。

關鍵詞:概念格;概念相似度;加權

中圖分類號:TP18文獻標識碼:A 文章編號:1009-3044(2009)25-7320-02

Details of the Curriculum in the Concept Lattice of the System

ZHANG Zhi-xing

(Hebei University School of Mathematics and Computer，Baoding 071000，China)

Abstract: Concept lattice is a powerful tool of data analysis theory. Account of this problem ofsearching curriculum system， using the similarity of the concept to construct the weighted concept lattice， a approach is presented to resolve the input sequence of words in the searching process， and the effectiveness of this approach is illustrated combined with an example.

Key words: concept lattice; similarity of the concept; weighted

概念格是由德國Wille教授首先提出的，它是形式概念分析理論中的核心數據結構，已經應用在眾多領域，如概念格在電子商務中的應用[1]。本文將給出概念格在查詢課程的系統中的一個簡單應用。比如說新學期開始，學生們總會查詢一下課程的安排情況，這時往往需要輸入一些關鍵詞，那么在輸入的過程中如何排列這些關鍵詞將可能會影響查詢的時間。

本文利用概念格，給出一種關鍵詞的排列順序，從而可以有效地提高效率。

1 概念格的相關知識

1.1 概念格的基本定義

本文中用到的有關概念格的定義來源于文獻[2-3]。

在形式概念分析中，形式背景通常被定義為一個三元組K=(G，M，I)，其中G為對象集，M為屬性集，I是G與M之間的一個二元關系即IG×M，對于g∈G，m∈M用gIm表示對象g具有屬性m。通常，一個形式背景可以直觀地使用一個交叉表格表示。

在形式背景K=(G，M，I)中，對于g∈G，定義{g}'={m∈M|gIm};對于m∈M，定義{m}'={g∈G|gIm}，從而對于AG，BM，有下式成立:

A'={m∈M|g∈A，gIm}={g}' B'={g∈G|m∈B，gIm}={m}'

對于AG及BM，元素對(A，B) 如果滿足條件:A'=B并且B'=A，則(A，B)稱為是一個形式概念(以下簡稱概念)，其中A稱為概念的外延，B稱為概念的內涵。形式背景K的所有概念構成的集合用L(K)表示。

對于(A1，B1)，(A2，B2)∈L(K)，定義(A1，B1)≤(A2，B2)<=>A1A2，不難證明“≤”是L(K)上的一個偏序關系。如果不存在(A3，B3)∈L(K)使得(A1，B1)≤(A3，B3)≤(A2，B2)成立，則(A1，B1)是(A2，B2)的直接子概念，(A2，B2)是(A1，B1)的直接父概念。事實上，(L(K)，≤)是一個完備格，通常稱其為形式背景K的概念格。

概念格可以用Hasse示圖來表示，其中Hasse示圖的點表示一個概念，兩點之間的連線表示這兩個概念之間存在直接父子關系。

1.2 概念格的構造算法

目前構造概念格的算法主要有漸進式算法和批處理算法。本文采用分層的概念格構造算法(見文獻[4])。

定義[4] 在概念格中，若概念(A，B)到格中最小元的最長極大鏈的長度為N，則稱(A，B)是第N層的格節點。

下面給出具體構造概念格的步驟。

Step 0 初始化i=1;

Step 1 對每一個g∈G，寫出所有的元素對(g，g')，構成集合S，轉step 2;

Step 2 若S中的元素對有相同屬性的，則把它們的對象求并，作為一個新的元素對放入S中，并且把其它和這個新元素對具有相同屬性的刪除，轉step 3;

Step 3 從S中找出所有g'極大的元素對，即作為第i層的概念，轉step 4;

Step 4 若S中沒有元素對，算法結束;否則，將S中剩余的元素對(X，Y)與第i層的概念(A，B)進行比較，若YB，則將(X∪A，Y)替代(X，Y)放入S中，轉step 5;

Step 5 將第i層的任兩個概念的外延求并，作為新的元素對放入S中，轉step 2;依次類推，求出概念格的所有概念;

Step 6 根據概念間的關系畫出Hasse示圖。

1.3 概念間的相似度

從直觀上說，概念的相似度是指兩個概念的形式相似程度。目前，關于概念相似度的具體度量方法有很多，如文獻[5]。

本文參照文獻[6]給出一種計算概念間相似度的方法。

設所有概念的個數為 ，將每個概念分別作為第一行，第一列構成一個表格形式。

對于概念(Ai，Bi)和(Aj，Bj)，記|Bi∩Bj|=hij，kij表示Bi與Bj不同的屬性個數。

若Bi=，或Bj=，則p=1;若Bi≠，則根據下面的情況計算概念的相似度:

1)hij值最大的對應的概念的p值最大，為T，其次為T-1，依此類推;

2)若有多個概念的具有相同的hij，則判斷kij，即kij越小的p的值越大;

3)若有多個概念的具有相同的kij，則按照概念外延的字典序，字典序小的p的值大。

顯然根據上述的計算方法可以得到概念相似度的表中第一行和第一列的值為1，對角線上除第一個位置外其它的值都為T。

2 概念格在查詢課程的系統中的應用

本節將用具體實例來說明如何利用概念格有效地查詢課程安排情況。

例如某學生要查詢課程名稱，上課日期和任課教師的情況，那么該學生如何輸入這三個關鍵詞?

下面給出解決這個問題的具體算法。

Step 1 把實際問題抽象成數學模型，即構造形式背景，設M={m1，m2，m3}={課程名稱，上課日期，任課教師}表示屬性的集合，G={1，2，3，4，5，6}={課程名稱，上課日期，任課教師，課程名稱上課日期，課程名稱任課教師，課程名稱上課日期任課教師}表示對象的集合，由G和M構成的形式背景如表1所示;

Step 2 按照1.2節中分層構造概念格的算法生成概念格并畫出Hasse示圖如圖1所示;

Step 3 將圖1中的概念標號，列出概念間的相似度表如表2所示;

Step 4 連結直接父概念與直接子概念的邊上的權是這兩個概念的相似度值，在表2中，把第一行看作是直接父概念，第一列看作是直接子概念，按照從“父”到“子”的順序查找概念的相似度，加權后的概念格如圖2所示;

Step 5 在加權的Hasse圖中找到所要查詢的概念，以此為起點從下往上遍歷概念格，要求選取權值和最小的路徑，并記錄下經過的每個概念，從而確定出關鍵詞的輸入順序。

比如某學生查詢課程名稱上課日期，根據上述算法，在圖2中找到概念⑤，按照從下往上的順序得到權值和最小的路徑，即③→①，從而該學生首先輸入上課日期，其次再輸入課程名稱。

在這個例子中我們只給出了三個關鍵詞，類似地可以進行更多個關鍵詞的輸入。

3 結束語

本文中給出的方法不僅可以用于查詢課程的系統中，而且可以解決一般化的需要對關鍵詞排列最優順序的問題中，有較廣泛的應用。

參考文獻:

[1] 左雄輝，糜仲春.概念格在電子商務中的應用[J].科技進步與對策，2005，141-142.

[2] B.A.Davey，H.A.Priestley.Introduction to lattice and order，2nd，edition[M].Cambridge University Press，2003.

[3] GanterB.，Willer. Formal concept analysis[M].Mathematical Fundations，Berling，Heidelberg:Springer-Verlag，1999.

[4] 龐智恒，何偉，樊磊，曹學磊.一種構造概念格的算法[J].中央民族大學學報(自然科學版)，2008，17(1):19-23.

[5] 智慧來，智東杰，劉宗田.基于概念格的概念相似度計算[J].計算機科學，2008，35(9):156-157.

[6] 肖升，陽西述.基于概念格中文信息最優檢索串判定算法[J].湖南師范大學自然科學學報，2006，29(2):35-38.