張嘉德,金子涵

(河北大學 數(shù)學與信息科學學院,河北 保定 071000)

0 引言

隨著網(wǎng)絡上數(shù)據(jù)獲取、數(shù)據(jù)通信和數(shù)據(jù)存儲技術(shù)的迅猛發(fā)展,網(wǎng)絡中積累了大量的圖書信息數(shù)據(jù)。這些數(shù)據(jù)中不僅包含著許多有價值的信息,也包含著大量的冗余信息。面對規(guī)模日益龐大的數(shù)據(jù),如何去粗求精從數(shù)據(jù)中有效地提取有價值的信息成為一個具有重大現(xiàn)實意義的問題。在這種背景下,機器學習、數(shù)據(jù)挖掘等技術(shù)得到了廣泛應用,大量的知識發(fā)現(xiàn)方法應運而生。

形式概念分析(Formal Concept Analysis) 由德國數(shù)學家R.Wille[1]提出,作為一種針對知識發(fā)現(xiàn)的有力工具,已被廣泛應用在各個領(lǐng)域,如人工智能、軟件工程、信息檢索、關(guān)聯(lián)規(guī)則挖掘等[2-3]。形式概念(下文簡稱“概念”)是一個有序?qū)?外延,內(nèi)涵),其中外延是一些對象的集合,描述了概念所涵蓋的對象；內(nèi)涵是一些屬性的集合,描述了概念的所有特征。在所有概念組成的集合上定義了一個泛化—例化的偏序關(guān)系,使之成為完備格,稱之為概念格。

經(jīng)典FCA只能處理確定性數(shù)據(jù),但是現(xiàn)實世界的數(shù)據(jù)往往具有不確定性,如何從不精確、不一致、不完備的網(wǎng)絡圖書數(shù)據(jù)中獲取人們需要的知識,是廣大學者一直關(guān)注的問題[4]。模糊集理論可以有效地處理不確定性數(shù)據(jù),且FCA與模糊集理論具有很強的互補性,將FCA與模糊集理論結(jié)合起來研究,得到模糊形式概念分析可以更加有效地表達和處理不確定性知識[4]。

西班牙學者Torra[5]于2009年提出了猶豫模糊集(HFS),它是模糊集的一種推廣。猶豫模糊集使用了一些可能的值而不是某一值去刻畫隸屬度,所以能夠反映決策者的猶豫不確定性,因而比其他模糊集理論更實用和更合適。此后,蔡麗娜[6]根據(jù)HFSs的性質(zhì),將區(qū)間值運用到猶豫模糊集,給出了區(qū)間值猶豫模糊集(IVHFS)的定義。本文主要以區(qū)間值猶豫模糊集(模糊集的一種拓展形式)為主要工具來處理不確定性數(shù)據(jù),借助Godin算法[7]討論概念格的生成,以期為網(wǎng)絡圖書信息的提取提供一種可行的分類方法。

1 預備知識

1.1 區(qū)間值猶豫模糊集

定義1.1.[6]設X為一個非空分明集合,單位閉區(qū)間[0,1]上的全體閉區(qū)間為[I],則稱映射?A:X→[I],x→?A(x)為X上的區(qū)間值模糊集,X上的全體區(qū)間值模糊集記為IF(X)。

定義1.2.[6]設X為一非空集合,則關(guān)于X的區(qū)間值猶豫模糊集為:

1.2 概念格

定義1.4[1](1)K=(G,M,I)被稱為形式背景,其中G表示非空的有限對象集合,M表示非空的有限屬性集合,I是從G到M的一個關(guān)系,即I?G×M, 且?x∈G,?a∈M,(x,y)∈I表示“對象x具有屬性a”。

(2)對于X?G及B?M, 定義:

f(X)={m∈M|?x∈X,(x,m)∈I},g(B)={x∈X|?b∈B,(x,b)∈I}。

如果X,B滿足f(X)=B,g(B)=X, 則稱二元組(X,B)是一個概念,X是概念(X,B)的外延,B是概念(X,B)的內(nèi)涵。由K=(G,M,I)生成的所有概念組成的集合,記為β(G,M,I)。

(3)任取兩個概念(X,B)與(Y,C),如果X?Y(等價于B?C),記為(X,B) ≤ (Y,D), 并稱(X,B) 是(Y,C)的子概念,或稱 (Y,C)是(X,B)的父概念 。所有概念按著偏序關(guān)系“?”構(gòu)造成一個完備的概念格,記為(β(O,P,I), ≤),一般用Hasse 圖表示。

2 基于區(qū)間值猶豫模糊形式背景的概念格的構(gòu)造方法

下面主要定義區(qū)間值猶豫模糊形式背景,并給出相關(guān)算法。

定義2.1.K=(G,M,V,)被稱為區(qū)間值猶豫模糊形式背景,當且僅當G為有限對象組成的非空集合,M表示有限屬性組成的非空集合,V表示所有猶豫模糊元可能取值的區(qū)間值集合,模糊關(guān)系是從G×M到V的一個映射,即

事實上,這里所討論的概念格的構(gòu)造方法是建立在區(qū)間值猶豫模糊集和概念格的基礎之上的。具體如下,我們首先將區(qū)間值猶豫模糊背景轉(zhuǎn)化為經(jīng)典形式背景,進而通過經(jīng)典概念格的構(gòu)造方法,得到全部概念信息。算法框架如圖1所示。

圖1 算法框架

算法步驟具體如下:

Step1. 對于區(qū)間值猶豫模糊形式背景所對應的表格中的每一個單元格里的區(qū)間集合(即區(qū)間值猶豫模糊元),計算每個區(qū)間值的左右端點值的平均值,由此將區(qū)間值猶豫模糊形式背景轉(zhuǎn)化為猶豫模糊形式背景。

Step2. 將猶豫模糊背景所對應的每一個單元格的值,計算平均值,從而可將猶豫模糊形式背景可轉(zhuǎn)換為模糊形式背景。

Step3.對應于每一屬性,設置信度閾值。對于每一個對象g所在行的單元格的值,將低于相應置信度閾值的值設置為零,表示該對象不具有相應屬性；否則,設置為1,表示該對象具有此屬性。執(zhí)行完此步驟,可得到一個經(jīng)典實形式背景。

Step4. 簡化經(jīng)典實形式背景。相同的行(或列)認為是等價的,即將等價的行和列刪除,得到凈化的經(jīng)典形式背景。

Step5. 對于經(jīng)典形式背景,采用經(jīng)典概念格的Godin增量算法,生成所有概念節(jié)點,得到初始的概念格。

Step6. 將刪除的對象和屬性添加到概念格中,并繪制Hasse圖。

3 算法在圖書信息提取中的應用

下面將新給出的概念格構(gòu)造方法應用于圖書信息提取,試驗結(jié)果證明這種方法是行之有效的。

現(xiàn)從一個網(wǎng)絡圖書網(wǎng)站,搜集了與5本書(g1,g2,g3,g4,g5)相關(guān)的、來自于21位讀者的評分信息。對于這21位讀者,其中25歲(含25歲)以下7人,25歲至35歲(含35歲)7人,35歲至55歲7人。已知這個圖書網(wǎng)站有自己的一套評分系統(tǒng),評分范圍為5個評分等級:五星,四星,三星,二星,一星,分別記作m1,m2,m3,m4,m5。注意:這里分別對這3類人的評分信息進行統(tǒng)計,評分值以3個區(qū)間值形式呈現(xiàn)。

事實上,所得數(shù)據(jù)(見表1)實為一區(qū)間值猶豫模糊形式背景K=(G,M,V,),其中

表1 區(qū)間值猶豫模糊形式背景

運行我們所提出的算法,可得全部概念如下:

第0層:D0: ({g1,g2,g3},{})；

第1層:D1: ({g1,g2},{m1,m5}),D2: ({g1,g3},{m3})；

第2層: D3: ({g1},{m1,m3,m5}),D4: ({g2},{m1,m4,m5}), D5:( {g3},{m2,m3})

第3層:D6: ({},{m1,m2,m3,m4,m5})；

所構(gòu)造的概念格如圖2所示:

圖2 應用所提算法生成的概念格

分析所得概念格信息,可為網(wǎng)站和讀者提供有價值的信息。例如,通過概念D2:( {g1,g3},{m3})

我們可知,對于g1,g3這兩本書,讀者評分可能均為三星。對于概念D3: ({g1},{m1,m3,m5}), 可知讀者對g1這本書,評分可能是五星、三星或一星3種情形。注意:閾值選擇不同,得到的概念格可能不同,即閾值對概念格有關(guān)鍵作用。因而,在實際應用中,為了反映更真實的概念格,應該謹慎選擇閾值。

4 結(jié)語

本文提供了一種基于區(qū)間值猶豫模糊形式背景的概念格提取方法,并將之應用于網(wǎng)絡圖書信息的提取,實例證明該方法是可行的,并能為讀者提供有價值的建議。下一步工作可提供一種不依賴于Godin算法的、生成的概念是區(qū)間值猶豫模糊概念的、有效的信息提取方法。