Třídění na základě odlišností závislostí atributů 

doktorand:
ing. Jan Burian
EuroMISE centrum – Kardio
Oddělení medicínské informatiky ÚI AV ČR a Fakulta informatiky a statistiky VŠE Praha 

burianj@vse.cz	školitel:
doc. PhDr. Karel Pstružina CSc.
Katedra filosofie
Fakulta informatiky a statistiky 
VŠE Praha

pstruzin@vse.cz	

obor studia:
Znalostní inženýrství a kognitivní vědy

Abstrakt

Tento článek popisuje nový přístup k třídění záznamů v databázích. Je zde technicky popsána  metoda identifikace třídícího atributu při učení bez učitele na základě analýzy závislostí atributů (měřených statistickými testy) pro různé třídy (kategorie) kandidáta na třídící atribut. Jsou ukázány možnosti jak měřit odlišnost závislostí atributů v třídách. Je popsán postup výběru třídícího atributu. Nakonec jsou navrženy další možné směry výzkumu.
1.	Třída jako závislost atributů
Představme si situaci, kdy chceme třídit záznamy uložené v tabulce relační databáze, avšak nemáme předem zadán atribut podle kterého třídit. Jedná se o častou situaci při strojovém učení bez učitele (unsupervised learning). To se využívá například u automatizovaných zařízení, které musí reagovat v reálném čase na nepředpověditelné situace, a lidský prvek nemůže poskytnout zpětnou vazbu z důvodů nedostatku času, či fyzické nemožnosti spojení se zařízením. Jiným příkladem je analýza pozorování příliš komplexních či zcela neznámých jevů, kdy předběžné znalosti nejsou k dispozici. Také v případě, že analyzujeme jev, který již je popsán nějakou teorií, ale ta z nějakého důvodu nedostačuje a chceme nalézt teorii alternativní, je na místě použít učení bez učitele. 
Klasické chápání třídy záznamů spočívá v tom, že si každý záznam představíme jako bod v prostoru atributů, můžeme jako třídy chápat shluky těchto bodů. Určením vhodných metrik těchto prostorů (míry podobnosti záznamů) a konstrukcí shluků, se zabývá rozsáhlá teorie, např. [2].
Tento způsob chápání třídy je intuitivní a méně náročný na formální reprezentaci, avšak nepostihuje globální vztahy v datech a to zejména u nominálních atributů (zde neexistuje uspořádání hodnot). 
Třídu záznamů můžeme alternativně chápat jako takovou skupinu záznamů, která má jisté ohodnocení vztahů mezi atributy. Ohodnocení vztahů budeme zde chápat jako určení závislosti mezi dvěma atributy tabulky databáze. 
Nechť V je množina všech atributů tabulky databáze. Nechť C  V je kandidát na třídící atribut a C1,C2 … Ck jsou kategorie (třídy)  tohoto atributu. Pro A,S  V; A  S; A,S  C označme AD(A,S|Ci) podmíněnou závislost atributů, představovanou hodnotu nějaké testové statistiky (například χ²) o závislosti dvou atributů A a S ve třídě Ci. 
Závislost atributů může být dána obecně libovolným statistickým testem závislosti mezi atributy, který je přípustný pro daný typ atributů.
My se v dalším budeme zabývat atributy kategoriálními, pro které se při určení závislosti vychází z kontingenční tabulky, která je daná atributem, jehož kategorie určují řádky tabulky (značíme A), atributem jehož kategorie určují sloupce tabulky (značíme S) a atributem jehož kategorie jsou podmínkou, kterou musí záznamy splňovat (značíme C, v našem případě pak tyto kategorie C1,C2 … Ck budou představovat třídy, do kterých budou záznamy rozděleny). Takovou  kontingenční tabulku označíme T(A,S,Ci)

Tabulka 1. Kontingenční tabulka T(A,S,Ci)
T(A, S, Ci)	S	
	s1	s2	...	sL	
A	a1	f1,1	f1,2	...	f1,L	
	a2	f2,1	f2,2	...	f2,L	
	...	...	...	...	...	
	aK	fK,1	fK,2	...	fK,L	

Zde fi,j je počet řádků databázové tabulky splňujících podmínku Ci a zároveň nabývajících hodnotu (kategorii) ai pro atribut A a hodnotu (kategorii) sj pro atribut S. Kategorie atributu C rozdělí množinu všech záznamů na třídy, ve kterých mohou být odlišné závislosti mezi atributy A a S. 
 
Pro ohodnocení vztahu můžeme použít buď testovací statistiku, či přímo hladinu pravděpodobnosti, na které je možno zamítnout hypotézu o nezávislosti atributů.

Příkladem systému, který lze použít pro generování závislostí mezi dvěma atributy při jisté podmínce představované kategoriemi třetího atributu (který pro naše účely chápeme jako kandidáta na třídící atribut), je procedura KL-Miner, součást dataminingového systému LISp-Miner [4]. Generovány jsou dvojice atributů (a k nim hodnoty příslušných testových statistik) při dané podmínce, které vyhovují tzv. KL-kvantifikátoru. Ten určuje druh použitého statistického testu a požadavek na tento test kladený (například platnost hypotézy o závislosti pro dané alfa). Pro naše účely stačí nastavit KL-kvantifikátor tak, aby se vygenerovaly závislosti pro všechny dvojice atributů. 

Poznámka. Vztahy mezi atributy nemusí být nutně všechny kombinace dvojic atributů (i když dále to budeme pro zjednodušení předpokládat). V systému KL-Miner můžeme určit dvě skupiny atributů, které nemusí být navzájem disjunktní. Potom atribut A z tabulky T(A,S,C) bude z první skupiny a atribut S ze skupiny druhé. Tím ovšem vnášíme do analýzy nějakou předběžnou znalost, která může zkreslit výsledek. 

Poznámka. Závislosti atributů mohou být symetrické i asymetrické. U symetrických bereme v úvahu jen jednu z obou permutací dvojice atributů (atribut je v A nebo v S). 

Poznámka. U systému KL-Miner může mít podmínka, ve které se střídají kategorie atributů představujících kandidáta na třídící atribut, složitější podobu. Může se jednat o konjunkce skupin kategorií různých atributů. Např.: 
Ci = Atribut1(Kategorie1 OR Kategorie2)  AND Atribut2(Kategorie3)
	V takovém případě by pak nemusel být identifikován jeden třídící atribut, ale třídící kombinace atributů a jejich kategorií.

Pokud je třída záznamů určena závislostí atributů, pak odlišnost tříd je dána odlišností závislostí atributů v třídách daných kategoriemi C (dále jen v třídách).   
Pokud chceme, aby třídy plnily nějaký praktický účel, musí v prvé řadě odlišovat skupiny záznamů. Proto je praktické vybrat takový třídící atribut, jehož kategorie roztřídí záznamy do tříd s maximálně odlišnými závislostmi atributů. 
Pokusme se o zjednodušený, ale srozumitelný příklad. Vezměme data o úmrtích pacientů z projektu STULONG [3] analyzovaná (pouze na základě asociačních pravidel) např. v [1]. Vyberme a transformujme z nich pro jednoduchost pouze tři atributy, každý se dvěma kategoriemi – hladina cholesterolu(vysoká, nízká), denní konzumace kávy(vysoká, nízká) a příčina úmrtí nádorové onemocnění (ano,ne). Pokud bychom záznamy rozdělili do tříd podle kategorií atributů hladina cholesterolu nebo spotřeba kávy, závislosti zbývajících atributů v třídách by se téměř nelišily. Pokud však rozdělíme data do tříd podle toho, zda příčina byla či nebyla nádorové onemocnění, v první třídě nalezneme silnou pozitivní závislost vysoké hladiny cholesterolu a vysoké spotřeby pití kávy, která v druhé třídě chybí. Závislosti atributů v třídách se liší a to nám přináší novou znalost. 
2.	 Odlišnost závislostí atributů v třídách
Stanovit odlišnost závislostí atributů v třídách je možno mnoha způsoby. Budeme se zde zabývat pouze dvěma z nich. Pro označení odlišnosti závislostí atributů v třídách budeme používat zkratku ADCD (Attribute Dependency Class Difference) s příslušným indexem označujícím metodu výpočtu (např. ADCD- nebo ADCD).
2.1	Odlišnost jako suma rozdílů ohodnocení závislosti atributů
Odlišnost závislostí atributů v třídách je možno pro 2 třídy (kandidát na třídící atribut má pouze dvě kategorie) definovat jako sumu absolutní hodnoty rozdílů ohodnocení závislosti atributů v třídách pro různá A a S. 
!Unexpected End of Formula

Tato odlišnost se sice jednoduše vypočte, avšak pro více tříd není jednoznačně dáno jak takový rozdíl závislostí atributů definovat a jak ho pak interpretovat. 
Maximální odlišnost závislostí mezi atributy má ten kandidát na třídící atribut pro nějž je ADCD maximální.
2.2	Odlišnost jako úhel mezi vektorem závislostí a osou souřadnic
Intuitivnějším a lépe interpretovatelným způsobem můžeme definovat odlišnost závislosti atributů v obecně k třídách, pokud si představíme závislosti atributů v třídách jako bod v prostoru, jehož dimenze jsou závislosti atributů v jednotlivých třídách. Pokud máme k tříd pak má tento prostor k rozměrů. Odlišnost závislostí atributů v třídách  pak můžeme chápat jako funkci úhlu , který svírá vektor (AD(A,S|C1), AD(A,S|C2), … AD(A,S|Ck)) a osa souřadnic prostoru dimenze k. Pro dvě dimenze můžeme sestrojit názorný graf.

Obr. 1. Vektor závislostí atributů A,S v třídách C

 Pokud AD(A,S|C1)=AD(A,S|C2), bod [AD(A,S|C1) ; AD(A,S|C2) ] se nalézá na ose souřadnic, úhel  je nulový a znamená to, že závislost A a S není podmíněna C.  

Pro vyjádření odlišnosti závislosti atributů A a S v třídách je vhodné použít cosinus úhlu , který se snadno vypočte podle vzorce analytické geometrie jako hodnota skalárního součinu vektoru (AD(A,S|C1), AD(A,S|C2),… AD(A,S|Ck)) a jednotkového vektoru dimenze k dělená součinem jejich velikostí. 
	Odlišnost závislostí atributů v třídách ADCD, pak bude suma těchto odlišností pro různá A a S.    

!Unexpected End of Formula

Poznámka. Jelikož jeden z vektorů je jednotkový, skalární součin vektorů v čitateli je pouze součtem složek vektoru (AD(A,S|C1), AD(A,S|C2) … AD(A,S|Ck)). Konstantní faktor  ve jmenovateli je velikost jednotkového vektoru dimenze k.
Pokud použijeme takové ohodnocení závislosti atributů ve třídách, že  hodnoty složek vektoru (AD(A,S|C1), AD(A,S|C2) … AD(A,S|Ck)) budou nabývat pouze nezáporných hodnot, bude obor hodnot ADCD interval <; 1>. Podotkněme, že v k rozměrném prostoru odchylka jednotkového vektoru a vektoru s jedinou nenulovou složkou není vždy 45° jako je tomu v prostoru dvourozměrném (tam by byl obor hodnot ADCD intervalu <;1>). 
Pokud hodnoty složek vektoru (AD(A,S|C1), AD(A,S|C2) … AD(A,S|Ck))  mohou nabývat záporných hodnot (typicky u testových statistik pro asymetrické závislosti),  bude obor hodnot ADCD interval <0;1>. 
	Pokud hodnoty složek vektoru (AD(A,S|C1), AD(A,S|C2) … AD(A,S|Ck)) budou všechny nulové, dodefinujeme hodnotu ADCD = 1. 
 
Z vlastností funkce cosinus vyplývá, že čím menší je ADCD , tím větší je odlišnost závislostí atributů v třídách. Maximální odlišnost závislostí mezi atributy má ten kandidát na třídící atribut pro nějž je ADCD minimální. 
V případě, že by pro praktické potřeby vadila tato nepřímá úměrnost, můžeme používat převrácenou hodnotu ADCD.
3.	Postup identifikace třídícího atributu 
Předpokládáme, že databáze je již nějak předzpracována či transformována a pracujeme pouze s relevantními odvozenými atributy.
Postup identifikující třídící atribut na základě maximální odlišnosti závislostí atributů v třídách vypadá (na základě výše uvedeného) následovně:
1.	Pro každou kategorii každého kandidáta na třídící atribut vyber z tabulky databáze třídu (skupinu záznamů, u kterých se daná kategorie vyskytuje). Pro tyto třídy vygeneruj závislosti dvojic ostatních atributů.  
2.	Urči odlišnost závislostí atributů v třídách (ADCD) pro jednotlivé kandidáty na třídící algoritmus. 
3.	Vyber jako třídící ten atribut, u nějž je odlišnost závislostí atributů v třídách maximální. 
4.	Závěr a další vývoj 
V současné době neexistuje software, který by z vygenerovaných závislostí atributů (tak jak je generuje např. KL-Miner či jiný statistický software) dokázal spočítat příslušné ADCD a vybrat třídící atribut. Budiž tento článek podnětem pro spolupráci na jeho tvorbě. 
	Výše uvedený koncept je možno dále doplňovat například o nové metody výpočtu ADCD. Popřípadě je možno používat nejen závislosti dvojic atributů, ale obecně n-tic atributů. To je však záležitost použitých statistických testů, výše uvedený koncept je v tomto ohledu univerzální.
	Výběr třídícího atributu ze známých atributů je jen dílčím řešením problému roztřídění záznamů podle maximální odlišnosti závislosti atributů v třídách. Daleko náročnější je problém tvorby nového atributu, který záznamy roztřídí tak, aby odlišnost závislostí atributů v třídách byla maximální ze všech  možných roztřídění. Je možné, že tento problém má exponenciální algoritmickou složitost. Nalezení suboptimálního řešení by však bylo vhodnou úlohou pro subsymbolické metody (neuronové sítě, genetické algoritmy).  
Literatura
[1]	BURIAN, Jan, RAUCH, Jan. Analysis of Death Causes in the STULONG Data Set. Dubrovník 22.09.2003 – 26.09.2003. In: BERKA, Petr (ed.). Discovery Challenge. Zagreb : IRB, 2003, s. 47–58. ISBN 953-6690-38-1.
[2]	Everitt B., Landau S., Leese M. Cluster Analysis. Oxford University Press. 2001. ISBN 0-340-76119-9.
[3]	Projekt LISp-Miner. http://lispminer.vse.cz 
[4]	EuroMISE centrum-Kardio, Projekt Stulong. http://euromise.vse.cz/stulong/

Summary: Classification as measuring difference between attribute dependencies
The aim of this article is to describe an alternative way how to understand a class of records according to the attribute dependencies between the classes. And to describe methods of determination of the best classification attribute using the analysis of attribute dependency in classes. Method of measuring attribute dependency class difference is described. Procedure of classification identification is described. In the end further possibilities of research are shown.