Classification as measuring difference between attribute dependencies 
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

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.
1.	Class as dependence of attributes
Typical problem of unsupervised learning is to classify records of a database table when there is given no classification attribute. The aim of this article is to describe an alternative way how to understand a class of records and to describe methods of determination the best classification attribute.
 Classical notion of records classification relies on representation of records as points in an abstract space of attributes. Classes are then represented as clusters of these points. There is large theory about constructing clusters and appropriate metrics of abstract spaces of attributes (measures of similarity of records), see [2] for example.
This concept of class is intuitive but it doesn’t involve the global relations (dependencies) in the dataset, namely when we are dealing with nominal attributes where no ordering of values exists. The classical concept of class could prevent us from discovering if there is some considerable degree of interactions between events represented by records.
Alternatively we can understand a class of attributes as a set of records with certain characteristics of relations between attributes (instead of relations between set of individual records). We will determine these characteristics from dependencies of couples of attributes. 
Let V be the set of all attributes of the database table. Let C  V be the candidate for the classification attribute and C1,C2 … Ck be the categories (classes) of this attribute. Let denote AD(A,S|Ci) the conditioned dependency of attributes for every A,S  V; A  S; A,S  C. AD(A,S|Ci) can be some characteristics of dependency between attributes A and S in class given by Ci. Attribute dependency could be obtained by given by a statistics like χ², Kendall’s tau, Cramers’s V etc. appropriate for given types of attributes. 
We will deal with categorical attributes only. The basis for determination of attribute dependency is the contingency table. Contingency table is given by the attribute whose categories are in rows (attribute A), the attribute whose categories are in columns (attribute S) and attribute whose categories are the condition which the records must satisfy (attribute C, in our case we understand its categories C1,C2 … Ck as classes of records). We denote such contingency table T(A,S,C)

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	

There fi,j denotes number of records satisfying the condition Ci and at the same time the value of attribute A is ai and value of attribute S is sj.  Categories of the attribute C divide the set of all records into classes, where there could be different dependencies between attributes A and S.

An example of a system able to generate dependencies between two attributes (or two groups of attributes) according to a given condition (represented by the categories of the third attribute) is the procedure KL-Miner, part of the datamining system LISp-Miner [2, 3]. There are generated triplets of attributes and statistics of the relevant contingency tables according to the so called KL-quantifier. KL-quantifier determines which statistics is used and which values of the statistics are significant. For our purposes we could set the KL-Miner to generate all of the possible triplets of attributes. 

Let the difference between the classes of  records (given by the categories of the attribute C) be determined by the difference between the attribute dependencies between the classes. Then categories of various attributes (candidates for classification attribute)  will divide records into classes with various differences between the attribute dependencies. Attributes whose categories divide records into classes with low differences between the attribute dependencies discover no new knowledge. Attribute whose categories divide records into classes with highest differences between the attribute dependencies will be determined as the classification attribute. 

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.	Difference between attribute dependencies in classes
There are many ways how to determine the difference between attribute dependencies in classes (in short Attribute Dependencies Class Difference, ADCD). We will describe only one. 
Dependency of attributes in different classes could we understand as a point in a abstract space (note that this space is quite different to the classical space of attributes) where dimensions are represented by dependencies in particular classes. For k classes this space have k dimensions. ADCD could be understand as a function of angle  between the vector of the attribute dependencies for all classes (AD(A,S|C1), AD(A,S|C2), … AD(A,S|Ck)) and the vector with unit coordinates. For two dimensions we can draw a simple graph.

Fig. 1. Vector of dependency between attributes A,S in classes C1 and C2

When AD(A,S|C1)=AD(A,S|C2) then angle  is zero. This means that dependency between attributes A and S is not conditioned by attribute C.  

For expression of ADSD is appropriate to use cosine of the angle , which can be easily computed as a value of scalar product of vector (AD(A,S|C1), AD(A,S|C2),… AD(A,S|Ck)) and vector with unit coordinates divided by product of their lengths. 
The difference between attribute dependencies in classes, ADCD, is then the sum of cosines of angles  for different combinations of A nad S.  

!Unexpected End of Formula

Note. Because of of the vecor is with unit coordinates, scalar product in the numerator is only product of the elements of vector (AD(A,S|C1), AD(A,S|C2) … AD(A,S|Ck)). Constant factor  in the denominator is the length of the vector with unit coordinates with dimension k. 
When the values of the elements of vector (AD(A,S|C1), AD(A,S|C2) … AD(A,S|Ck)) will be positive then the range of ADCD will be <; 1>. Note that in k-dimensional space is the deviation between the vector with unit coordinates and vector with only on non-zero coordinate greater than 45°. In 2-dimansional space will be the range ADCD   <;1>). 
When the values of the elements of vector (AD(A,S|C1), AD(A,S|C2) … AD(A,S|Ck)) will be positive and negative (typically for asymmetric dependencies) then the range of ADCD will be <0;1>. 
For zero vector (AD(A,S|C1), AD(A,S|C2) … AD(A,S|Ck)) we will define ADCD = 1. 
 
From properties of the function cosine follows that the smaller is ADCD the greater is  the difference between attribute dependencies in classes. Maximum difference between attribute dependencies in classes has the attribute with minimum ADCD .
3.	Procedure of determination of the classification attribute
We assume the database is ready to analysis and we work only with relevant attributes. The procedure of determination of classification attribute with maximum difference between attribute dependencies in classes follows:
1.	For every candidate for classification attribute C divide the database in classes according to categories C1,C2 … Ck. 
2.	 For these classes determine maximum difference between attribute dependencies in classes (ADCD) for all couples of relevant attributes. 
3.	The classification attribute has the maximum difference between attribute dependencies in classes. 
4.	Conclusion and further r development 
Understanding classes of records as a set of records with different characteristics of attribute dependencies helps to analyze datasets with no or minimal preliminary knowledge and where we suppose high degree of simultaneous interactions between events represented by records. This is for example the case of microarray datasetets (the expression levels of the particular genes are in records). 
Software able to compute ADCD from attribute dependencies is currently developed on University of economics Prague. It’s based on attribute dependenice generated by procedutre KL-MInber a part of acadenmic datamining system Lisp-Miner. 
The system KL-Miner can also generate dependencies not only between two attributes but between two conjunctions of literals representing  particular categories of many attributes. Similarly could be represented the classes. 

Literatura
[1]	Everitt B., Landau S., Leese M. Cluster Analysis. Oxford University Press. 2001. ISBN 0-340-76119-9.
[2]	Projekt LISp-Miner. http://lispminer.vse.cz 
[3]	Rauch, J. – Šimůnek, M. – Lín, V.: Mining for Patterns Based on Contingency Tables by KL-Miner – First Experience. In: LIN, Tsau Young, HU, Xiaohua, OHSUGA, Setsuo, LIAU, C. J. (ed.). Data mining – Foundations and New Directions in Data Mining. Melbourne: IEEE Computer Society, 2003, pp. 156–163.

Summary:
Cognitive inspiration for unsupervised learning using the attribute dependency.
The first chapter describes some inspirations of cognitive science applied in artificial intelligence. On the basis of neurophysiological discoveries of holistic nature of knowledge representation in brain there have been formulated new approach to the classification of database records. The rest of the paper shows methods of identification of the classification attribute using the analysis of attribute dependency in classes. Methods of measuring attribute dependency class difference are described. Procedure of classification identification is described. In the end further possibilities of research are shown.