基于閉包系統劃分的概念格并行構造算法

[摘 要] 隨著處理的形式背景的增大，概念格的時空復雜度也會隨著急劇增大。研究新的方法和手段來構造概念格，是概念格技術應用于大型復雜數據系統的前提，提高其構造效率的一種有效途徑是利用高性能并行計算機和網絡并行計算的能力，因此概念格的并行構造算法已成為眾多學者的一個新的研究方向。概念格的并行構造思想就是根據不同的原理，采用分治策略，通過對形式背景的拆分，形成分布存儲的多個子背景，然后構造相應的子概念格，再由子概念格的合并得到所需的概念格。目前建格算法的分布處理研究主要有形式背景的并置和疊置以及形式背景的折疊搜索子空間劃分兩種方法，本文在總結研究這兩種方法的基礎上，基于偏序集上閉包系統分解的思想，對提出的閉包系統劃分為多個子閉包系統的判定定理進行了證明，使閉包系統的分解既不會產生冗余信息，也不會使信息丟失，并把所提出的判定定理用于概念格的并行處理，提出了一個新的基于閉包劃分的概念格并行生成算法——Para-Pruning算法。通過實驗，利用隨機生成的數據集同經典NextClosure算法進行比較分析，驗證了新算法的正確性和有效性。

[關鍵詞] 概念格;并行構造算法;閉包系統

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2009 . 21 . 006

[中圖分類號]TP393 [文獻標識碼]A[文章編號]1673 - 0194(2009)21 - 0020- 05

1引 言

概念格也稱為Galois格，是形式概念分析理論中的核心數據結構，它利用二元關系建立一種概念間的層次關系，是進行數據分析和規則提取的有效工具[1]。隨著研究深入，形式概念分析越來越多地被應用到數據挖掘、信息檢索、軟件工程等方面，已經成為當前計算機科學領域的一個熱門研究課題。由于概念格自身的完備性，構造概念格的時間復雜度一直是影響形式概念分析應用的主要因素。隨著處理的形式背景的增大，構造概念格的時空復雜度也會隨之急劇增加。提高其構造效率的一種有效途徑是利用高性能并行計算機和網絡并行計算的能力，概念格的分布處理或并行處理采用的思想都是分治策略，當前建格算法的分布處理研究主要有形式背景的并置和疊置以及形式背景的折疊搜索子空間劃分兩種方法[2]，這兩類概念格的分布處理模型都是分治策略應用的很好的例子。但進一步的研究發現，概念格并置與疊置模型要求概念格的類型比較嚴格，即所能計算的概念格是一種特殊的概念格，而折疊子空間劃分過于機械，過多地依賴于劃分參數DP，不能很好地解決特殊概念格的劃分[3]。本文也采用分治策略，提出了一種新的基于閉包劃分的概念格并行生成算法——Para-Pruning算法。

2基本定義

定義1 設K = (G，M，I)為一形式背景，?坌M1∈M，定義|M1′|為M′中對象的個數，?坌G1∈G，定義|G1′|為G′ 中屬性的個數。

定義2 設K = (G，M，I)為一形式背景，S為K上的概念集合，定義C0 = (M′M)，C1 = (G，G′)，且|M′| = 0，|G′| = 0，定義Ct = {C0，C1｝。

定義3 設K = (C，M，I)為一形式背景，定義運算↑g，滿足↑g = {gi∈G|gi′?哿g′｝。

設K = (G，M，I)為一形式背景，Kg和Kg是由K分解包含g與不包含g的兩個子背景，滿足Kg = (G1，g′，G1 × g′∩I)，其中 ，G1 = {g1|g1′∩g′≠?準，g1∈G｝，Kg = (G\\↑g，M2，G\\↑g × M2∩I)。其中，M2 = {mi|mi′∩(G\\↑g)≠?準，mi∈M｝。

定義4 設F(I)是形式背景K = (G，M，I)對象G 上的閉包系統，g為∨-Prime元素，?坌A，B∈F(I)，g?埸(A∪B)，滿足g?埸(A∪B)″。

定義5 設F(I)是形式背景K = (G，M，I)對象 G上的閉包系統，定義:

(1)Fg(I)為形式背景Kg = (G1，g′，G1 × g′∩I)對象G1上的閉包系統

(2)Fg′(I)為Fg = (G\\↑g，M2，G\\↑g× M2∩I)對象G\\↑g 上的閉包系統:

(3)Fg(I)= F(I)\\Fg(I)。

定理1 設K = (G，M，I)為一形式背景，定義F(I)為背景K的外延的閉包系統，g為∨-Prime元素，滿足:

(1)|F(I)| ≤1;

(2)F(I) = Fg(I)∪Fg(I)，Fg(I)和Fg(I)分別為背景Kg和Kg的外延的閉包系統。

此定理說明，如果g為∨-Prime元素，則Fg(I)=Fg′。

定理2 設K = (G，M，I)為一形式背景，X∈Fg′(I)\\Fg(I)，?坌Y∈Fg(I)， 滿足X?奐Y，Y∈Fg′(I)、Fg(I)。

證明:略[4]。

定理3 設K = (C，M，I)為一形式背景，g∈G是∨-Prime元素當且僅當?堝g|g∈G滿足g′ = G\\↑g。

證明:略[4]。

3Para-Pruning算法的描述

Para-Pruning算法是基于對搜索空間劃分及縮減來求解概念的，與已有的分布處理模型不同的是，Para-Pruning算法的劃分是基于閉包系統的劃分，其原理是把一個閉包系統劃分為多個子閉包系統分別求出概念集后，然后合并得出原閉包系統所對應的概念集。

命題1 設K = (C，M，I)為一形式背景，g∈G是 ∨-Prime元素，則?坌A∈Fg(I)，?堝m∈M\\g′，滿足A\\↑g?哿m′。

證明:在背景K = (C，M，I)中，若A\\↑g = ?準，即則背景K1 = (G\\↑g，g′，G\\↑g × g′∩I)和背景K2 = (↑g，M\\g′，↑g × M\\g′∩I)，有|F(Ii)| = 0，i，j∈{1，2｝，滿足定義5和定理1，所以g∈G是∨-Prime元素;若A\\↑g ≠ ?準，設A\\↑g?埸m′，A\\↑g?哿G\\↑g，即在背景K2中有概念(A\\↑g，(A\\↑g)′)存在，則在Fg(K)中，有元素A\\↑g存在，在Fg(K)中，有元素(A′\\↑g)″= A存在，有概念(A′\\↑g)″，(A′\\↑g)′)= (A，(A′\\↑g)′)存在，即F(K)?奐Fg(K)∪F (K)，|Fg(K)∪Fg(K)\\F(K)| ≠ 0，矛盾，所以原假設錯誤，g∈G是 ∨-Prime，得證。

命題2 設K = (G，M，I)為一形式背景，g∈G是 ∨-Prime元素，則?坌A∈Fg(I)，?堝B∈Fg(I)，(A\\↑g)″?哿B。

證明:很明顯，可以由命題1得出。

命題3設K = (G，M，I)為一形式背景，g∈G是 ∨-Prime元素，則?坌A∈g′，滿足(m′\\↑g)′?芫g。

證明:若(m′\\↑g)′?哿g′，則(m′\\↑g)″?勐g″，(m′\\↑g)″∈Fg(I)，g″∈Fg(I)，即Fg(I)∩Fg(I)≠?準，與原命題矛盾，假設錯誤，得證。

命題4 設K = (G，M，I)為一形式背景，g∈G是∨-Prime，?坌m∈g′，則?堝mi∈M\\g′，m′\\↑g?哿mi。

證明:很明顯，可以由命題1得出。

命題5 設K = (G，M，I)為一形式背景，g∈G是非∨-Prime元素，則?堝m∈g′，m′\\↑g\\mi′≠?準，其中mi∈M\\↑g。

證明:很明顯，可以由命題1得出。

根據上面介紹的Para-Pruning算法的基本定義和原理，可以看出每個搜索空間是相互獨立的，并且每個子搜索空間都對應一個閉包系統，所以可以派生不同的進程分別處理每個子搜索空間。Para-Pruning算法首先將原形式背景轉化為有序形式背景，按照排序后背景的特點，判斷對象集合中的特殊對象是否為∨-Prime元素，對搜索空間進行劃分為相互獨立的子閉包系統，根據所給定Depth值的大小是否進行更進一步的劃分，最后在每個子空間內用批處理或者漸進式構造算法[1] [6]進行概念的計算。

對∨-Prime元素的判定，在文獻[4]和文獻[5]中，Alain Gely和G.Markowsky提出，依據是g′ = G\\↑g(定理3)，但經進一步的研究發現，滿足∨-Prime條件的元素并不僅僅滿足條件g′ = G\\↑g，通過對命題1的證明，定理3實際上是命題1的一個充分條件，這樣，就為找出更多的∨-Prime元素提供了理論依據。

命題6Para-Pruning算法的預處理Sort(K)是必要的。

證明:對原形式背景的排序，實際上在對象集合中的對象g定義了一個字典序，把每個屬性所具有的對象在該字典序下排列，使排序后的背景有明顯的“階梯”狀，這樣，可以很方便地判斷那些↑g集合中的元素，即兩個階梯間的元素{g|g∈↑g｝，為后續的計算提供方便。

Para-Pruingn算法的偽代碼如下:

算法1:Para_Pruning(K，d) //Para_Pruning主函數

輸入:K = (C，M，I)，d，Depth，//初始背景及相關參數

輸出:K，A′，//劃分后子背景的集合和所有概念內涵

Begin

Ifd ≤ Depth

Sort(K) //基于屬性m字典序的排列，m∈M

K =DeComposition(K，d)

For EachKg∈K

Para_Pruning(Kg，d + 1)

Else

Prun_GeneratingClosedSets(K)

End If

End

算法2:DeComposition(K，d)//初始背景的劃分

輸入:K = (G，M，I) //Sort后的有序背景

輸出:K//有序背景K的各個劃分Kg∈K

Begin

While(g ≤ G)

Choose g ≤ G such thatg is ∨-Prime

Kg = (G1，g′，G1 × g′∩I)

K≡K∪{Kg｝

K = Kg= (G\\↑g，M2，G\\↑g × M2∩I)

g = Pre(g)// 的前一個“階梯”元素

End While

End

根據閉包系統的性質可以證明，子閉包系統對應的概念集合的并集與原閉包系統所對應的概念集合相同。Para-Pruning算法不會造成信息的丟失。Para-Pruning算法的主要計算時間在于劃分完成后在每個子背景求解概念的時間，由于在計算中避免了空間的搜索，所以其時間復雜度要小于經典的NextClosue算法。

下面給出了一個具體的例子來描述算法的運算過程，假設深度設Depth = 1。圖1中表a給出一個形式背景K = (G，M，I)，?菖表示所對應的對象和屬性具有關系I，即gIm。用所給出的算法計算背景a的概念描述如下。表b是該背景的排序，c、d、e和f分別是排序后背景的劃分，每個背景所對應的概念集合分別為:

背景a:Sa = {(?準，Ma)，(7，bdf)，(78，bf)，(789，b)，(4，chi)，(459，hi)，(9，behi)，(45689，i)，(8，befgi)，(89，bei)，(1，aeg)，(12689，e)，(689，ei)，(1238，g)，(128，eg)，(Ga，?準)｝，|Sa| = 16。

背景c:Sc = {(1，aeg)，(12689，e)，(128，eg)，(1238，g)，(Gc，?準)｝，|Sc| = 5。

背景d:Sd = {(?準，Mf)，(7，bdf)，(78，bf)，(789，b)，(4，chi)，(459，hi)，(9，behi)，(45689，i)，(8，befgi)，(89，bei)，(689，ei)，(Gd，?準)｝，|Sa| = 12。

背景e:Se = {(4，chi)，(459，hi)，(45689，i)｝，|Se| = 3。

背景f:Sf = {(?準，Mf)，(7，bdf)，(78，bf)，(789，b)，(9，behi)，(8，befgi)，(89，bei)，(689，ei)，(Gf，?準)｝，|Sf|=9。

很明顯，有Sa \\Cta = (Sc\\Ctc)∪(Se \\Cte)∪Sf\\Ctf，而且(Si \\Cti)∩(Sj \\Ctj) = ?準，i，j∈{c，e，f｝，i≠j。

如果按照Alain Gely和G.Markowsky所提出定理3，此例是不能進行閉包分解的，然而，本例卻劃分了3個子閉包系統，由此也可說明定理3是命題1的一個充分條件。

4實驗分析

為了驗證Para-Pruning算法的優越性，給出了此算法與經典NextClosure算法的比較分析。在Pentium 4 2.4，256M 內存，Windows XP操作系統，使用隨機生成的數據集，利用VB.net 2005實現了Para-Pruning算法和NextClosure算法(參見表1、表2)。測試數據采用150組隨機生成的樣本數據，為提高數據的真實性，對隨機生成的每10組樣本數據取均值。生成隨機數據集時，考慮了3個參數:對象數|G|、屬性數|M|、以及用于反映背景稠密程度的參數|d|(每個對象具有的平均屬性數)，用來控制隨機數據集的大小和稀疏程度。實驗結果見圖3~圖5。圖中橫坐標表示對象數，縱坐標為表示時間(或

|d|)，曲線上的點表示完成概念計算所用的時間。

表1|M| = 100，|d| = 5

圖3|M| = 100，|d| = 25

圖4|M| = 100，|d| = 15

圖5|G| = 100，|M| = 100

實驗結果表明:①Para-Pruning算法構造出的節點數與NextClosure算法構造出的節點數是相同的，驗證了Para-Pruning算法的正確性;②Para-Pruning算法比NextClosure算法效率高，說明把基于背景 K上的子閉包系統劃分為多個子閉包系統，進而分別求概念可以明顯地提高運算效率;③上述實驗結果是在一臺機器上實現的，如果進行分布計算，效果會更加明顯;④形式背景不同，Para-Pruning算法的效率是不同的，背景稀疏的背景效果更為明顯。⑤圖5中的Sort處理過程所耗時間遠低于概念的求解時間，說明了Para-Pruning算法中排序的時間對算法的時間復雜度影響不大。

5結 論

在研究現有的兩種并行建格算法基礎上，提出了一種基于閉包系統劃分的概念格并行生成算法Para-Pruning算法。該算法將屬性集合的冪集視為閉包的搜索空間，按是否包含一個對象(或屬性)將整個搜索空間進行劃分，并識別出那些能生成正規子閉包的子搜索空間，再進一步遞歸劃分，從而有效提高搜索效率;在計算閉包過程中保存一些必要的中間結果，用來提高閉包運算速度。在隨機生成的數據集和真實數據集上進行的實驗測試表明，本算法的時間性能要優于NextClosure算法。算法還有很多值得研究和改進的地方，如對子閉包系統劃分的更為有效的測試及背景劃分的深度等方面的問題，將在未來的工作中做進一步的研究。

主要參考文獻

[1]Bernhard Ganter， Rudolf Wille. Formal Concept Analysis: Mathematical Foundations[M]. Berlin， Springer-Verlag， 1999.

[2]Fu H， Nguifo EM. A parallel algorithm to generate formal concepts for large data[C]// Eklund P， ed. Proc. of the 2nd Int’l Conf. on Formal Concept Analysis (ICFCA 2004). LNCS 2961， Berlin: Springer-Verlag， 2004:394-401.

[3]李云，劉宗田，陳峻，等.多概念格的橫向合并算法[J].電子學報，2004，32 (11):1849-1854.

[4]Alain Gély.A Generic Algorithm for Generating Closed Sets of a Binary Relation[C]//B Ganter，R Godin Eds. Formal Concept Analysis:3rd Int’l Conf. ICFCA 2005 ，LNAI 3403，Springer，2005:223-234.

[5]G Markowsky.Primes，Irreducibles and Extremal Lattices[J].Order，1992，9(3):265-290.

[6]R Godin， et al. Incremental Concept Formation Algorithm Based on Galois (concept) Lattices[J]. Computational Intelligence，1995， 11 (2) : 246-267.

[7]Jiawei Han， Micheline Kamber. Data Mining: Concepts and Techniques[M].2nd Edition. Beijing: China Machine Press， 2006.

[8]Pang-Ning Tan， Michael Steinbach and Vipin Kumar. 數據挖掘導論[M]. 范明，等，譯. 北京:人民郵電出版社， 2006.

A Parallel Constructing Algorithm Based on Dividing of Closure System forConcept Lattice

MA Chi 1，2

(1.School of Economics and Management ，University of Science and Technology Beijing， Beijing 100083;

2.School of Software Engineering， University of Science and Technology Liaoning， Liaoning Anshan 114051)

Abstract: With the increasing of the context， the time complexity and the space complexity of the construction of concept lattice will be dramatically increased accordingly. The new constructing of concept lattice has been paid much attention because it is the premise for being used in a large and complicated data system. The high-performance parallel computer and network parallel computing technology are normally used to enhance the structure efficiency. However， the parallel constructing of concept lattice should adopt the dividing and conquering method by considering different structuring principles to divide the context into sub-contexts. The overall concept lattice is composed of a series of sub-concept lattices each of which is structured from its related sub-context. So far， there are mainly two structuring methods， collocation and overlay of context and folding search space partition of context. This paper introduces a new parallel structuring method based on the idea of the dividing of the closure system of poset to divide the whole closure system into sub-closure system. The method can eliminate the redundancy and loss of information during the process of the dividing of the closure system. The experiment result showed the accuracy and validity of the present method by comparing with the NextClosure algorithm.

Key words: Concept Lattice; Parallel Constructing Algorithm; Closure System

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文