PŘÍRODOVĚDECKÁ FAKULTA UNIVERZITY PALACKÉHO KATEDRA INFORMATIKY
DIPLOMOVÁ PRÁCE
Rozpoznávání závislostí ve vágních datech
2006
Zdeněk Horák
Místopřísežně prohlašuji, že jsem celou práci včetně příloh vypracoval samostatně.
Výsledky této práce byly dle zadání uvolněny pod licencí GNU GPL, jejíž text je uveden jako příloha A.
21. srpna 2006
Zdeněk Horák
i
Anotace Hlavním cílem této diplomové práce byla efektivní implementace algoritmů pro generování atributových implikací a některých jejich specifických skupin z tabulkových dat s fuzzy atributy (konkrétně jde o neredundantní báze při použití globalizace jako zdůrazňovače pravdy). Součástí tohoto textu je také zjednodušený teoretický úvod právě do problematiky atributových implikací ve fuzzy prostředí.
ii
Děkuji doc. RNDr. Vilému Vychodilovi, Ph.D., za jeho trpělivost a způsob, jakým mě vedl při tvorbě této práce.
iii
Obsah 1. Úvod
1
2. Atributové implikace 2.1. Neformální úvod . . . . . . . . . . . 2.2. Teoretické základy . . . . . . . . . . 2.2.1. Základy fuzzy logiky . . . . . 2.2.2. Formální konceptuální analýza 2.2.3. Fuzzy atributové implikace . . 2.3. Shrnutí . . . . . . . . . . . . . . . . . 3. Algoritmy 3.1. GMinBasis . . . . . 3.2. GRedMinBasis . . 3.3. Fuzzy NextClosure 3.4. GLinClosure . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
4. Aplikace 4.1. Struktura . . . . . . . . . . . . 4.2. Ovládání aplikace . . . . . . . . 4.3. Formát vstupních dat . . . . . . 4.4. Generátor náhodných kontextů 4.5. Kompilace ze zdrojového kódu . 4.6. Vývojové nástroje . . . . . . . . 4.7. Poznámky k implementaci . . . 4.8. Srovnání výkonnosti . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . .
2 2 3 3 4 5 8
. . . .
9 9 10 11 13
. . . . . . . .
15 15 16 18 18 20 21 21 23
Závěr
27
Conclusions
28
Reference
29
A. GNU General Public License
31
i
Seznam tabulek 1. 2. 3.
Informace o planetách naší sluneční soustavy. . . . . . . . . . . . Srovnání výkonnosti algoritmů a jejich implementací . . . . . . . Výkonnost podle použitých datových struktur . . . . . . . . . . .
ii
2 25 26
Seznam algoritmů 1 2 3 4
GMinBasis . . GRedMinBasis NextClosure . GLinClosure .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
iii
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
9 11 12 14
1.
Úvod
Analýza tabulkových dat zejména v posledních letech nabývá nejen v informatické komunitě na důležitosti. Původní – a dnes již poměrně dobře rozpracované – přístupy uvažovaly pouze tabulky s binárními daty. Řádky tabulek zpravidla reprezentovaly objekty, sloupce odpovídaly analyzovaným atributům. Vztah mezi objekty a atributy byl tedy čistě bivalentní, buď objekt atribut měl nebo ne. To je samozřejmě značné omezení, protože atributy objektů bývají často složitější. Existují sice způsoby, jak i tyto složitější atributy převést na binární data (např. pomocí škálování, viz [5]), ovšem při jejich použití se situace rychle komplikuje, často se stává až nepřehlednou. Řešení ovšem nabízí přístup, který stojí spíše na počátku své cesty, i když základy jsou již pevně usazeny – jde o využití fuzzy logiky. V následující kapitole jsou představeny atributové implikace jako nástroj analýzy tabulkových dat a to jak po stránce neformální, tak i čistě teoretické, včetně základů fuzzy logiky a formální konceptuální analýzy. Na konci kapitoly je uvedeno krátké shrnutí, jako pokus o ucelený náhled na problematiku z pohledu počítačového zpracování. Třetí kapitola popisuje algoritmy pro výpočet neredundantních bází atributových implikací z datových tabulek s fuzzy atributy při použití globalizace jako zdůrazňovače pravdy (viz dále). Efektivní implementace těchto algoritmů je součástí této diplomové práce. Kapitola čtvrtá je věnována právě popisu této implementace a zejména vyvinutému balíčku aplikací. Uživatelé zde mohou najít adresy ke stažení balíčku a návod na kompilaci a používání aplikace. V této kapitole naleznete také několik poznámek k implementaci, určených zejména pro programátory. Podstatnou součástí této práce je i srovnání výkonnosti vytvořené aplikace a jejích variant s původním kódem. V souladu se zadáním diplomové práce byly zdrojové kódy aplikace uvolněny pod GNU GPL licencí, jejíž text je vložen jako příloha A.
1
2. 2.1.
Atributové implikace Neformální úvod
Atributovou implikací rozumíme výraz A ⇒ B, kde A a B jsou množiny atributů. Tuto implikaci můžeme číst jako: „Pokud má objekt všechny atributy z množiny A, pak má i všechny atributy z množiny B.ÿ V této práci se omezíme na atributové implikace nad tabulkovými daty, avšak ve fuzzy prostředí. Ukažme si to na následujícím, dnes již snad klasickém, příkladu (viz [3]).
Merkur Venuše Země Mars Jupiter Saturn Uran Neptun Pluto
malá 1.0 1.0 1.0 1.0 0.0 0.0 0.5 0.5 1.0
velká 0.0 0.0 0.0 0.0 1.0 1.0 0.5 0.5 0.0
dále Slunci 0.0 0.0 0.0 0.5 1.0 1.0 1.0 1.0 1.0
blíže Slunci 1.0 1.0 1.0 1.0 0.5 0.5 0.0 0.0 0.0
Tabulka 1. Informace o planetách naší sluneční soustavy. Tato tabulka zaznamenává vlastnosti planet naší sluneční soustavy. Jednotlivé planety můžeme chápat jako objekty, sloupce odpovídají atributům, které mohou objekty mít. Hodnota z tabulky udává, v jakém stupni (tedy nakolik) má objekt na daném řádku atribut v daném sloupci. Stupeň 1 vyjadřuje, že objekt má atribut zcela (tedy je např. malý či blízký Slunci), zatímco stupeň 0 udává, že objekt atribut nemá vůbec. Z tabulky můžeme „vyčístÿ několik atributových implikací, např. planety, které jsou velké ve stupni 0.5, jsou dále od Slunce. Všimněme si, že obráceně toto tvrzení platit nemusí (a v našem případě také neplatí). Takovýchto tvrzení bychom však mohli v naší tabulce najít velké množství. Ne všechna by byla zajímavá – některá by byla triviální a některá by se významově překrývala. Budeme se tedy snažit získat takovou množinu atributových implikací, která popisuje všechny vztahy platící v tabulce, ale neobsahuje žádné implikace navíc. Tato práce se zabývá efektivní (zejména co do rychlosti výpočtu) implementací algoritmu pro generování výše popsaných množin atributových implikací (při určitých omezeních) z datových tabulek. 2
2.2.
Teoretické základy
V této podkapitole popíšeme teorii, na které atributové implikace ve fuzzy prostředí stojí. Použité věty jsou uváděny pouze přehledově, bez důkazů. Ty je možné najít s pomocí seznamu literatury. Předpokládá se, že čtenář disponuje základními znalostmi z algebry (např. viz [11]) a matematické logiky (např. [16]). 2.2.1.
Základy fuzzy logiky
Následující informace naleznete přehledově například v [3]. Oproti dvěma pravdivostním hodnotám v klasické logice se ve fuzzy logice používá škála pravdivostních hodnot (označme L). Jako základní strukturu pravdivostních hodnot ve fuzzy logice používáme tzv. úplný residuovaný svaz, tedy algebru L = hL, ∨, ∧, ⊗, →, 0, 1i, kde hL, ∨, ∧, 0, 1i je úplný svaz (s 0 a 1 jako nejmenším, resp. největším prvkem), hL, ⊗, 1i je komutativní monoid a h⊗, →i je adjungovaný pár binárních operací. Podmínka adjunkce stanoví: a ≤ b → c, právě když a ⊗ b ≤ c,
(1)
pro lib. a, b, c ∈ L. Jednotlivé prvky a ∈ L nazýváme pravdivostními stupni. Typickou volbou L bývá konečný podřetězec [0, 1] a binární operace ∨ a ∧ odpovídající maximu a minimu. Operace ⊗ se volí jako zleva spojitá t-norma1 , operace → je jednoznačně určena právě podmínkou adjunkce. Obvyklé dvojice jsou: • Lukasiewiczova a ⊗ b = max(a + b − 1, 0) a → b = min(1 − a + b, 0)
(2) (3)
a ⊗ b = min(a, b) ½ 1 pokud a ≤ b a→b = b jinak
(4)
a⊗b = a·b ½ 1 pokud a ≤ b a→b = b jinak a
(6)
• Gödelova
(5)
• Goguenova
(7)
1 tedy komutativní a asociativní binární operace na L, která je neklesající v obou argumentech a pro lib. x ∈ L splňuje x ⊗ 0 = 0 a x ⊗ 1 = 1
3
Spolu s úplným residuovaným svazem L často uvažujeme ještě tzv. zdůrazňovače pravdy (angl. truth-stressing hedges, více v [2] a [14]), jež realizují spojku „být velmi pravdivýÿ a značíme je ∗ . Jde o unární operace splňující: a∗ (a → b)∗ a∗∗ 1∗
≤ ≤ = =
a, a∗ → b∗ , a∗ , 1.
(8) (9) (10) (11)
pro lib. a, b ∈ L. Hraničními případy zdůrazňovačů pravdy jsou vždy: (i) identita a∗ = a, (ii) globalizace
½ ∗
a =
1 pro a = 1, 0 jinak.
Na struktuře pravdivostních hodnot L můžete definovat pojem L-množiny (fuzzy množiny) A na universu U jako zobrazení A : U → L, přičemž A(u) budeme interpretovat jako „stupeň, ve kterém u patří do Aÿ. Pomocí LU budeme označovat soubor všech L-množin na universu U . Obdobně můžeme definovat i fuzzy relaci I mezi množinami X a Y jako zobrazení I : X × Y → L, kde I(x, y) je pravdivostní stupeň výroku „x je v relaci s yÿ, pro x ∈ X, y ∈ Y . Ve fuzzy prostředí lze pojem podmnožiny rozšířit na stupeň, v jakém je jedna množina podmnožinou druhé. Pro A, B ∈ LU jej definujme jako ^ S (A, B) = (A (u) → B(u)) . (12) u∈U
Budeme psát A ⊆ B, právě když S (A, B) = 1. 2.2.2.
Formální konceptuální analýza
Formální konceptuální analýza (FCA) je jednou z metod analýzy objektatributových dat. Pro naše účely si představíme několik základních termínů z této disciplíny. Formální fuzzy kontext je trojice hX, Y, Ii, kde X je množina objektů, Y množina atributů a I je fuzzy relace mezi X a Y , tedy I : X × Y → L. Formální fuzzy kontext odpovídá již dříve představené datové tabulce s fuzzy atributy – objektu přiřazuje stupeň, ve kterém objekt má daný atribut.
4
Pro fuzzy množiny A ∈ LX , B ∈ LY (tedy A je fuzzy množina objektů, B je fuzzy množina atributů) definujme fuzzy množinu atributů A↑ ∈ LY a fuzzy množinu objektů B ↓ ∈ LX jako A↑ (y) =
^
(A(x)∗X → I(x, y))
(13)
(B(y)∗Y → I(x, y))
(14)
x∈X ↓
B (x) =
^
y∈Y
Symboly ↑ a ↓ lze uvažovat jako zobrazení ↑ : LX → LY , ↓ : LY → LX , indukované fuzzy kontextem. Operace ∗X a ∗Y jsou již dříve uvedené zdůrazňovače pravdy, k jejich úloze se vrátíme níže. Formální fuzzy koncept je dvojice hA, Bi, A ∈ LX , B ∈ LY , taková, že ↑ A = B a B ↓ = A. V tomto případě budeme A nazývat extentem konceptu, B jeho intentem. Označme: © ª B(X ∗X , Y ∗Y , I) = hA, Bi ∈ LX × LY | A↑ = B, B ↓ = A , (15) a pro hA1 , B1 i, hA2 , B2 i ∈ B(X ∗ , Y ∗ , I) definujme binární relaci ≤: hA1 , B1 i ≤ hA2 , B2 i, právě když A1 ⊆ A2 (nebo B2 ⊆ B1 ).
(16)
Pak hB(X ∗X , Y ∗Y , I), ≤i nazýváme fuzzy konceptuální svaz indukovaný kontextem hX, Y, Ii. Prvky hA, Bi tohoto svazu jsou právě všechny formální fuzzy koncepty nacházející se ve vstupních datech. Volbou zdůrazňovačů pravdy ∗X a ∗Y můžeme plynule (viz [2]) ovlivňovat význam pojmů na nich založených, tedy např. množství konceptů získaných z formálního kontextu. V zápisu budeme symbol ∗ vynechávat, pokud použijeme identitu, tedy např. B(X ∗X , Y, I), ještě jednodušeji B(X ∗ , Y, I). 2.2.3.
Fuzzy atributové implikace
Fuzzy atributová implikace (nad množinou atributů Y ) je výraz A ⇒ B, kde A, B ∈ LY (A a B jsou fuzzy množiny atributů). Tento výraz můžeme číst jako: „Pokud je (velmi) pravdivé, že objekt má všechny atributy z A, pak má i všechny atributy z B.ÿ Vše detailněji v [4] a [6]. Stupeň platnosti atributové implikace A ⇒ B v L-množině M ∈ LY značíme kA ⇒ BkM ∈ L a definujeme jej jako kA ⇒ BkM = S(A, M )∗ → S(B, M ).
(17)
Pokud za M zvolíme fuzzy množinu atributů objektu x, pak kA ⇒ BkM ∈ L je pravdivostní stupeň, ve kterém implikace A ⇒ B platí pro daný objekt (resp. řádek datové tabulky s fuzzy atributy). 5
Stupeň platnosti atributové implikace v M ⊆ LY (tedy v systému fuzzy množin, např. ve skupině řádků datové tabulky) značíme jako kA ⇒ BkM ∈ L a definujeme: ^ kA ⇒ BkM = kA ⇒ BkM . (18) M ∈M
Zaveďme si pro daný kontext hX, Y, Ii fuzzy množinu atributů Ix ∈ LY (pro x ∈ X) takovou, že Ix (y) = I(x, y), pro všechna y ∈ Y . Ix tedy odpovídá atributům, které má objekt x uvedeny v datové tabulce formálního kontextu. Stupeň kA ⇒ BkhX,Y,I i ∈ L, ve kterém implikace A ⇒ B platí v kontextu hX, Y, Ii, definujeme jako kA ⇒ BkhX,Y,Ii = kA ⇒ BkM , kde M = {Ix | x ∈ X}. Označme množinu všech intentů konceptů svazu B(X ∗ , Y, I) jako © ª Int(X ∗ , Y, I) = B ∈ LY | hA, Bi ∈ B(X ∗ , Y, I) pro lib. A .
(19)
(20)
Z definice formálního fuzzy konceptu vidíme, že M ∈ LY je intentem nějakého konceptu© svazu B(X ∗ , Y, I), ª právě když M = M ↓↑ , tedy dostáváme, že ∗ Y ↓↑ Int(X , Y, I) = M ∈ L | M = M . Věta. Nechť hX, Y, Ii je datová tabulka s fuzzy atributy. Pak pro všechny fuzzy atributové implikace A ⇒ B platí kA ⇒ BkhX,Y,Ii = kA ⇒ BkInt(X ∗ ,Y,I) = S(B, A↓↑ ).
(21)
Mějme dánu množinu fuzzy atributových implikací T nad datovou tabulkou s fuzzy atributy hX, Y, Ii. Množinu M ∈ LY budeme nazývat modelem T , pokud kA ⇒ BkM = 1 pro všechny implikace A ⇒ B ∈ T . Množinu všech modelů (množiny atributových implikací T ) budeme označovat jako © ª Mod(T ) = M ∈ LY | M je modelem T . (22) Stupeň kA ⇒ BkT ∈ L, ve kterém A ⇒ B sémanticky vyplývá z množiny implikací T , definujeme jako kA ⇒ BkT = kA ⇒ BkMod(T ) .
(23)
Množinu fuzzy atributových implikací T budeme nazývat úplnou (v hX, Y, Ii), pokud kA ⇒ BkT = kA ⇒ BkhX,Y,Ii pro všechny implikace A ⇒ B. Je-li T úplná a žádná vlastní podmnožina T již úplná není, budeme T nazývat neredundantní báze (vztaženo k dané datové tabulce s fuzzy atributy hX, Y, Ii). 6
Věta. Množina fuzzy Mod(T ) = Int(X ∗ , Y, I).
atributových
implikací
je
úplná,
právě
když
Jako systém pseudo-intentů kontextu hX, Y, Ii budeme označovat systém fuzzy množin atributů P ⊆ LY , pokud pro všechny P ∈ LY platí: P ∈ P, Prvky tohoto ložme ∗ ZT ∗ Z T0 ∗ Z Tn
P 6= P ↓↑ a kQ ⇒ Q↓↑ kP = 1 pro všechny Q ∈ P takové, že Q 6= P.
právě když
systému budeme nazývat pseudo-intenty. Pro Z ∈ LY poS = Z ∪ {B ⊗ S(A, Z)∗ | A ⇒ B ∈ T a A 6= Z} , = Z, ∗ ∗ = (Z T n−1 )T , pro n ≥ 1.
a definujme operátor clT ∗ : LY → LY : clT ∗ (Z) =
∞ [
∗
Z Tn
(24)
n=0
Věta. Pro systém pseudo-intentů P a množinu © ª T = P ⇒ P ↓↑ | P ∈ P
(25)
platí (i) T je neredundantní báze. Navíc, je-li (ii) Je-li
∗
∗
globalizace, pak je T minimální.
globalizace, pak clT ∗ je L∗ -uzávěrový operátor2 a platí © ª clT ∗ (Z) | Z ∈ LY = P ∪ Int(X ∗ , Y, I).
(26)
Tuto množinu budeme nazývat Guigues-Duquennova báze (GD). Minimální neredundantní báze ovšem nejsou obecně určeny jednoznačně. Uvažme tzv. kmenovou bázi (angl. stem basis), definovanou jako T ◦ = {P ⇒ P ◦ | P ∈ P}, kde ½ 0 pokud P ↓↑ (y) = P (y), ◦ P (y) = ↓↑ P (y) jinak. Tato báze obsahuje stejné množství implikací jako původní GD báze, avšak pravé strany těchto implikací mohou být jednodušší, pro člověka přehlednější, aniž by báze ztratila něco na své informační hodnotě. 2
zobrazení clT ∗ : LY → LY splňující
(i) Z ⊆ clT ∗ (Z), pro všechna Z ∈ LY , (ii) S(Z1 , Z2 )∗ ≤ S(clT ∗ (Z1 ), clT ∗ (Z2 ))∗ , pro všechna Z1 , Z2 ∈ LY , (iii) clT ∗ (Z) = clT ∗ (clT ∗ (Z)), pro všechna Z ∈ LY .
7
2.3.
Shrnutí
Naším cílem je analýza tzv. objekt-atributových dat, přičemž uvažujeme objekty s fuzzy atributy. Varianta s binárními atributy je rozvíjena již poměrně dlouhou dobu v podobě klasické formální konceptuální analýzy. Máme k dispozici aparát fuzzy logiky, který již disponuje všemi klíčovými prvky, takže můžeme využívat představených pojmů jako jsou fuzzy formální kontext, koncept, atd. Z pohledu úlohy shlukování je pro nás klíčový fuzzy konceptuální svaz skládající se z jednotlivých konceptů – tedy vzájemně jednoznačných dvojic extentů a intentů. Chceme-li hledat v datech zajímavé závislosti, je pro nás výhodnější pohled atributových implikací. Abychom však omezili velké množství atributových implikací, které se v datech běžně nachází, hledáme takovou množinu implikací, která je tak malá, „ jak jen to jdeÿ, avšak popisuje všechny závislosti, které se v datech nacházejí. Pro tyto účely se hodí výše představené pseudo-intenty a jejich báze. V předchozí části jsme si uvedli konstrukci, která za jistých podmínek (tedy přesněji při použití globalizace jako zdůrazňovače pravdy) vede k uzávěrovému operátoru, jehož pevné body3 jsou právě všechny intenty a pseudo-intenty daného fuzzy formálního kontextu. V následující kapitole si představíme výpočetně schůdný způsob, jak uvedené pevné body nalézt. Předtím si však pro větší názornost uvedeme množinu atributových implikací, která tvoří zmíněnou Guigues-Duquennovu bázi pro data z Tabulky 1. { malá,
0.5
/velká, vzdálená { velká, vzdálená { vzdálená, 0.5/blízká { 0.5/malá, 0.5/blízká { 0.5/velká { blízká
} } } } } }
⇒ ⇒ ⇒ ⇒ ⇒ ⇒
{ { { { { {
malá, velká, blízká, vzdálená } , velká, vzdálená, 0.5/blízká } , velká, vzdálená, 0.5/blízká } , malá, blízká } , 0.5 /velká, vzdálená } , malá, blízká } .
Zápis „0.5/maláÿ znamená, že daná množina obsahuje atribut „maláÿ ve stupni 0.5. Tam, kde je stupeň vynechán, obsahuje množina atribut zcela – tedy ve stupni 1. Pro větší přehlednost byly názvy některých atributů zkráceny. K této bázi můžeme uvést také – z pohledu člověka jistě srozumitelnější – kmenovou bázi. { malá,
0.5
/velká, vzdálená { velká, vzdálená { vzdálená, 0.5/blízká { 0.5/malá, 0.5/blízká { 0.5/velká { blízká
3
} } } } } }
body operátoru clT ∗ pro něž platí Z = clT ∗ (Z)
8
⇒ ⇒ ⇒ ⇒ ⇒ ⇒
{ { { { { {
velká, blízká } , /blízká } , velká } , malá, blízká } , vzdálená } , malá } .
0.5
3.
Algoritmy
V následující části uvedeme několik algoritmů pro generování bází atributových implikací z formálních fuzzy kontextů. V tomto dokumentu naleznete jen jejich pseudokód, konkrétní implementace je součástí zdrojových kódů přiložených k diplomové práci. Při použití odpovídajících struktur jsou všechny následující algoritmy schopny degenerovat do klasického bivalentního případu. Pro úplnost nutno dodat, že ve zbytku dokumentu se omezíme na konečnou množinu atributů a lineárně uspořádanou konečnou množinu pravdivostních hodnot L. Tato omezení však nejsou – vzhledem k praktickému charakteru algoritmů – nijak limitující.
3.1.
GMinBasis
Tento základní algoritmus (podrobněji např. v [8]) vychází z toho, že máme k dispozici funkci NextClosure, která nám pro fuzzy množinu atributů a uzávěrový operátor vrátí lexikálně nejmenší pevný bod uzávěrového operátoru, který je však striktně větší než daná množina. Teď již jen stačí začít s prázdnou množinou a postupně získávat jednotlivé pevné body uzávěrového operátoru a u každého z nich jednoduchým testem rozlišit, zda se jedná o intent (B = B ↓↑ ) či pseudo-intent (B 6= B ↓↑ ). Vše, tedy i včetně celkové složitosti algoritmu, stojí na zmíněné funkci pro výpočet uzávěru. K tomuto účelu můžeme použít fuzzy verzi Ganterova algoritmu NextClosure (původní verze viz [12], fuzzy rozšíření viz [1]), který si rozebereme v další podkapitole.
1 2 3 4 5 6 7 8 9 10 11 12 13
Vstup: Formální fuzzy kontext hX, Y, Ii Výstup: Minimální neredundantní báze atributových implikací, množina intentů B := ∅ if B = B ↓↑ then add B to INTENTS else add B ⇒ B ↓↑ to THEORY while B 6= Y do B := NextClosure(B, clTHEORY ) if B = B ↓↑ then add B to INTENTS else add B ⇒ B ↓↑ to THEORY end return THEORY, INTENTS Algoritmus 1: GMinBasis
9
3.2.
GRedMinBasis
Tento algoritmus (viz [10], [8]) je pouze modifikací algoritmu předchozího. Již zmíněná kmenová báze představuje prostředek, jak redukovat pravé strany atributových implikací báze, aby se staly čitelnějšími. Takzvaná Supp-reducibilita představuje prostředek k redukci levých stran implikací. Uveďme si ji nejprve teoreticky. V dalším textu budeme pro fuzzy množinu atributů A označovat [A]T jako nejmenší model v Mod(T ) obsahující A. Operaci ª uvažujeme jako funkci: a ª b = a ⊗ ((a → b)∗ → 0) , která se při užití globalizace jako zdůrazňovače pravdy ½ 0 pro a ≤ b, aªb= a jinak.
∗
zjednoduší na
Jako sem(T ) označujeme množinu fuzzy atributových implikací, které sémanticky vyplývají z T . Definice. Nechť T je množina fuzzy atributových implikací, A ⇒ B a C ⇒ D jsou dvě různé implikace z množiny T. Pokud (i) D ⊆ A, (ii) C ⊆ [A]T −{A⇒B} , a (iii) |(A ª D) ∪ C| ≤ |A|, pak A ⇒ B nazveme Supp-reducibilní pomocí implikace C ⇒ D v množině implikací T . Definice. Nechť T je množina fuzzy atributových implikací, pokud v ní neexistují žádné implikace A ⇒ B a C ⇒ D takové, že A ⇒ B je Supp-reducibilní C ⇒ D v T, pak množinu T nazveme Supp-redukovanou. Věta. Pro každou množinu atributových implikací T existuje Supp-redukovaná množina T 0 taková, že sem(T ) = sem(T 0 ) a platí |T 0 | ≤ |T |. Důkaz předchozí věty (viz [10]) nám dává návod, jak Supp-redukovanou bázi získat. Můžeme totiž nejprve vypočítat minimální neredundantní bázi (například pomocí předchozího algoritmu) a poté ji postupně redukovat nalézáním Suppreducibilních dvojic. Bohužel je tento postup značně výpočetně náročný. Ovšem vzhledem k tomu, že funkce NextClosure nám vrací pevné body uzávěrového operátoru v lexikografickém uspořádání, je možné redukci implikací zapojit přímo do předchozího algoritmu. Získáváme tedy následující postup. 10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
Vstup: Formální fuzzy kontext Výstup: Supp-redukovaná minimální neredundantní báze, množina intentů B := ∅ if B = B ↓↑ then add B to INTENTS else add B ⇒ B ↓↑ to THEORY REDUCEDTHEORY := THEORY while B 6= Y do B := NextClosure(B, clTHEORY ) if B = B ↓↑ then add B to INTENTS else add B ⇒ B ↓↑ to THEORY BR := B repeat REDUCED := true foreach Q ⇒ R ∈ REDUCEDTHEORY do if R ⊆ BR and | (BR ª R) ∪ Q |<| BR | then BR := (BR ª R) ∪ Q REDUCED := f alse end until REDUCED = true add BR ⇒ B ↓↑ to REDUCEDTHEORY end return REDUCEDTHEORY, INTENTS Algoritmus 2: GRedMinBasis
3.3.
Fuzzy NextClosure
Nyní si rozebereme zmiňovanou funkci NextClosure, která nám pro fuzzy množinu atributů a uzávěr vrátí lexikálně nejmenší pevný bod uzávěrového operátoru, který je však striktně větší než daná množina atributů. Z hlediska celkové výpočetní náročnosti je důležité téma výpočtu uzávěru, proto jej necháme na později a nyní si uvedeme základní kostru algoritmu. Bližší informace naleznete v [1]. Mějme fuzzy formální kontext hX, Y, Ii, jednotlivé atributy očíslujme Y = {y1 , . . . , yn }. Pro fuzzy množiny atributů A, B ∈ LY a index i ∈ {1, . . . , n} položme A
právě když
A(yj ) = B(yj ) pro ∀j ∈ {1, . . . , n} , takové, že j < i a A(yi ) < B(yi ),
a definujme relaci (odpovídající tzv. lexikografickému uspořádání): A < B právě když A
11
Pro fuzzy množinu A ⊆ LY , index i ∈ {1, . . . , n} a pravdivostní stupeň k ∈ L definujme operaci: © ª ¡ © ª¢ A ⊕ k/i = clT ∗ (A ∩ {1, . . . , i − 1}) ∪ k/i . Věta. Nejmenší pevný bod (uzávěrového operátoru clT ∗ ) B + větší než B ∈ LY (vzhledem k představenému uspořádání <) obdržíme jako © ª B + = B ⊕ k/i , © ª kde i ∈ {1, . . . , n} je největší a k ∈ L nejmenší pro které platí B
1 2 3 4 5 6 7 8 9 10 11 12 13
Vstup: Fuzzy množina atributů B, uzávěrový operátor clT ∗ , množina pravdivostních hodnot L = (k1 , . . . , km ) Výstup: Lexikálně nejmenší pevný bod uzávěrového operátoru striktně větší než B. i := n d := m while true do© ª C := B ⊕ kd/i if B
1 then d := d − 1 else i := i − 1 d := m end Algoritmus 3: NextClosure
Výpočet uzávěru je v předchozím algoritmu ukryt na řádku č. 4. Připomeňme si, jak je operátor definován: ∞ [ ∗ clT ∗ (Z) = Z Tn n=0 Y
přičemž (pro Z ∈ L ):
S ∗ Z T = Z ∪ {B ⊗ S(A, Z)∗ | A ⇒ B ∈ T a A 6= Z} , ∗ Z T0 = Z, ∗ ∗ ∗ Z Tn = (Z T n−1 )T , pro n ≥ 1.
Při použití globalizace jako zdůrazňovače pravdy můžeme druhý řádek zjednodušit na tvar: [ ∗ ZT = Z ∪ {B | A ⇒ B ∈ T a A ⊂ Z} . Výpočet podle tohoto předpisu je konečný díky konečné množině atributů a pravdivostních hodnot. Pseudokód uvedeného výpočtu je nyní již triviální, proto jej zde nebudeme uvádět. Problémem ovšem je značná výpočetní náročnost tohoto postupu, konkrétně je to O(np2 ), kde n je počet atributů a p je počet atributových implikací v T . Ta je způsobena zejména tím, že jednotlivé atributové implikace jsou posuzovány vícekrát než by bylo nutné. 12
3.4.
GLinClosure
Řešení předchozího problému představuje algoritmus jménem Graded LinClosure, který je fuzzy rozšířením algoritmu LinClosure známého z databází. Více o tomto rozšíření najdete v [9]. Algoritmus je zde pro konzistenci uveden v původní podobě, která v závislosti na příznaku PCLOSED vrací buď námi požadovaný uzávěr clT ∗ (pro PCLOSED = true) nebo nejmenší model T obsahující vstupní množinu (pro PCLOSED = false). Složitost algoritmu je O(n), kde n označuje rozsah vstupu. Tohoto zřejmého vylepšení bylo dosáhnuto tím, že každá atributová implikace je posuzována pouze jednou. Princip algoritmu je v zásadě obdobný jako u dříve uvedeného předpisu – jde o postupné přidávání přípustných konsekventů (tedy pravých stran) implikací z množiny T . Je zde však také k dispozici efektivní test, zda je levá strana implikace obsažena v konstruovaném uzávěru tak, aby k němu mohla být její pravá strana přidána. V následujícím textu budeme značení A(y) = a zapisovat také jako hy, ai ∈ A. Popišme si blíže některé proměnné použité v pseudokódu algoritmu. Fuzzy množina atributů NEWDEP reprezentuje konstruovaný uzávěr, CARDND značí kardinalitu této fuzzy množiny. COUNT[A ⇒ B] je kladné celé číslo označující počet atributů z množiny A takových, že A(y) > NEWDEP(y), Jako CARD[A ⇒ B] budeme označovat kardinalitu fuzzy množiny A. Poslední tři proměnné jsou důležité právě pro zmíněný rychlý test inkluze. Jakmile se v průběhu výpočtu hodnota COUNT[A ⇒ B] sníží na 0, víme, že A ⊆ NEWDEP. Jsou-li pak odlišné kardinality množin (tedy proměnné CARD[A ⇒ B] a CARDND), dostáváme automaticky A ⊂ NEWDEP. Na kardinalitu fuzzy množin budeme nahlížet následujícím způsobem. Uvažme monotónní injektivní zobrazení fL : L → [0, 1]. Pro libovolnou fuzzy množinu atributů M ∈ LY můžeme definovat číslo card(M ) ∈ [0, ∞] jako P card(M ) = hy,ai∈M fL (a). Dále k použitým proměnným. UPDATE je fuzzy množina atributů, jenž mají být ještě v průběhu výpočtu aktualizovány. WAITLIST je seznam fuzzy množin atributů, které mají být přidány ke konstruovanému uzávěru, jakmile se zvýší jeho kardinalita. LIST[y] je množina ukazatelů na fuzzy atributové implikace, ve kterých figuruje na jejich levé straně atribut y. SKIP[y][A ⇒ B] označuje, zda byla tato implikace již použita při aktualizaci atributu y. DEGREE[y][A ⇒ B] značí stupeň, ve kterém je atribut y obsažen v levé straně implikace. Prázdný seznam je v algoritmu uveden jako ().
13
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
Vstup: množina atributových implikací THEORY nad atributy Y , fuzzy množina atributů Z ∈ LY a příznak PCLOSED Výstup: clTHEORY (Z) pro PCLOSED = true, jinak [Z]THEORY NEWDEP := Z foreach A ⇒ B ∈ THEORY do if A = ∅ then NEWDEP := NEWDEP ∪ B else COUNT[A ⇒ B] := | A | CARD[A ⇒ B] := card(A) foreach hy, ai ∈ A do add A ⇒ B to LIST[y] DEGREE[y][A ⇒ B] := a SKIP[y][A ⇒ B] := f alse end end UPDATE := NEWDEP CARDND := card(NEWDEP) WAITLIST := ( ) while UPDATE 6= ∅ do choose hy, ai ∈ UPDATE UPDATE := UPDATE − {hy, ai} foreach A ⇒ B ∈ LIST[y] such that SKIP[y][A ⇒ B] = f alse and DEGREE[y][A ⇒ B] ≤ a do SKIP[y][A ⇒ B] := true COUNT[A ⇒ B] := COUNT[A ⇒ B] − 1 if COUNT[A ⇒ B] = 0 and (PCLOSED = f alse or CARD[A ⇒ B] < CARDND) then ADD := B ª NEWDEP P CARDND := CARDND + hy,ai∈ADD (fL (a) − fL (NEWDEP (y))) NEWDEP := NEWDEP ∪ ADD UPDATE := UPDATE ∪ ADD if PCLOSED = true and ADD 6= ∅ then while WAITLIST 6= ( ) do choose B ∈ WAITLIST remove B from WAITLIST ADD := B ª NEWDEP P CARDND := CARDND + hy,ai∈ADD (fL (a) − fL (NEWDEP (y))) NEWDEP := NEWDEP ∪ ADD UPDATE := UPDATE ∪ ADD end if COUNT[A ⇒ B] = 0 and PCLOSED = true and CARD[A ⇒ B] = CARDND then add B to WAITLIST end end return NEWDEP Algoritmus 4: GLinClosure
14
4.
Aplikace
Hlavním cílem této diplomové práce bylo vytvořit implementaci některých algoritmů použitelných ke generování některých bází atributových implikací (viz kapitola 3) a provést analýzu efektivity této implementace, zejména srovnání s předchozími implementacemi. Celá aplikace je realizována jako konzolová, veškeré operace lze provádět pomocí argumentů příkazové řádky. Jako programovací jazyk bylo použit standardní C (v normě ISO C90), přičemž aplikace nepoužívá žadné platformově-specifické vlastnosti, měla by tedy být přenositelná na velké množství různých systémů. Stačí mít k dispozici kompilátor jazyka C pro cílovou platformu a aplikaci přeložit ze zdrojových kódů. Standardně je aplikace distribuovaná ve zdrojových kódech s binárními spusR R titelnými soubory pro platformu Microsoft° Windows° (najdete je v adresáři bin/win32). Aplikace při výpočtu používá strukturu pravdivostních hodnot získanou ze vstupních dat a případně od uživatele. Při výpočtech je použito Lukasiewiczovo residuum, ovšem jeho význam je utlumen použitým zdůrazňovačem pravdy – globalizací. V případě problémů prosím kontaktujte autora na e-mailu či . Celý balíček je možné získat na adresách: • http://phoenix.inf.upol.cz/~horakz/gd.tgz • http://projects.entis-design.com/gd
4.1.
Struktura
bin/ data/ doc/ src/
binární spustitelné soubory ukázková vstupní data dokumentace (včetně zdrojového kódu v LATEXu) zdrojové kódy aplikace a pomocných programů
Makefile LICENSE.TXT README.TXT compile cygwin.bat compile mingw.bat
soubor s pravidly pro kompilaci pomocí balíčku Make text licence GNU GPL 2 popis balíčku a návod na sestavení a použití aplikace dávka příkazů pro sestavení v prostředí Cygwin dávka příkazů pro sestavení v prostředí MinGW
V adresáři s binárními spustitelnými soubory se po kompilaci (analogicky v případě předkompilovaných binárních souborů v podadresáři win32) nacházejí tyto soubory:
15
gd Hlavní aplikace pro generování GD báze. gd sparse Varianta aplikace používající některé odlišné datové struktury výhodné pro práci s tzv. řídkými kontexty. Jde o kontexty, ve kterých je většina prvků nulových a není tedy nutné tyto prvky uchovávat. gd slow Varianta aplikace využívající pomalejší způsob výpočtu uzávěru, již jen pro demonstrační účely. gencontext Pomocná aplikace pro generování náhodných kontextů (viz dále).
4.2.
Ovládání aplikace
Ovládání aplikace je v zásadě totožné na různých platformách, pro které je určena. Základní nápovědu můžete získat spuštěním binárního souboru (umístěného v adresáři bin, případně jeho podadresáři win32) s parametrem help: > ./gd --help Guigues-Duquenne bassis in fuzzy setting (linear L with globalization) Original code (c) Vilem Vychodil C implementation Zdenek Horak v1.0a Usage: gd [OPTIONS] [FILE] Compute GD base and further info from data table in FILE (or stdin by default) Options: -v be verbose -o ... write output to specified file -r perform supp-reduction of implications -f n specify own degree of full truth (also --fully-true) fetch input from stdin (default if filename omitted) -s ... specify type of output (PLAIN/SCHEME) -c ... limit cache size to x kB (0 unlimited, -1 to disable) -dxxx things you want to print out, where x is one of the following m as implications (also --implications) p as pseudointents (also --pseudos) i as intents (also --intents) s as stem basis (also --stem) c as concepts (also --concepts) n as number of (pseudo)intents
Program implicitně předpokládá datovou tabulku na standardním vstupu. Pokud jako jeden z argumentů uvedete jméno souboru, program se pokusí načíst data právě z tohoto souboru. Formát vstupních dat je uveden v následující podkapitole. Proberme si nyní postupně jednotlivé přepínače aplikace. Pokud chcete, aby program vypisoval poněkud více informací o své činnosti, použijte přepínač -v. Zejména v průběhu delších výpočtů se může hodit zobrazování jednoduchého ukazetele průběhu. Chcete-li výstup aplikace uložit do souboru, můžete tak mj. učinit přepínačem -o následovaným jménem souboru. 16
Program získává informace o struktuře pravdivostních hodnot ze vstupních dat. To je postačující, ovšem pouze v případě, že se v datech vyskytuje i úplně pravdivý prvek (tj. například číslo 10 při škále pravdivostních hodnot 0–10). Pokud tomu tak není, je nutné jej aplikaci dodat pomocí přepínače -f. Jestliže vám nevyhovuje formát výstupu aplikace, můžete si zvolit jiný, konkrétně pomocí přepínače -s následovaného klíčovým slovem SCHEME (usnadňuje použití např. v některých funkcionálních jazycích) nebo PLAIN (standardně). Supp-redukovanou bázi atributových implikací (viz dříve) můžete nechat vypočítat pomocí přepínače -r. Standardně aplikace vypisuje na výstup Guigues-Duquennovu bázi atributových implikací, množinu pseudo-intentů, intentů, formálních konceptů a kmenovou bázi. Pokud nepotřebujete tyto informace všechny, můžete zvolit výpis libovolné jejich kombinace pomocí přepínače -d, bez mezer následovaným písmeny odpovídajícími jednotlivým komponentám výstupu (m pro implikace, p pro pseudo-intenty, i pro intenty, s pro kmenovou bázi, c pro koncepty a n pro počty pseudo-intentů a intentů). Spíše technickou záležitostí je přepínač -c, který umožňuje omezit množství pomocné paměti, kterou aplikace při běhu využívá. Přepínač se zadává s číslem v kilobytech a použití najde zejména při delších výpočtech na serverech sdílených s dalšími uživateli. Hodnota -1 omezí použití pomocné paměti jen na místa, kde je to nezbytně nutné. Chcete-li rovnou začít aplikaci používat, můžete ji prostě spustit s některým z ukázkových vstupních souborů (tento odpovídá Tabulce 1) > ./gd ../data/inputorig.txt Názorněji si však ukažme použití aplikace na následujícím příkladu. Po jeho spuštění program načte tabulku ze souboru data/inputorig.txt, vypočte Suppredukovanou GD bázi atributových implikací a ve SCHEME notaci ji zapíše do souboru result. Během výpočtu bude zobrazovat informace o jeho průběhu. > ./gd -v -r -o result -s SCHEME -dm ../data/inputorig.txt Guigues-Duquenne bassis in fuzzy setting (linear L with globalization) Original code (c) Vilem Vychodil C implementation Zdenek Horak v1.0a Input file: data/inputorig.txt Fetching input from file. Fetched data: Columns: 4 Rows: 9 Full truth: 10 Truth degrees: 3 { 0/0 5/1 10/2 } Computing ... Writing output to file ’result’
17
4.3.
Formát vstupních dat
Vstupem aplikace je datová tabulka reprezentující formální fuzzy kontext, uložená buď v souboru nebo předložená na standardní vstup aplikace (viz výše). Syntaxe zápisu je triviální, jde o seznam celých čísel, oddělený například mezerami, nebo jinými znaky. Podmínkou ovšem je, že samotným pravdivostním stupňům tabulky předchází čísla určující počet řádků a sloupců. Program také z logických důvodů zamítne výpočet kontextu skládajícího se jen z nulových hodnot. Nečíselné znaky na vstupu jsou ignorovány, působí pouze jako oddělovače. Jak již bylo uvedeno, pravdivostními stupni jsou celá čísla, nikoliv čísla desetinná, jak bývá běžné. Tato skutečnost není nijak limitující, protože se pohybujeme v konečné množině pravdivostních hodnot. Maximální velikost pravdivostního stupně je určena rozsahem datového typu signed integer cílové platformy. Nejmenší pravdivostní stupeň vždy odpovídá hodnotě 0. Ukázkový kontext z Tabulky 1 tak lze zapsat například jedním z následujících způsobů. 9 4 10 0 0 10 10 0 0 10 10 0 0 10 10 0 5 10 0 10 10 5 0 10 10 5 5 5 10 0 5 5 10 0 10 0 10 0
4.4.
( (9 4) (10 0 0 10) (10 0 0 10) (10 0 0 10) (10 0 5 10) (0 10 10 5) (0 10 10 5) (5 5 10 0) (5 5 10 0) (10 0 10 0) )
Generátor náhodných kontextů
Součástí diplomové práce je i jednoduchá aplikace pro generování náhodných formálních fuzzy kontextů s předem danými vlastnosti. Její využití je zejména jako zdroj vstupních dat při testování rychlosti aplikace pro generování atributových implikací, nicméně může nalézt své uplatnění i jinde.
18
Základní přehled o ovládání programu získáte opět příkazem: > ./gencontext --help Generate fuzzy context (c)Zdenek Horak Usage: gencontext [OPTIONS] Generate data table with specified properties Options: -o -d -r -c -f -s -p
... n n n n ... ...
write output to specified file number of degrees (also --degrees) number of rows (also --rows) number of columns (also --columns) density (percentage) of non-null degrees (also --density) specify type of output (PLAIN/SCHEME) specify own propability distribution (numbers separated by spaces, also --probabilities)
Význam přepínače -o je stejný jako u aplikace pro generování bází, tedy určuje, že výstup se má zapsat do uvedeného souboru. Obdobně přepínač -s opět slouží k výběru formátu výstupu. Zatímco volba PLAIN je pro člověka přehlednější, volba SCHEME je výhodnější pro použití např. ve funkcionálních jazycích. Velikost datové tabulky se určuje přepínači -c, následovaného požadovaným počtem sloupců a -r s požadovaným počtem řádků. Požadovaný počet pravdivostních stupňů určíte přepínačem -d. Pomocí přepínače -f můžete ovlivnit výskyt nenulových hodnot v kontextu. Číslo za tímto přepínačem určuje v procentech šanci, že na dané pozici se objeví právě nenulová hodnota. Tedy volba -f 10 vytvoří velmi řídký kontext, kde bude asi jen desetina hodnot různých od nuly. Potřebujete-li specifikovat pravděpodobnosti jednotlivých prvků přesněji, můžete využít přepínače -p následovaného celými čísly oddělenými mezerami. Tyto hodoty odpovídají pravděpodobnostem (frekvencím) jednotlivých prvků, výběr poté probíhá metodou „ruletového kolaÿ. Opět si praktické použití ukažme na následujícím příkladu, který vygeneruje formální fuzzy kontext s pěti sloupci, deseti řádky a třemi pravdivostními stupni (0, 1 a 2), přičemž bude větší pravděpodobnost, že se ve výstupu objeví stupně 0 a 2. Výstup bude zapsán ve SCHEME notaci. > ./gencontext -r 10 -c 5 -d 3 -p 10 5 10 -s SCHEME ( (2 (2 (0 (2 (1 (2 (0 (0 (2 (1 )
0 2 0 2 0 2 1 2 1 2
1 2 2 0 2 2 0 0 2 2
0 0 2 0 1 1 0 2 1 2
1) 2) 1) 2) 0) 0) 2) 0) 1) 1)
19
4.5.
Kompilace ze zdrojového kódu
Zdrojový kód programu odpovídá standardu jazyka C a není vázán na žádné platformově-specifické vlastnosti. Jeho kompilace je tedy – alespoň teoreticky – možná na velkém množství různých systémů. Nejjednodušším způsobem (zejména na množství *NIXových platforem) je využití balíku Make (ve spolupráci s kompilátorem GCC), kdy po rozbalení zdrojových kódů stačí spustit příkaz: > make gcc -O9 -mcpu=pentium4 -march=pentium4 -fomit-frame-pointer -finline-functions -fexpensive-optimizations -ansi -pedantic -Wall -lm src/gd.c -o bin/gd gcc -DCONTEXT_SPARSE -O9 -mcpu=pentium4 -march=pentium4 -fomit-frame-pointer -finline-functions -fexpensive-optimizations -ansi -pedantic -Wall -lm src/gd.c -o bin/gd_sparse gcc -DCLOSURE_SLOW -O9 -mcpu=pentium4 -march=pentium4 -fomit-frame-pointer -finline-functions -fexpensive-optimizations -ansi -pedantic -Wall -lm src/gd.c -o bin/gd_slow gcc -ansi -pedantic -Wall -lm src/gencontext.c -o bin/gencontext chmod +x bin/gd chmod +x bin/gd_sparse chmod +x bin/gencontext
Pokud tento balík z nějakých důvodů použít nemůžete, lze samozřejmě provést kompilaci přímo pomocí kompilátoru GCC. To lze provést příkazy >gcc -O9 -mcpu=pentium4 -march=pentium4 -fomit-frame-pointer -finline-functions -fexpensive-optimizations -ansi -pedantic -Wall -lm src/gd.c -o bin/gd >gcc -DCONTEXT_SPARSE -O9 -mcpu=pentium4 -march=pentium4 -fomit-frame-pointer -finline-functions -fexpensive-optimizations -ansi -pedantic -Wall -lm src/gd.c -o bin/gd_sparse >gcc -DCLOSURE_SLOW -O9 -mcpu=pentium4 -march=pentium4 -fomit-frame-pointer -finline-functions -fexpensive-optimizations -ansi -pedantic -Wall -lm src/gd.c -o bin/gd_slow >gcc -ansi -pedantic -Wall -lm src/gencontext.c -o bin/gencontext >chmod +x bin/gd >chmod +x bin/gd_sparse >chmod +x bin/gencontext
Pro použití jiného C kompilátoru vás musím odkázat na dokumentaci tohoto R R kompilátoru. Na platformě Microsoft° Windows° byl k přeložení programu použit také kompilátor GCC, ovšem v prostředí MinGW4 . K rekompilaci v tomto prostředí můžete využít dávkový soubor compile_mingw.bat, ovšem před jeho použitím prosím nastavte správnou cestu na prvním řádku souboru. Pro prostředí Cygwin5 je připravena obdobná dávka v souboru compile_cygwin.bat. 4 5
http://www.mingw.org http://www.cygwin.com
20
4.6.
Vývojové nástroje
Při vývoji aplikace byl použit zejména následující software: GCC PSPad Valgrind GNU gprof Electric Fence Debian GNU/Linux
4.7.
http://gcc.gnu.org/ http://www.pspad.com/ http://valgrind.org/ http://www.gnu.org/software/binutils/ http://perens.com/freesoftware/electricfence/ http://debian.org/
Poznámky k implementaci
Samostatná dokumentace k aplikaci neexistuje. Vzhledem k charakteru aplikace a programovacího jazyka byl zvolen způsob vysvětlujících komentářů přímo ve zdrojových kódech programů. Přesto může být snad pro některé čtenáře užitečné seznámení s vnitřní strukturou aplikace. Při její tvorbě byl kladen důraz na efektivitu, zejména v časově kritických částech. Mimo tyto části kódu (při inicializaci a výstupu hodnot) byla upřednostněna přehlednost. Pro mírné urychlení a alespoň částečné zvýšení přehlednosti kritických částí kódu (výpočty pevných bodů uzávěrového operátoru) je ve větší míře využíván tzv. vedlejší efekt. Týká se zejména řešení pomocných pamětí, které jsou často uloženy ve statických proměnných a pro celkovou vyšší rychlost aplikace alokovány při prvním volání daných funkcí. Paměť je uvolněna posledním, speciálním vyvoláním. Konkrétně jde o funkce next(), z t ast() a linclosure() (vše v souboru fuzzy.c). Při kompilaci jsou pomocí přepínače ze stejných zdrojových kódů vytvořeny tři různé verze výsledné aplikace, jejichž účel byl popsán výše. Definice symbolu (ať už v kódu či pomocí přepínače kompilátoru) CONTEXT SPARSE způsobí, že místo souboru context full.c je při kompilaci použit soubor context sparse.c. Oba tyto soubory obsahují definice struktur kontextu, funkce šipkových operátorů nad kontextem, funkce pro vytvoření kontextu ze vstupu a funkci pro extrakci pravdivostních stupňů z kontextu. Soubor context sparse.c je speciálně upraven pro rychlejší práci s tzv. řídkými kontexty. Praktické nasazení však ukázalo, že tato možnost je výkonnostně dostačující i pro běžná data. Druhým přepínačem použitelným při kompilaci je CLOSURE SLOW, který způsobí, že při výpočtu pevného bodu uzávěrového operátoru se nepoužije algoritmus GLinClosure, ale pomalejší Closure (viz kapitola algoritmy). Původní varianta kódu v paměti alokuje pole celých čísel o velikosti m x n, kde m je počet sloupců kontextu, n počet řádků. Jediné operace, které se přímo nad kontexty provádějí, jsou výpočty šipkových operátorů se zdůrazňovači pravdy. V případě těchto „plnýchÿ kontextů jde o jednoduché zanořené smyčky. 21
Varianta pro řídké kontexty používá k ukládání také pole, ovšem zaznamenávají se pouze nenulové hodnoty – vždy jde o dvojici číslo atributu, hodnota atributu pro objekt na daném řádku. Konce řádků jsou vyznačeny číslem −1. Kvůli efektivitě výpočtu je tato struktura vytvořena nejen pro řádky, ale také pro sloupce. Jako základní datový typ byl zvolen signed int, protože disponuje dostatečným rozsahem k pokrytí dat, které by program byl schopen spočítat (což vzhledem k rychle rostoucí složitosti není velký problém), ale umožňuje i uložení kontrolních symbolů (jako například již zmíněný konec řádku). Na některých místech jsou kvůli rozsahu používány i jiné typy (např. unsigned int). Pokud by i přesto byl rozsah použitých datových typů nedostatečný, lze doporučit rekompilaci a spuštění například na 64-bitové platformě. V průběhu výpočtů jsou často používány fuzzy množiny, jejichž reprezentace v aplikaci je podle výhodnosti také dvojího druhu. První – prosté pole, obdobné reprezentaci „plnýchÿ kontextů. Druhá, podobná té, která je použita pro kontexty řídké. Kromě relativně malých pomocných pamětí je v aplikaci na dvou místech implementována masivnější cache paměť. V prvním případě jde o pole zaznamenávající výsledky šipkových operátorů s indexem ve formě n-árního vyhledávacího stromu, který umožňuje rychlé nalezení výsledků a plynulé škálování (díky uložení výsledků i indexu v lineárním poli). Tato cache paměť ztratila částečně na využití nasazením algoritmu GLinClosure. Druhé místo aplikace využívající cache paměť je inicializace struktur nutných pro výpočet algoritmu GLinClosure. Při tomto algoritmu je potřebný strom s informacemi o implikacích a atributech, avšak jen malou část stromu je nutné inicializovat znovu při každém volání funkce. Právě ta je uložena v cache paměti. Členění souborů zdrojových kódů odpovídá snaze o modularitu aplikace. Nyní blíže k jednotlivým souborům kódů. gd.c Jde o hlavní soubor celého projektu. Ve funkci main() se zpracovávají argumenty příkazové řádky, prostřednictvím funkcí readInput() a extractDegrees() program načte kontext, získá z něj množinu pravdivostních hodnot a spustí výpočet pomocí funkce generate pintents(). Ta svou činností odpovídá výše uvedenému algoritmu GMinBasis, případně GRedMinBasis, pokud uživatel zapnul tzv. Supp-reducibilitu. fuzzy.h Tento soubor obsahuje definice základních výčtových typů, typů struktur a funkcí používaných v celé aplikaci. fuzzy.c V tomto souboru najdete zejména funkci pro výpočet pevných bodů uzávěrového operátoru (next) a z ní volané funkce pro výpočet samotného uzávěru (z t ast a glin closure). context full.c, context sparse.c Jde o již výše popsané soubory obsahující definice kontextů a funkcí pro výpočet šipkových operátorů. 22
texts.c Tento soubor obsahuje veškeré textové konstanty používané v celé aplikaci k výstupu směrem k uživateli. Tyto konstanty jsou při kompilaci pomocí maker vkládány do ostatních souborů. utils.c Soubor obsahující pomocné funkce pro práci a výpočty s fuzzy množinami a některá pomocné makra. output.c V tomto souboru najdete funkce používané pro výpis vypočítaných informací. fuzzy basics.c Tento soubor obsahuje definice funkcí realizujících běžné varianty základních fuzzy operací (residua, konjunkce, zdůrazňovače pravdy). Ne všechny jsou při výpočtu pochopitelně použity. gencontext.c Jde o samostatnou pomocnou aplikaci pro generování náhodných kontextů. Některé její části se proto překrývají s kódy z ostatních souborů.
4.8.
Srovnání výkonnosti
Ve zbytku textu budeme mluvit o různých algoritmech a jejich implementacích. Kvůli přehlednosti budeme používat následující zkratky: gdLinFull Jedná se o vlastní implementaci využívající algoritmus GLinClosure a klasické datové struktury pro uložení kontextu. gdLinSparse Vlastní implementace – analogie předchozího, ovšem k uložení kontextu jsou použity speciální struktury vhodné pro řídké kontexty. gdClosure Opět vlastní implementace, kontext je ukládán v klasických strukturách, ale k výpočtu uzávěru je použit pomalejší algoritmus Closure. gdOriginal Původní implementace Viléma Vychodila v jazyce SCHEME6 využívající algoritmus GLinClosure. Do binární podoby zkompilováno překladačem Bigloo7 . Následující tabulky shrnují výsledky výpočtů zmíněných programů nad různými vstupními daty. Uvedené hodnoty představují průměr z více náhodných vzorků. Výpočty probíhaly na počítači s procesorem AMD AthlonTM XP 2200+, 512 MB operační paměti. Jako operační systému byl použit Debian GNU/Linux 3.1, verze jádra 2.6.8-2. V případě datových tabulek s binárními atributy existují testovací vzorky, na nichž panuje v komunitě Data Miningu dostatečná shoda a lze pomocí nich porovnávat efektivnost jednotlivých algoritmů (viz http://fimi.cs.helsinki.fi/data/). V našem případě je situace ovšem složitější, zejména proto, že zpracovatelný rozsah dat je zatím velmi omezený, ale 6 7
http://www.schemers.org/ http://www-sop.inria.fr/mimosa/fp/bigloo/
23
také proto, že celé odvětví stojí teprve na počátku. Nezbylo tedy než pomocí několika krátkých experimentů stanovit výpočetně schůdný rozsah dat tak, aby ilustroval vlastnosti jednotlivých algoritmů a implementací. Zejména u rychlejších implementací a menších vstupních dat tak došlo k tomu, že se čas výpočtu dostal pod práh měřitelnosti. Tato skutečnost je v tabulkách znázorněna symbolem „<00:00.01ÿ. Cílem tabulky 2 je porovnat výkonnost jednotlivých implementací algoritmů na různě strukturovaných vstupních datech. Již na první pohled je zřejmé, že implementace, které jsou výsledkem této diplomové práce, jsou několikasetnásobně rychlejší, než implementace původní. Vzhledem k tomu, že v případě původního kódu šlo o spíše prototypiální implementaci se záměrem ověřit funkčnost a demonstrovat nové možnosti, nemohlo to ani dopadnout jinak. Jasně je také vidět vylepšení, kterého bylo dosáhnuto použitím algoritmu GLinClosure. Rozdíl ve složitosti tohoto algoritmu a algoritmu původního (Closure) je způsoben především množstvím posuzování existujících atributových implikací v postupně budované bázi, což lze dosledovat i v této tabulce. Nárůst rychlosti je patrný za všech okolností, ale u kontextů s vyšším počtem pseudointentů v GD bázi je výraznější. Ve výsledcích může pozorné oko čtenářovo vysledovat i zajímavou věc týkající se varianty programu upravené pro řídké kontexty. Blíže si jí všimneme u tabulky 3. Všechna data bohužel není možné zahrnout do jednoho či několika málo grafů, uvedeme si proto alespoň základní výsledky, přičemž většinu proměnných charakteristik kontextu zafixujeme. Zjištěné výsledky týkající se průměrného počtu pseudo-intentů a konceptů potvrzují výsledky experimentů uvedených v [3]. Konkrétně tedy, že počet implikací GD báze roste spolu s rozsahem vstupních dat výrazně pomaleji než počet konceptů. Stejně tak, že nízká hustota vstupních kontextů vede sice k nízkému počtu konceptů, ale také k velkému počtu pseudo-intentů. 12000
gdOriginal 400
10000 8000
300
[ms]
intenty
6000
200
4000 gdClosure
100
gdLinFull
0 5
30
55 Hustota
2000 pseudointenty
0
80
5
30
55 Hustota
80
Obrázek 1. Doba výpočtu, resp. množství intentů a pseudointentů pro kontext 25 x 15 x 5 v závislosti na jeho hustotě 24
25
b
čas je uveden ve formátu (hodiny:)minuty:sekundy.milisekundy zápis znamená počet řádků x počet sloupců x počet pravdivostních hodnot c poměrné zastoupení nenulových hodnot d tato hodnota není podložena dostatečným počtem vzorků
a
gdLinFull < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 00:00.01 < 00:00.01 < 00:00.01 00:00.03 00:00.08 < 00:00.01 00:00.08 00:00.96 00:09.95
čas výpočtua gdLinSparse gdClosure < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 00:00.01 < 00:00.01 00:00.04 00:00.01 00:00.09 < 00:00.01 00:00.01 < 00:00.01 00:00.06 00:00.03 00:00.38 00:00.09 00:00.50 < 00:00.01 00:00.07 00:00.08 00:01.02 00:00.96 00:16.32 00:10.02 01:47.50 gdOriginal < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 < 00:00.01 00:00.03 00:00.12 00:00.16 00:00.01 00:00.16 00:00.48 00:01.28 00:00.08 00:00.65 00:08.42 02:15.78 00:00.65 00:10.67 07:29.31 d 5:58:40.85
průměrný počet konceptů pseudo-intentů 5 5 13 6 20 3 25 1 5 9 24 23 76 38 107 36 5 9 35 34 86 59 232 70 13 34 111 96 693 183 3 454 76 16 61 194 218 1 451 649 11 986 861
Tabulka 2. Srovnání výkonnosti algoritmů a jejich implementací
kontext rozsahb hustotac 15 x 5 x 2 5% 15 x 5 x 2 30 % 15 x 5 x 2 55 % 15 x 5 x 2 80 % 15 x 5 x 5 5% 15 x 5 x 5 30 % 15 x 5 x 5 55 % 15 x 5 x 5 80 % 15 x 5 x 10 5% 15 x 5 x 10 30 % 15 x 5 x 10 55 % 15 x 5 x 10 80 % 25 x 15 x 2 5% 25 x 15 x 2 30 % 25 x 15 x 2 55 % 25 x 15 x 2 80 % 25 x 15 x 5 5% 25 x 15 x 5 30 % 25 x 15 x 5 55 % 25 x 15 x 5 80 %
kontext rozsahb hustotac 35 x 15 x 10 5% 35 x 15 x 10 30 % 35 x 15 x 10 55 % 35 x 15 x 10 80 % 35 x 25 x 10 5% 35 x 25 x 10 30 % 35 x 25 x 10 55 %
čas výpočtua gdLinFull gdLinSparse 00:00.02 00:00.02 00:00.56 00:00.57 00:17.85 00:17.98 38:24.57 38:09.02 00:00.19 00:00.21 00:07.30 00:07.37 31:19.63 30:44.53
průměrný počet konceptů pseudo-intentů 26 80 424 408 5 792 1 609 149 649 3 721 41 164 952 1 030 21 458 6 056
Tabulka 3. Výkonnost podle použitých datových struktur a
čas je uveden ve formátu (hodiny:)minuty:sekundy.milisekundy zápis znamená počet řádků x počet sloupců x počet pravdivostních hodnot c poměrné zastoupení nenulových hodnot b
Tabulka 3 se snaží zdokumentovat trend, který je patrný již z tabulky 2 – tedy že struktury použité k implementaci práce s tzv. „řídkýmiÿ kontexty (tedy kontexty, ve kterých je většina hodnot nulových) jsou dostatečně efektivní i pro práci s kontexty ostatními. Oproti předchozí tabulce jsou vstupní data větší, přesto je stále odchylka času potřebného k výpočtům malá. Tato tabulka zároveň ukazuje, že přes veškerou snahu o efektivitu a optimalizaci, je celková složitost problému stále tak velká, že kontexty větší než uvedené v tabulce, budou jen obtížně zpracovatelné.
26
Závěr Tato práce popisuje algoritmy schopné generovat minimální neredundantní báze atributových implikací z datových tabulek s fuzzy attributy. Pro čtenáře je uvedeno i shrnutí teorie potřebné pro zvládnutí těchto algoritmů. Součástí práce byla i efektivní implementace popsaných algoritmů. Na závěr jsou provedeny a vyhodnoceny experimenty s několika implementacemi zmíněných algoritmů a různými vstupními daty. Zajímavým zjištěním (jež zřejmě stojí za další prozkoumání) je, že datové struktury použité v této aplikaci pro práci s řídkými kontexty, jsou dostatečně rychlé i pro práci s běžnými kontexty. Jejich paměťová náročnost je však v nejhorším případě 4x větší. Experimenty s náhodnými daty ovšem také jasně ukázaly, kde leží hranice současných algoritmů. Další drobná vylepšení jsou sice samozřejmě možná, ovšem na celkové době výpočtu se příliš neprojeví. Momentálně se zdá být největší překážkou složitost Ganterova algoritmu NextClosure a jeho fuzzy rozšíření. Vzhledem k tomu, že toto rozšíření vzniklo z původní verze pracující s binárními atributy, jeví se cesta další adaptace klasických algoritmů jako slibná. V klasickém případě je k dispozici ještě celá řada výkonnějších algoritmů (viz např. [15]), které by snad bylo možné adaptovat. Jiná šance se nabízí v možné paralelizaci používaných algoritmů.
27
Conclusions This MSc. thesis describes algorithms capable of generating minimal nonredundant basis of attribute implications from data tables with fuzzy attributes. Also an overview of theory is presented to the readers. Part of this thesis provides an effective implementation of described algorithms. Finally some experiments are done and evaluated on different implementations of mentioned algorithms and various data contexts. An interesting observation (which probably deserves further investigation) is, that data structures used to handle sparse contexts in this implementation, are fast enough to handle also common contexts. However, the memory consumption is 4 times bigger in the worst case. Experiments with random data have also clearly shown what the current range of computably tractable contexts is. Further small improvements are surely possible, but the total computational time will not be affected too much. Currently, the biggest obstruction seems to be the complexity of used Ganter’s NextClosure algorithm (and it’s fuzzy extension). With respect to the fact, that this extension has arised from the original bivalent case, the way of adopting further algorithms seems to be promising. There are yet a number of more efficient algorithms (see [15]) in the bivalent case. Another opportunity is in possible paralelization of used algorithms.
28
Reference [1] Bělohlávek R. Algorithms for fuzzy concept lattices. Proc. Fourth Int. Conf. on Recent Advances in Soft Computing, RASC 2002, Nottingham, United Kingdom, 12–13 December, 2002, s. 67–68 (extended abstract); s. 200–205 (full paper on the included CD). ISBN 1-84233-0764. [2] Bělohlávek R., Funioková T., Vychodil V. Galois connections with hedges. Proc. IFSA, 2005, Vol. II, s. 1250–1255. ISBN 7-302-11377-7. [3] Bělohlávek R., Vychodil V. Implications from data with fuzzy attributes. AISTA, 2004. ISBN 2-9599776-8-8. [4] Bělohlávek R., Vychodil V. Fuzzy attribute logic: syntactic entailment and completeness. JCIS, 2005, s. 78–81. ISBN 0-9707890-3-3. [5] Bělohlávek R., Vychodil V. Reducing attribute implications from data tables with fuzzy attributes to tables with binary attributes. JCIS, 2005, s. 82–85. ISBN 0-9707890-3-3. [6] Bělohlávek R., Vychodil V. Fuzzy attribute logic: attribute implications, their validity, entailment, and non-redundant basis. Proc. IFSA, 2005, Vol. I, s. 622–627. ISBN 7-302-11377-7. [7] Bělohlávek R., Vychodil V. Axiomatizations of fuzzy attribute logic. Proc. IICAI, 2005, s. 2178–2193. ISBN 0-9727412-1-6. [8] Bělohlávek R., Vychodil V. Functional dependencies of data tables over domains with similarity. IICAI, 2005, s. 2486–2504. ISBN 0–9727412–1–6. [9] Bělohlávek R., Vychodil V. Graded LinClosure (submitted). [10] Bělohlávek R., Vychodil V.: Reducing the size of if-then rules generated from data tables with graded attributes. IEEE IRI 2006, Sep 16–18, 2006, Waikoloa, Hawaii, USA (to appear). [11] Burris S., Sankappanavar H.P. A Course in Universal Algebra. SpringerVerlag, New York, 1981. [12] Ganter B., Wille R. Formal Concept Analysis: Mathematical Foundations. Springer, 1999. [13] Hájek P. Metamathematics of Fuzzy Logic. Kluwer, Dordrecht, 1998. [14] Hájek P. On very true. Fuzzy sets and Systems 124, 2001, s. 329–333.
29
[15] Kuznetsov S. O., Obiedkov S. A. Comparing performance of algorithms for generating concept lattices. J. Experimental & Theoretical Artificial Intelligence 14(2003), s. 189—216. [16] Sochor A. Klasická matematická logika. Karolinum, Praha, 2001. ISBN 80-246-0218-0. [17] Vychodil V. Fuzzy attribute implications as formulas of logics with truthevaluated syntax. JCIS, 2005, s. 74–77. ISBN 0-9707890-3-3.
30
A.
GNU General Public License Version 2, June 1991 c 1989, 1991 Free Software Foundation, Inc. Copyright ° 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed. Preamble The licenses for most software are designed to take away your freedom to share and change it. By contrast, the GNU General Public License is intended to guarantee your freedom to share and change free software—to make sure the software is free for all its users. This General Public License applies to most of the Free Software Foundation’s software and to any other program whose authors commit to using it. (Some other Free Software Foundation software is covered by the GNU Library General Public License instead.) You can apply it to your programs, too. When we speak of free software, we are referring to freedom, not price. Our General Public Licenses are designed to make sure that you have the freedom to distribute copies of free software (and charge for this service if you wish), that you receive source code or can get it if you want it, that you can change the software or use pieces of it in new free programs; and that you know you can do these things. To protect your rights, we need to make restrictions that forbid anyone to deny you these rights or to ask you to surrender the rights. These restrictions translate to certain responsibilities for you if you distribute copies of the software, or if you modify it. For example, if you distribute copies of such a program, whether gratis or for a fee, you must give the recipients all the rights that you have. You must make sure that they, too, receive or can get the source code. And you must show them these terms so they know their rights. We protect your rights with two steps: (1) copyright the software, and (2) offer you this license which gives you legal permission to copy, distribute and/or modify the software. Also, for each author’s protection and ours, we want to make certain that everyone understands that there is no warranty for this free software. If the software is modified by someone else and passed on, we want its recipients to know that what they have is not the original, so that any problems introduced by others will not reflect on the original authors’ reputations. Finally, any free program is threatened constantly by software patents. We wish to avoid the danger that redistributors of a free program will individually obtain patent licenses, in effect making the program proprietary.
31
To prevent this, we have made it clear that any patent must be licensed for everyone’s free use or not licensed at all. The precise terms and conditions for copying, distribution and modification follow.
GNU General Public License Terms and Conditions For Copying, Distribution and Modification 0. This License applies to any program or other work which contains a notice placed by the copyright holder saying it may be distributed under the terms of this General Public License. The “Program”, below, refers to any such program or work, and a “work based on the Program” means either the Program or any derivative work under copyright law: that is to say, a work containing the Program or a portion of it, either verbatim or with modifications and/or translated into another language. (Hereinafter, translation is included without limitation in the term “modification”.) Each licensee is addressed as “you”. Activities other than copying, distribution and modification are not covered by this License; they are outside its scope. The act of running the Program is not restricted, and the output from the Program is covered only if its contents constitute a work based on the Program (independent of having been made by running the Program). Whether that is true depends on what the Program does. 1. You may copy and distribute verbatim copies of the Program’s source code as you receive it, in any medium, provided that you conspicuously and appropriately publish on each copy an appropriate copyright notice and disclaimer of warranty; keep intact all the notices that refer to this License and to the absence of any warranty; and give any other recipients of the Program a copy of this License along with the Program. You may charge a fee for the physical act of transferring a copy, and you may at your option offer warranty protection in exchange for a fee. 2. You may modify your copy or copies of the Program or any portion of it, thus forming a work based on the Program, and copy and distribute such modifications or work under the terms of Section 1 above, provided that you also meet all of these conditions: (a) You must cause the modified files to carry prominent notices stating that you changed the files and the date of any change.
32
(b) You must cause any work that you distribute or publish, that in whole or in part contains or is derived from the Program or any part thereof, to be licensed as a whole at no charge to all third parties under the terms of this License. (c) If the modified program normally reads commands interactively when run, you must cause it, when started running for such interactive use in the most ordinary way, to print or display an announcement including an appropriate copyright notice and a notice that there is no warranty (or else, saying that you provide a warranty) and that users may redistribute the program under these conditions, and telling the user how to view a copy of this License. (Exception: if the Program itself is interactive but does not normally print such an announcement, your work based on the Program is not required to print an announcement.) These requirements apply to the modified work as a whole. If identifiable sections of that work are not derived from the Program, and can be reasonably considered independent and separate works in themselves, then this License, and its terms, do not apply to those sections when you distribute them as separate works. But when you distribute the same sections as part of a whole which is a work based on the Program, the distribution of the whole must be on the terms of this License, whose permissions for other licensees extend to the entire whole, and thus to each and every part regardless of who wrote it. Thus, it is not the intent of this section to claim rights or contest your rights to work written entirely by you; rather, the intent is to exercise the right to control the distribution of derivative or collective works based on the Program. In addition, mere aggregation of another work not based on the Program with the Program (or with a work based on the Program) on a volume of a storage or distribution medium does not bring the other work under the scope of this License. 3. You may copy and distribute the Program (or a work based on it, under Section 2) in object code or executable form under the terms of Sections 1 and 2 above provided that you also do one of the following: (a) Accompany it with the complete corresponding machine-readable source code, which must be distributed under the terms of Sections 1 and 2 above on a medium customarily used for software interchange; or, (b) Accompany it with a written offer, valid for at least three years, to give any third party, for a charge no more than your cost of physically 33
performing source distribution, a complete machine-readable copy of the corresponding source code, to be distributed under the terms of Sections 1 and 2 above on a medium customarily used for software interchange; or, (c) Accompany it with the information you received as to the offer to distribute corresponding source code. (This alternative is allowed only for noncommercial distribution and only if you received the program in object code or executable form with such an offer, in accord with Subsection b above.) The source code for a work means the preferred form of the work for making modifications to it. For an executable work, complete source code means all the source code for all modules it contains, plus any associated interface definition files, plus the scripts used to control compilation and installation of the executable. However, as a special exception, the source code distributed need not include anything that is normally distributed (in either source or binary form) with the major components (compiler, kernel, and so on) of the operating system on which the executable runs, unless that component itself accompanies the executable. If distribution of executable or object code is made by offering access to copy from a designated place, then offering equivalent access to copy the source code from the same place counts as distribution of the source code, even though third parties are not compelled to copy the source along with the object code. 4. You may not copy, modify, sublicense, or distribute the Program except as expressly provided under this License. Any attempt otherwise to copy, modify, sublicense or distribute the Program is void, and will automatically terminate your rights under this License. However, parties who have received copies, or rights, from you under this License will not have their licenses terminated so long as such parties remain in full compliance. 5. You are not required to accept this License, since you have not signed it. However, nothing else grants you permission to modify or distribute the Program or its derivative works. These actions are prohibited by law if you do not accept this License. Therefore, by modifying or distributing the Program (or any work based on the Program), you indicate your acceptance of this License to do so, and all its terms and conditions for copying, distributing or modifying the Program or works based on it. 6. Each time you redistribute the Program (or any work based on the Program), the recipient automatically receives a license from the original licensor to copy, distribute or modify the Program subject to these terms and 34
conditions. You may not impose any further restrictions on the recipients’ exercise of the rights granted herein. You are not responsible for enforcing compliance by third parties to this License. 7. If, as a consequence of a court judgment or allegation of patent infringement or for any other reason (not limited to patent issues), conditions are imposed on you (whether by court order, agreement or otherwise) that contradict the conditions of this License, they do not excuse you from the conditions of this License. If you cannot distribute so as to satisfy simultaneously your obligations under this License and any other pertinent obligations, then as a consequence you may not distribute the Program at all. For example, if a patent license would not permit royalty-free redistribution of the Program by all those who receive copies directly or indirectly through you, then the only way you could satisfy both it and this License would be to refrain entirely from distribution of the Program. If any portion of this section is held invalid or unenforceable under any particular circumstance, the balance of the section is intended to apply and the section as a whole is intended to apply in other circumstances. It is not the purpose of this section to induce you to infringe any patents or other property right claims or to contest validity of any such claims; this section has the sole purpose of protecting the integrity of the free software distribution system, which is implemented by public license practices. Many people have made generous contributions to the wide range of software distributed through that system in reliance on consistent application of that system; it is up to the author/donor to decide if he or she is willing to distribute software through any other system and a licensee cannot impose that choice. This section is intended to make thoroughly clear what is believed to be a consequence of the rest of this License. 8. If the distribution and/or use of the Program is restricted in certain countries either by patents or by copyrighted interfaces, the original copyright holder who places the Program under this License may add an explicit geographical distribution limitation excluding those countries, so that distribution is permitted only in or among countries not thus excluded. In such case, this License incorporates the limitation as if written in the body of this License. 9. The Free Software Foundation may publish revised and/or new versions of the General Public License from time to time. Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns.
35
Each version is given a distinguishing version number. If the Program specifies a version number of this License which applies to it and “any later version”, you have the option of following the terms and conditions either of that version or of any later version published by the Free Software Foundation. If the Program does not specify a version number of this License, you may choose any version ever published by the Free Software Foundation. 10. If you wish to incorporate parts of the Program into other free programs whose distribution conditions are different, write to the author to ask for permission. For software which is copyrighted by the Free Software Foundation, write to the Free Software Foundation; we sometimes make exceptions for this. Our decision will be guided by the two goals of preserving the free status of all derivatives of our free software and of promoting the sharing and reuse of software generally.
No Warranty 11. Because the program is licensed free of charge, there is no warranty for the program, to the extent permitted by applicable law. Except when otherwise stated in writing the copyright holders and/or other parties provide the program “as is” without warranty of any kind, either expressed or implied, including, but not limited to, the implied warranties of merchantability and fitness for a particular purpose. The entire risk as to the quality and performance of the program is with you. Should the program prove defective, you assume the cost of all necessary servicing, repair or correction. 12. In no event unless required by applicable law or agreed to in writing will any copyright holder, or any other party who may modify and/or redistribute the program as permitted above, be liable to you for damages, including any general, special, incidental or consequential damages arising out of the use or inability to use the program (including but not limited to loss of data or data being rendered inaccurate or losses sustained by you or third parties or a failure of the program to operate with any other programs), even if such holder or other party has been advised of the possibility of such damages.
End of Terms and Conditions
36
Appendix: How to Apply These Terms to Your New Programs If you develop a new program, and you want it to be of the greatest possible use to the public, the best way to achieve this is to make it free software which everyone can redistribute and change under these terms. To do so, attach the following notices to the program. It is safest to attach them to the start of each source file to most effectively convey the exclusion of warranty; and each file should have at least the “copyright” line and a pointer to where the full notice is found. hone line to give the program’s name and a brief idea of what it does.i Copyright (C) hyeari hname of authori This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. Also add information on how to contact you by electronic and paper mail. If the program is interactive, make it output a short notice like this when it starts in an interactive mode: Gnomovision version 69, Copyright (C) hyeari hname of authori Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type ‘show w’. This is free software, and you are welcome to redistribute it under certain conditions; type ‘show c’ for details. The hypothetical commands show w and show c should show the appropriate parts of the General Public License. Of course, the commands you use may be called something other than show w and show c; they could even be mouse-clicks or menu items—whatever suits your program. You should also get your employer (if you work as a programmer) or your school, if any, to sign a “copyright disclaimer” for the program, if necessary. Here is a sample; alter the names: 37
Yoyodyne, Inc., hereby disclaims all copyright interest in the program ‘Gnomovision’ (which makes passes at compilers) written by James Hacker. hsignature of Ty Cooni, 1 April 1989 Ty Coon, President of Vice This General Public License does not permit incorporating your program into proprietary programs. If your program is a subroutine library, you may consider it more useful to permit linking proprietary applications with the library. If this is what you want to do, use the GNU Library General Public License instead of this License.
38
