陳永平，楊思春

1.馬鞍山職業(yè)技術(shù)學(xué)院計(jì)算機(jī)系，安徽馬鞍山 243000

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

面向?qū)ο蟾拍罡竦膲嚎s

陳永平1，楊思春2

1.馬鞍山職業(yè)技術(shù)學(xué)院計(jì)算機(jī)系，安徽馬鞍山 243000

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

1 引言

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

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

概念格的壓縮由于概念格中的節(jié)點(diǎn)數(shù)量是指數(shù)級(jí)的，導(dǎo)致數(shù)據(jù)與概念格也變得十分復(fù)雜，所以有必要對(duì)概念格進(jìn)行壓縮，簡(jiǎn)化知識(shí)庫(kù)，從而可以快速地從復(fù)雜數(shù)據(jù)中進(jìn)行知識(shí)發(fā)現(xiàn)，做出高效的決策。文獻(xiàn)[6-7]分別利用SVD方法和模糊聚類方法對(duì)經(jīng)典概念格進(jìn)行壓縮，不能適用于面向?qū)ο蟾拍罡?；文獻(xiàn)[8]根據(jù)對(duì)象的相似度或者屬性的相似度來(lái)控制面向?qū)傩愿拍罡裰泄?jié)點(diǎn)的個(gè)數(shù)，以實(shí)現(xiàn)對(duì)面向?qū)傩愿拍罡竦膲嚎s。然而概念是由對(duì)象和屬性共同確定，僅考慮對(duì)象相似度或?qū)傩韵嗨贫榷疾荒苋娴胤从掣拍畹奶匦?，因此本文引入了概念間相似度的一種新的計(jì)算方法，由對(duì)象和屬性共同確定概念之間的相似程度，進(jìn)而產(chǎn)生概念鄰域，并根據(jù)概念間相似程度來(lái)控制概念鄰域的大小，從而控制面向?qū)ο蟾拍罡裰泄?jié)點(diǎn)的個(gè)數(shù)，實(shí)現(xiàn)面向?qū)ο蟾拍罡竦膲嚎s。與現(xiàn)有文獻(xiàn)的其他壓縮方法相比，本文提出的方法當(dāng)選取的參數(shù)值較小時(shí)，壓縮效果明顯。

2 預(yù)備知識(shí)

3 面向?qū)ο蟾拍罡竦膲嚎s

該定理表明，使用本文方法對(duì)面向?qū)ο蟾拍罡襁M(jìn)行壓縮后，不會(huì)產(chǎn)生新的概念節(jié)點(diǎn)，并且壓縮后的概念集包含于壓縮前的概念集中，即壓縮后的概念集為壓縮前的概念集的子集。

4 例子

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

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

由表1可以得到形式背景(G，M，R)中的關(guān)系R的集合共有19項(xiàng)，并分別令為：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)。這樣關(guān)系R={t1，t2，…，t19}。并通過(guò)計(jì)算得到表1的形式背景(G，M，R)的面向?qū)ο蟾拍罡馤S(G，M，R)，如圖1所示。

對(duì)于形式背景(G，M，R)，如表1所示，利用方法對(duì)面向?qū)ο蟾拍罡襁M(jìn)行壓縮，其中的α和β的取值為0.5。

圖1 LS(G，M，R)

步驟3利用本文方法（式（2））對(duì)面向?qū)ο蟾拍罡襁M(jìn)行壓縮，壓縮后的面向?qū)ο蟾拍罡袢鐖D2所示。

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

另外，本文還對(duì)參數(shù)γ=0.31和γ=0.80分別進(jìn)行計(jì)算，得到壓縮后的面向?qū)ο蟾拍罡穹謩e如圖3和圖4所示。

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

通過(guò)上述計(jì)算可以看出，γ取不同值，面向?qū)ο蟾拍罡竦膲嚎s效果不同，如果γ取值較小時(shí)，概念格的壓縮比較明顯，γ取值較大時(shí)，概念格的壓縮不是很明顯。因此，對(duì)于γ值的選取，要根據(jù)實(shí)際應(yīng)用和實(shí)際壓縮的需要，選取滿足要求的γ值，使壓縮后的面向?qū)ο蟾拍罡裥Ч顑?yōu)。

5 結(jié)束語(yǔ)

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

[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]宋笑雪，張文修，李紅.變精度對(duì)象概念格的構(gòu)造及其性質(zhì)[J].計(jì)算機(jī)科學(xué)，2010，37（12）：197-200.

[3]韓中華，馬斌，許可，等.基于譜系聚類的粗糙集數(shù)據(jù)挖掘預(yù)處理方法[J].計(jì)算機(jī)工程與應(yīng)用，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]魏玲，李強(qiáng).面向?qū)傩愿拍罡窕诟采w的壓縮[J].電子科技大學(xué)學(xué)報(bào)，2012，41（2）：299-304.

[9]姚廣，魏玲，王磊.合成背景的面向?qū)傩愿拍钌蒣J].西北大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，40（1）：1-4.

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

[11]王虹，萬(wàn)金鳳.協(xié)調(diào)決策形式背景的屬性約簡(jiǎn)[J].工程數(shù)學(xué)學(xué)報(bào)，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

概念格理論是知識(shí)處理與分析的一種有力工具，在知識(shí)發(fā)現(xiàn)和數(shù)據(jù)挖掘等眾多領(lǐng)域有著重要的應(yīng)用。引入了概念相似度新的計(jì)算方法，由對(duì)象和屬性共同確定概念之間的相似程度，進(jìn)而產(chǎn)生概念鄰域，并根據(jù)概念間相似程度來(lái)控制概念鄰域的大小，刪除不必要的節(jié)點(diǎn)，從而控制面向?qū)ο蟾拍罡裰泄?jié)點(diǎn)的個(gè)數(shù)，實(shí)現(xiàn)面向?qū)ο蟾拍罡竦膲嚎s和知識(shí)庫(kù)簡(jiǎn)化。示例表明，當(dāng)參數(shù)的值較小時(shí)，壓縮效果明顯。

形式背景；概念格；面向?qū)ο蟾拍罡?；相似度；鄰?/p>

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.

安徽省高校省級(jí)自然科學(xué)基金（No.KJ2010B223）；安徽省高校省級(jí)自然科學(xué)研究重點(diǎn)項(xiàng)目（No.KJ2011A048）。

陳永平（1969—），男，副教授，主要研究方向?yàn)槿斯ぶ悄艿?；楊思春，男，博士研究生，副教授，碩導(dǎo)，主要研究方向?yàn)槿斯ぶ悄埽匀徽Z(yǔ)言處理等。E-mail：cyp7222@sina.com

2013-03-28

2013-06-13

1002-8331（2013）19-0119-04

◎圖形圖像處理◎