面向對象概念格的壓縮

陳永平，楊思春

1.馬鞍山職業(yè)技術學院計算機系，安徽馬鞍山 243000

2.安徽工業(yè)大學計算機學院，安徽馬鞍山 243002

面向對象概念格的壓縮

陳永平1，楊思春2

1.馬鞍山職業(yè)技術學院計算機系，安徽馬鞍山 243000

2.安徽工業(yè)大學計算機學院，安徽馬鞍山 243002

1 引言

概念格理論，又稱形式概念分析，是由德國數(shù)學家Wille于1982年提出的[1]，是進行數(shù)據(jù)分析的一種有效工具，該理論是根據(jù)數(shù)據(jù)集中對象和屬性間的二元關系建立的一種概念層次結構，體現(xiàn)了概念間的泛化和特化的關系。目前，該理論已應用到數(shù)據(jù)決策分析、信息檢索、數(shù)據(jù)挖掘、軟件工程和知識發(fā)現(xiàn)等領域。粗糙集理論由Pawlak提出的，它是一種處理模糊和不確定知識的計算工具，已被成功地應用于決策分析、數(shù)據(jù)挖掘等領域。

雖然，粗糙集理論和形式概念分析為我們提供了兩種不同的數(shù)據(jù)分析方法，它們以不同的角度研究數(shù)據(jù)集合中所隱含的知識；但是概念格理論和粗糙集理論又是相互關聯(lián)、相互補充，在研究方法上相互借鑒、相互融合，為數(shù)據(jù)分析提供了新的研究方法[2-3]。Gediga、Dntsch[4]和Yao[5]等把粗糙集理論引入到概念格理論中，從而定義了面向對象概念格和面向屬性概念格，并且進一步研究了這兩種概念格之間的關系。

概念格的壓縮由于概念格中的節(jié)點數(shù)量是指數(shù)級的，導致數(shù)據(jù)與概念格也變得十分復雜，所以有必要對概念格進行壓縮，簡化知識庫，從而可以快速地從復雜數(shù)據(jù)中進行知識發(fā)現(xiàn)，做出高效的決策。文獻[6-7]分別利用SVD方法和模糊聚類方法對經典概念格進行壓縮，不能適用于面向對象概念格；文獻[8]根據(jù)對象的相似度或者屬性的相似度來控制面向屬性概念格中節(jié)點的個數(shù)，以實現(xiàn)對面向屬性概念格的壓縮。然而概念是由對象和屬性共同確定，僅考慮對象相似度或屬性相似度都不能全面地反映概念的特性，因此本文引入了概念間相似度的一種新的計算方法，由對象和屬性共同確定概念之間的相似程度，進而產生概念鄰域，并根據(jù)概念間相似程度來控制概念鄰域的大小，從而控制面向對象概念格中節(jié)點的個數(shù)，實現(xiàn)面向對象概念格的壓縮。與現(xiàn)有文獻的其他壓縮方法相比，本文提出的方法當選取的參數(shù)值較小時，壓縮效果明顯。

2 預備知識

3 面向對象概念格的壓縮

該定理表明，使用本文方法對面向對象概念格進行壓縮后，不會產生新的概念節(jié)點，并且壓縮后的概念集包含于壓縮前的概念集中，即壓縮后的概念集為壓縮前的概念集的子集。

4 例子

設(G，M，R)為形式背景，對象集G={1，2，3，4，5，6}，屬性集M={a，b，c，d，e，f，h}，其中(n，m)∈R時用1表示，(n，m)?R用0表示，如表1所示。

表1 形式背景(G，M，R)

由表1可以得到形式背景(G，M，R)中的關系R的集合共有19項，并分別令為：t1=(1，a)，t2=(1，c)，t3=(1，d)，t4=(1，e)，t5=(1，f)，t6=(2，a)，t7=(2，c)，t8=(2，f)，t9=(3，b)，t10=(3，e)，t11=(4，b)，t12=(4，e)，t13=(4，f)，t14=(4，h)，t15=(5，a)，t16=(6，a)，t17=(6，b)，t18=(6，e)，t19=(6，f)。這樣關系R={t1，t2，…，t19}。并通過計算得到表1的形式背景(G，M，R)的面向對象概念格LS(G，M，R)，如圖1所示。

對于形式背景(G，M，R)，如表1所示，利用方法對面向對象概念格進行壓縮，其中的α和β的取值為0.5。

圖1 LS(G，M，R)

步驟3利用本文方法（式（2））對面向對象概念格進行壓縮，壓縮后的面向對象概念格如圖2所示。

圖2 γ=0.5時的LS0(G，M，R)

另外，本文還對參數(shù)γ=0.31和γ=0.80分別進行計算，得到壓縮后的面向對象概念格分別如圖3和圖4所示。

圖4 γ=0.80時的LS0(G，M，R)

通過上述計算可以看出，γ取不同值，面向對象概念格的壓縮效果不同，如果γ取值較小時，概念格的壓縮比較明顯，γ取值較大時，概念格的壓縮不是很明顯。因此，對于γ值的選取，要根據(jù)實際應用和實際壓縮的需要，選取滿足要求的γ值，使壓縮后的面向對象概念格效果最優(yōu)。

5 結束語

概念格理論是知識處理與分析的一種有力工具，在知識發(fā)現(xiàn)和數(shù)據(jù)挖掘等眾多領域有著重要的應用。本文引入了概念間相似度的新的計算方法，由對象和屬性共同確定概念之間的相似程度，進而產生概念鄰域，并根據(jù)概念間相似程度來控制概念鄰域的大小，刪除不必要的節(jié)點，以得到控制面向對象概念格中節(jié)點的個數(shù)，實現(xiàn)了面向對象概念格的壓縮和知識庫簡化。與現(xiàn)有的其他壓縮方法相比，本文提出的方法中當參數(shù)γ值較小時，壓縮效果明顯。后續(xù)研究，將對面向對象概念格壓縮的應用以及參數(shù)α、β、γ取值進行探討。

[1]Wille R.Restructuring lattice theory：an approach based on hierarchies of concepts[M]//Rival I.Ordered Sets.Dordrecht-Boston：Reidel，1982：445-470.

[2]宋笑雪，張文修，李紅.變精度對象概念格的構造及其性質[J].計算機科學，2010，37（12）：197-200.

[3]韓中華，馬斌，許可，等.基于譜系聚類的粗糙集數(shù)據(jù)挖掘預處理方法[J].計算機工程與應用，2008，44（2）：194-196.

[4]Gediga G，Dntsch I.Modal style operators in qualitative data analysis[C]//Proceedings of the IEEE International Conference on Data Mining，2002：155-162.

[5]Yao Y Y.A comparative study of formal concept analysis and rough set theory in data analysis[C]//Proceedings of 3rd International Conference（RSCTC’04），2004：59-68.

[6]Cheung K S K，Vogel D.Complexity reduction in lattice based information retrieval[J].Information Retrieval，2005，8：285-299.

[7]Kumar A C，Srinivs S.Concept lattice reduction using fuzzy K-meansclustering[J].ExpertSystemswithApplications，2010，37（3）：2696-2704.

[8]魏玲，李強.面向屬性概念格基于覆蓋的壓縮[J].電子科技大學學報，2012，41（2）：299-304.

[9]姚廣，魏玲，王磊.合成背景的面向屬性概念生成[J].西北大學學報：自然科學版，2010，40（1）：1-4.

[10]王虹，張文修.基于概念格的形式背景的知識約簡[J].模式識別與人工智能，2005，18（6）：641-645.

[11]王虹，萬金鳳.協(xié)調決策形式背景的屬性約簡[J].工程數(shù)學學報，2006，23（3）：455-460.

[12]Zhu W.Relationship between generalized rough sets based on binary relation and covering[J].Information Seienees，2009，179：210-225.

CHEN Yongping1,YANG Sichun2

1.Department of Computer Science,Ma’anshan Technical College,Ma’anshan,Anhui 243000,China
2.School of Computer Science,Anhui University of Technology,Ma’anshan,Anhui 243002,China

Concept lattice theory is a powerful tool for processing and analysis of knowledge,knowledge discovery and data mining,and other important applications.A new method of similarity calculation of concepts is introduced.Objects and properties are both used to determine the similarity of concepts,generate the concept neighborhood and control its size according to the similarity degree of concepts.And then,it removes unnecessary nodes,to control the number of nodes in the object-oriented concepts,realization of object-oriented concepts simplify the compression and the knowledge base.The examples show that the compressing of object-oriented concept lattice is more effect when parameter values are smaller.

formal context;concept lattice;object-oriented concept lattice;similarity degree;neighborhood

概念格理論是知識處理與分析的一種有力工具，在知識發(fā)現(xiàn)和數(shù)據(jù)挖掘等眾多領域有著重要的應用。引入了概念相似度新的計算方法，由對象和屬性共同確定概念之間的相似程度，進而產生概念鄰域，并根據(jù)概念間相似程度來控制概念鄰域的大小，刪除不必要的節(jié)點，從而控制面向對象概念格中節(jié)點的個數(shù)，實現(xiàn)面向對象概念格的壓縮和知識庫簡化。示例表明，當參數(shù)的值較小時，壓縮效果明顯。

形式背景；概念格；面向對象概念格；相似度；鄰居

A

TP18

10.3778/j.issn.1002-8331.1303-0451

CHEN Yongping,YANG Sichun.Reduction of object-oriented concept lattices.Computer Engineering and Applications, 2013,49（19）：119-122.

安徽省高校省級自然科學基金（No.KJ2010B223）；安徽省高校省級自然科學研究重點項目（No.KJ2011A048）。

陳永平（1969—），男，副教授，主要研究方向為人工智能等；楊思春，男，博士研究生，副教授，碩導，主要研究方向為人工智能，自然語言處理等。E-mail：cyp7222@sina.com

2013-03-28

2013-06-13

1002-8331（2013）19-0119-04

◎圖形圖像處理◎