›
›

An information-theoretic metric based method for selecting clustering attribute

Download
Kỷ yếu Hội nghị Khoa học Quốc gia lần thứ IX “Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR'9)”; Cần Thơ, ngày 4-5/8/2016  
DOI: 10.15625/vap.2016.0005  
AN INFORMATION-THEORETIC METRIC BASED METHOD  
FOR SELECTING CLUSTERING ATTRIBUTE  
Pham Cong Xuyen, Đo Si Truong, Nguyen Thanh Tung  
Lac Hong University  
[email protected], [email protected].vn, [email protected]n  
ABSTRACT—Clustering problem appears in many different fields like Data Mining, Pattern Recognition, Bioinfor-matics, etc. The  
basic objective of clustering is to group objects into clusters so that objects in the same cluster are more similar to one another than  
they are to objects in other clusters. Recently, many researchers have contributed to categorical data clustering, where data objects  
are made up of non-numerical attributes. Especially, rough set theory based attribute selection clustering approaches for  
categorical data have attracted much attention. The key to these approaches is how to select only one attribute that is the best to  
cluster the objects at each time from many candidates of attributes.  
In this paper, we review three rough set based techniques: Total Roughness (TR), Min-Min Roughness (MMR) and Maximum  
Dependency Attribute (MDA), and propose MAMD (Minimum value of Average Mantaras Distance), an alternative algorithm for  
hierarchical clustering attribute selection. MAMD uses Mantaras metric which is an information-theoretic metric on the set of  
partitions of a finite set of objects and seeks to determine a clustering attribute such that the average distance between the partition  
generated by this attribute and the partitions generated by other attributes of the objects has a minimum value. To evaluate and  
compare MAMD with three rough set based techniques, we use the concept of average intra-class similarity to measure the  
clustering quality of selected attribute. The experiment results show that the clustering quality of the attribute selected by our  
method is higher than that of attributes selected by TR, MMR and MDA methods.  
Keywords— Data Mining, Hierarchical clustering, Categorical data, Rough sets, Clustering attribute selection.  
I. INTRODUCTION  
During the last two decades, data mining has emerged as a rapidly growing interdisciplinary field which merges  
together databases, statistics, machine learning and related areas in order to extract useful knowledge from data (Han  
and Kamber, 2006).  
Clustering is one of fundamental operations in data mining. It can be defined as as follows. Let  
{
}
                  be the set of   objects, where each   is an   dimensional vector in the given feature space. The  
 
 
 
 
clustering activity is to find clusters/groups of objects in such a way that objects within the same cluster have a high  
degree of similarity, while objects belonging to different clusters have a high degree of dissimilarity [6].  
Clustering problem appears in many different domains such as pattern recognition, computer vision, biology,  
medicine, information retrieval, etc. At present, there exist a large number of clustering algorithms in the literature.  
Types of clustering are divided broadly into hierarchical and non-hierarchical clustering. Non-hierarchical clustering  
methods create a single partition of the dataset optimizing a criterion function. Hierarchical clustering methods create a  
sequence of nested partitions of the dataset.  
Most of the earlier works on clustering has been focused on numerical data whose inherent geometric properties  
can be exploited to naturally define distance functions between data points. However, data mining applications  
frequently involve many datasets that also consist of categorical attributes on which distance functions are not naturally  
defined. Recently, clustering categorical data have attracted much attention from the data mining research community  
[1, 4, 7, 8, 11, 12, 14]. One of the techniques of categorical data clustering was implemented by introducing a series  
of clustering attributes, in which one of the attributes is selected and used to divide the objects at each time until all  
objects are clustered. To this, one practical problem is faced: for many candidates of attributes, we need to select only  
one at each time that is the best attribute to cluster the objects according to some predefined criterion.  
Recently, there has been works in the area of applying rough set theory to handle uncertainty in the process of  
selecting clustering attributes [7, 9, 11, 12]. Mazlack et al. [11] proposed a technique using the average of the  
accuracy of approximation in the rough set theory called total roughness (TR), where the higher the total roughness is,  
the higher the accuracy of selecting clustering attribute. Parmar et al. [12] proposed the MMR (Min–Min–Roughness)  
algorithm, which is a „„purity‟‟ rough set-based hierarchical clustering algorithm for categorical data. The MMR  
algorithm determines the clustering attribute by MR (Min–Roughness) criterion. However, as Herawan et al. has  
proven in [7], MMR is the complementary of TR and with this technique, the complexity is still an issue due to all  
attributes are considered to obtain the clustering attribute. In order to solve these problems, Herawan et al. [7] proposed  
a new technique called maximum dependency attributes (MDA), which is based on rough set theory by taking into  
32  
AN INFORMATION-THEORETIC METRIC BASED METHOD FOR SELECTING CLUSTERING ATTRIBUTE  
account the dependency of attributes of the database. According to Herawan et al. [7], MDA technique provides better  
performance than TR and MMR. However, there is an inherent similarity among TR, MMR and MDA, although they  
look different. The similarity lies that the values of the three techniques are all mainly determined by the cardinality of  
lower approximation of an attribute with respect to other attributes.  
In this paper, we review three rough set based techniques: Total Roughness (TR), Min-Min Roughness (MMR)  
and Maximum Dependency Attribute (MDA), and propose MAMD (Minimum value of Average Mantaras Distance),  
an alternative algorithm for hierarchical clustering attribute selection. MAMD uses Mantaras metric which is an  
information-theoretic metric on the set of partitions of a finite set of objects and seeks to determine a clustering  
attribute such that the average distance between the partition generated by this attribute and the partitions generated by  
other attributes of the objects has a minimum value. To evaluate and compare MAMD with three rough set based  
techniques, we use the concept of average intra-class similarity to measure the clustering quality of selected attribute.  
The experiment results show that the clustering quality of the attribute selected by our method is higher than that of  
attributes selected by TR, MMR and MDA methods.  
II. PRELIMINARIES  
In this section, some basic notions are briefly reviewed. In Section 2.1, we provide the basic concepts of rough set  
theory [13] and in Section 2.2 we describe Mantaras metric on the set of partitions of a finite set [10].  
A. Rough Set Theory  
An information system is a quadruple tuple                 , where   is a non-empty finite set of objects,   is a  
nonempty finite set of attributes,     
  where   is a set of all values of attribute  , and              is a  
    
⋃
    
 
 
function, called information function, that assigns value a             for every              .  
 
Definition 1. Let                  be an information system,      . Two elements          is said to be  -  
indiscernible in   if and only if                  , for every      .  
We denote the indiscernibility relation induced by the set of attributes   by       . Obviously,        is an  
equivalence relation and it induces unique partition (clustering) of  . The partition of   induced by        in  
[ ]  
                 denoted by   and the equivalence class in the partition   containing      , denoted by   .  
 
 
 
Definition 2. Let                  be an information system,       and      . The  -lower approximation of  ,  
denoted by      and  -upper approximation of  , denoted by     , respectively, are defined by  
    
{
| [ ]  
 
}
    
{
| [ ]  
 
}
        
            
    and             
(1)  
 
 
These definitions state that object        certainly belongs to  , whereas object        could belong to  .  
Obviously, there is             and   is said to be definable if        . Otherwise,   is said to be rough with B-  
    
boundary                 
 
Definition 3. Let                  be an information system,       and      . The accuracy of approximation of   
with respect to   is defined as:  
|  |  
    
    
 
    
 
|  |  
Throughout the paper, | | denotes the cardinality of  .  
        
Obviously,            . If          then        . The  -boundary of   is empty, and   is crisp with  
 
 
    
respect to  . If        , then        . The  -boundary of   is not empty, and   is rough with respect to  .  
 
Definition 4. Let                  be an information system,       and      . The roughness of   with respect to   
is defined as:  
    
|    |  
    
        
 
 
    
    
|    |  
Definition 5. Let                  be an information system. For         , it is said that   depends on   in a degree   
           , denoted by      , if  
 
∑
|    |  
| |  
 
    
    
    
Pham Cong Xuyen, Đo Si Truong, Nguyen Thanh Tung  
33  
B. Mantaras metric  
 
 
{
}
 
Definition 4. Let                be an information system,       and                   . The entropy of partition  
 
 
 
  is defined as:  
 
 
 
 
 
 
    
        ∑             
    
    
 
 
    
 
 
|
|⁄| |  
where           , and we define           .  
 
 
 
{
}
{
}
Definition 5. Let                  be an information system,                             , and                   .  
 
 
 
 
 
 
 
 
The conditional entropy of partition   with respect to partition   is defined as:  
 
 
 
 
 
|
 
 
          ∑  ( ) ∑  (  |  )     (  | )  
    
 
 
 
 
 
 
 
    
    
where  (  | )   |      |⁄| |,                and                     
 
 
 
 
 
{
}
{
}
Definition 6. Let                  be an information system,                             , and                   .  
 
 
 
 
 
 
 
 
The joint entropy of partitions   and   is defined as:  
 
 
 
 
 
 
            ∑ ∑  (     )     (     )  
    
 
 
 
 
 
 
 
        
⁄| |  
where  (     )   |     |   ,                and                     
 
 
 
 
From formulas (4) (5) and (6) we have:  
 
|
 
 
 
 
 
                      
 
    
    
 
 
 
 
Proposition 1. [10] The measure  
    
                        
 
 
 
|
 
 
|
 
 
 
 
 
is a metric on the set of partitions of  , that is, for any partitions       , and   on   it satisfies  
 
 
 
    
            and the equality holds iff       
        
(i)  
 
 
 
 
                  
 
(ii)  
(iii)  
 
 
 
    
                            .  
 
 
 
 
 
 
 
 
 
 
Note that, from formula (8), we can write:  
 
 
 
 
 
 
 
 
                               
 
     
 
 
 
 
 
III. THREE ROUGH SET-BASED TECHNIQUES  
Let                be an information system ,      ,       refers to the set of values of attribute   ,          
 
 
 
 
 
 
 
 
is a subset of objects having one specific value,  , of attribute   , that is,         is a class of objects induced by  
 
 
indiscernibility relation        ,           refers to the lower approximation, and           refers to the upper  
 
 
 
 
 
 
 
approximation with respect to   .  
 
A. TR (Total Roughness) Technique [11]  
Input: Dataset (information system)   without clustering attribute  
Output: Clustering attribute  
Begin  
Step 1: Compute the equivalence classes using the indiscernibility relation  
on each attribute.  
 
 
 
 
with respect to all  
Step 2: For each   determine its mean roughness       
 
 
 
  ,      , by the following formula  
 
|
|
      
 
∑
  |  
          
 
 
 
 
    
 
 
 
 
      
 
 
     
 
 
|
|
      
 
34  
AN INFORMATION-THEORETIC METRIC BASED METHOD FOR SELECTING CLUSTERING ATTRIBUTE  
where  
 
 
|        |  
 
 
 
 
|
 
 
 
           
     
 
 
 
|        |  
 
 
 
Step 3: For each       compute its total roughness with respect to   ,      , by  
 
 
the following formula  
|
|
 
∑
    
 
 
      
 
            
 
 
 
 
     
     
     
 
| |  
      
 
Step 4. Select the attribute   with the maximum value of TR as clustering  
 
attribute, i.e.  
 
           
{  (  )}  
 
     
 
 
End  
B. MMR (Min–Min-Roughness) Technique [12]  
Input: Dataset (information system)   without clustering attribute  
Output: Clustering attribute  
Begin  
Step 1: Compute the equivalence classes using the indiscernibility relation  
on each attribute.  
 
 
 
 
with respect to all  
Step 2: For each   determine its mean roughness       
 
 
 
  ,      , by the following formula  
 
|
|
      
 
∑
  |  
          
 
 
 
 
    
 
 
 
 
 
      
     
 
 
 
|
|
      
 
where  
 
 
|        |  
 
 
 
 
|
 
 
 
               
     
 
 
 
|        |  
 
 
 
 
 
 
Step 3: For each   determine its minimum roughness MR   by the following  
 
formula  
 
 
    
    
 
     
 
    
(        )  
     
     
 
             
 
 
Step 4. Select the attribute   with the minimum value of MR as clustering  
 
attribute, i.e.  
 
           
{  (  )}  
 
     
 
 
End  
C. MDA (Maximum degree of Dependency of Attributes) Technique [7]  
Input: Dataset (information system)   without clustering attribute  
Output: Clustering attribute  
Begin  
Step 1. Compute the equivalence classes using the indiscernibility relation  
on each attribute.  
Step 2. For each   determine the dependency degree of attribute   with  
 
 
respect to all   , where      . by the following formula  
 
∑
|   |  
⁄
      
 
 
 
 
 
 
 
 
 
     
 
| |  
 
 
 
Step 3. Select the maximum of dependency degree      of each attribute  
 
  (     ) as following  
 
 
Pham Cong Xuyen, Đo Si Truong, Nguyen Thanh Tung  
35  
 
 
    
    
 
     
 
    (    )  
     
 
             
 
 
Step 4. Select the attribute   with the maximum value of MD as clustering  
 
attribute, i.e.  
 
           
{  (  )}  
     
     
 
 
 
End  
IV. MAMD (MINIMUM AVERAGE MANTARAS DISTANCE) TECHNIQUE  
In this section we present MAMD technique, which is based on Minimum Average Mantaras Distance, to select  
clustering attribute.  
Definition 7. Let                  be an information system, and       is an attribute, the Average Mantaras Distance  
 
of   to all   ,      , is defined by the following formula:  
 
 
|
|
 
∑
  (      )  
 
 
 
        
 
 
 
 
      
     
 
| |  
      
where       are the partitions of   induced by         and         respectively.  
 
 
 
 
 
 
In the above definitions,   (      ) is a measurement to the distance between   and     From the view of  
 
 
 
 
 
 
 
 
clustering, the lower     is, the higher the crispness of the clustering. Based on the above definition, we present the  
MAMD algorithm as follows.  
Input: Dataset (information system)   without clustering attribute  
Output: Clustering attribute  
Begin  
Step 1. For each attribute         compute the equivalence classes of partition   
 
 
 
induced by indiscernibility relation        .  
 
Step 2. For each attribute       compute the condition entropy of partition   
 
 
 
with respect to partition   , where     :  
 
 
 
 
 
|
 
 
          ∑  ( ) ∑  (  | )     (  | )  
     
                 and  (  | )   |     |⁄| |,                
 
 
 
 
 
 
 
 
    
    
{
}
{
}
 
where                   
,
 
 
 
 
 
 
 
 
 
 
 
 
 
and                     
Step 3. For each every pair          , where      , compute the distance between  
 
 
two partitions   and   using Mantaras metric:  
 
 
 
 
  (      )     (  |  )     (  |  )  
     
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Step 4. For each attribute        compute the Average Mantaras Distance       
 
according to (22).  
Step 5. Select the attribute with the lowest     as clustering attribute.  
End  
Let us illustrate the MAMD algorithm by an example.  
Example. Table 1 shows Credit dataset as in [7]. There are ten objects with five categorical attributes: Magazine  
Promotion (MP), Watch Promotion (WP), Life Insurance Promotion (LIP), Credit Card Insurance (CCI), and Sex (S).  
First, we deal with attribute MP. The partition of   induced by attribute MP is:  
 
   
 {{1, 2, 4, 5, 7, 9, 10}, {3, 6, 8}}.  
We have:  
 
 
 
 
 
 
        
    
 
    
 
          
   
 
   
      
   
36  
AN INFORMATION-THEORETIC METRIC BASED METHOD FOR SELECTING CLUSTERING ATTRIBUTE  
The partition of   induced by attribute WP is:  
 {{1, 3, 5, 6, 7, 9}, {2, 4, 8, 10}}  
 
   
 
 
 
 
 
 
        
    
 
    
 
          
   
 
   
      
   
Table 1. The Credit dataset  
MP WP LIP CCI  
S
#
1
2
3
4
5
6
7
8
9
yes no  
yes yes yes  
no no no  
no  
no Male  
no Female  
no Male  
yes yes yes yes Male  
yes no yes  
no no no  
no Female  
no Female  
yes no yes yes Male  
no yes  
yes no  
10 yes yes yes  
no  
no  
no Male  
no Male  
no Female  
The partition of   induced by {MP,WP} is:  
 {{1, 5, 7, 9}, {2, 4, 10}, {3, 6}, {8}}  
 
{     }  
 
 
 
 
 
 
 
 
 ( {     })         
 
    
 
    
 
    
 
         
 
 
 
   
      
      
      
   
Applying Eq. (10), we get the distance between   and   as follows:  
   
   
 
 
 
 
 
 
          
   
        
    ( {     })       
      
      
   
With the same process, we can get the distance between MP and other attributes:  
 
 
 
    
                           
          
 
        
                 
       
 
The Average Mantaras Distance     of attribute MP can be computed by Eq.(22) as:  
                              
 
 
         
        
 
With the same process as MP, we can deal with other attributes . The     and      of all attributes are  
summarized in Table 2.  
Table 2. All values of distance and average distance between attributes in Table 1  
Distance (w.r.t….)  
Attribute  
    
MP  
WP  
LIP  
                        
0.000 1.722 1.678 1.902 1.786  
CCI  
S
MP  
WP  
LIP  
CCI  
S
0.000 1.840  
      
      
      
      
1.722 0.000 1.249  
1.678 1.249 0.000 1.351  
1.446  
       
1.412  
1.902 1.722 1.351 0.000 1.704  
From Table 2, we can see that attribute CCI has the smallest    ; therefore CCI is selected as clustering  
attribute using MAMD algorithm.  
V. COMPARISON TESTS  
A. clustering quality measure  
The four techniques TR, MMR, MDA and MAMD techniques use different methods for selecting clustering  
attribute. Measuring the clustering quality of selected attribute in a just manner is a non-trivial task. Since the goal of  
cluster analysis is to group data with similar characteristics, we use average intra-class similarity to measure the  
quality.  
Definition 8. Let                  be an information system and suppose that all attributes in   are categorical. Then  
the similarity between two objects   and   in   is defined as:  
 
 
Pham Cong Xuyen, Đo Si Truong, Nguyen Thanh Tung  
37  
{
}
 
 
 
|{       |                  }|  
 
 
 
 
 (      )   
     
 
 
| |  
 
Definition 9. Let                  be an information system. Suppose       is selected as clustering attribute and the  
 
{
}
clustering (partition) induced by   is                   where     {              |},                . The average  
|
    
 
 
 
 
 
 
 
      
 
similarity (  ) of object   with respect to other objects in   is defined as:  
   
 
|
|
 
 
∑
 (      )  
      
        
  (  )   
     
   
|
|
      
 
Definition 10. Let                  be an information system. Suppose       is selected as clustering attribute and the  
 
{
}
clustering (partition) induced by   is                   where     {              |} ,                . The intra-  
|
    
 
 
 
 
 
 
 
      
 
class similarity (  ) of cluster   is defined as:  
 
|
|
 
 
∑
  (  )  
   
    
 
 
 
     
     
 
|
 
 
|
Definition 11. Let                  be an information system. Suppose       is selected as clustering attribute and the  
 
{
}
clustering (partition) induced by   is                   where     {              |},                . The average  
|
    
 
 
 
 
 
 
 
      
 
intra-class similarity (   ) of clustering induced by   is defined as:  
 
 
∑
    
     
 
    
   (  )   
 
     
 
 
The higher the average intra-class similarity is the higher the clustering quality of the selected attribute.  
B. Datasets for testing and results  
The data sets of four test cases, as in [7], are presented in Table 1, Table 3, Table 4 and Table 5. These are Credit,  
Animal world, Parmar, and student‟s enrollment qualification data sets.  
Table 3. The animal world data set  
Animal  
Hair Teeth  
Eye  
Feather Feet Eat  
Milk Fly Swim  
Tiger  
Y
Y
Y
Y
N
N
N
N
N
pointed forward  
pointed forward  
N
N
N
N
Y
Y
Y
Y
N
claw meat  
claw meat  
hoof grass  
hoof grass  
claw grain  
Y
Y
Y
Y
N
N
N
N
N
N
N
N
N
N
N
Y
Y
N
Y
Y
N
N
N
Y
Y
N
N
Cheetah  
Giraffe  
Zebra  
blunt  
blunt  
N
side  
side  
Ostrich  
Penguin  
Albatross  
Eagle  
side  
N
side  
web  
fish  
N
side  
craw grain  
craw meat  
N
forward  
Viper  
pointed forward  
N
meat  
Table 4. The Parmar data set  
Rows  
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
Big  
Blue  
Hard  
Indefinite Plastic Negative  
Medium Red  
Small  
Moderate Smooth  
Yellow Soft Fuzzy  
Wood Neutral  
Plush Positive  
Plastic Negative  
4
Medium Blue  
Moderate Fuzzy  
5
Small  
Big  
Yellow Soft  
Green Hard  
Indefinite Plastic Neutral  
Smooth Wood Positive  
6
7
Small  
Small  
Big  
Yellow Hard  
Yellow Soft  
Indefinite Metal Positive  
Indefinite Plastic Positive  
8
9
Green  
Hard  
Smooth  
Wood Neutral  
Plastic Neutral  
10  
Medium Green  
Moderate Smooth  
38  
AN INFORMATION-THEORETIC METRIC BASED METHOD FOR SELECTING CLUSTERING ATTRIBUTE  
Table 5. The student‟s enrollment qualification data set  
Student Degree English Experience  
IT  
Maths Programming Statistics  
Medium  
1
2
PhD  
Good  
Good  
Good  
Good  
Good  
Good  
Good  
Good  
Good  
Good  
Good  
Good  
Medium Medium  
Medium Medium  
Medium Medium  
PhD  
M.Sc  
Good  
Medium  
3
4
Good  
Medium  
M.Sc  
Medium  
5
6
7
M.Sc  
M.Sc  
B.Sc  
Medium Medium  
Medium Medium  
Medium Medium Medium  
Medium Medium Medium  
Medium  
Medium  
Medium  
Medium  
Bad  
Medium Medium  
Medium Medium  
Good  
Good  
Good  
Good  
8
B.Sc  
Good  
We have installed all the four techniques TR, MMR, MDA and MAMD, in R programming language using  
RoughSets package.  
As the results of computations, Table 6 shows the clustering attributes chosen by the techniques in each data set.  
Table 6. Clustering attributes selected by the techniques in data set  
Datasets  
Credit  
CCI  
Animal  
Hair  
Parmar  
Var1  
Var1  
Var1  
Var2  
Student  
TR  
Experience  
Experience  
Experience  
Degree  
MMR  
MDA  
CCI  
Hair  
CCI  
Hair  
MAMD CCI  
Teeth  
From Table 6, we can see that for all the four considered data sets, three techniques TR, MMR and MDA choose  
same attribute as the clustering attribute. Our technique MAMD chooses same attribute CCI in Credit data set, but  
other attributes in Animal world, Parmar and Student‟s enrollment qualification data sets.  
Now, let us measure the clustering quality of attributes chosen by TR, MMR, MDA and MAMD in these three  
data sets.  
We take attribute Hair in Credit data set as an example to calculate the average intra-class similarity.  
The partition of   induced by attribute Hair consists of two equivalence classes:  
  =               {                              }  
 
                  {                                         }  
 
We take animal Tiger in   as an example to calculate the similarity, average similarity. Applying Eq. (25), we  
 
have  
                                                                           
Applying Eq. (26), the average similarity of Tiger with respect to other animals in   is calculated as follows:  
 
                   
 
 
           
        
 
With the same process, the similarity and average similarity of other animals in   are calculated and summarized  
 
as in Table 7.  
Table 7. The similarity,    and    of all animals in   induced by Hair  
 
Animal Tiger Cheetah Giraffe Zebra  
   
   
Tiger  
-
1.000  
-
0.444  
0.444  
-
0.444 0.630 0.630  
0.444 0.630  
Cheetah 1.000  
Giraffe 0.444  
0.444  
0.444  
1.000 0.630  
Zebra  
0.444  
1.000  
-
0.630  
Pham Cong Xuyen, Đo Si Truong, Nguyen Thanh Tung  
39  
Applying Eq. (27), the intra-class similarity of   is calculated below.  
 
                              
 
 
 
     
        
 
 
Using the same way, we obtain               .  
 
Lastly, using Eq. (28), the average intra-class similarity is calculated as follows:  
               
 
 
           
         
 
With the same process, we have computed the average intra-class similarity of clustering induced by Teeth in  
“Animal world”, by Var1 and by Var2 in Parmar, by Experience and by Degree in Student dataset. The computation  
results are given in Table 8.  
Table 8. The average intra-class similarity (   ) of clustering  
induced by attributes in the datasets  
Selected attributes and their     values  
Animal  
Hair 0.587  
Hair 0.587  
Hair 0.587  
Parmar  
Student  
TR  
Var1 0.536 Experience 0.638  
Experience 0.638  
Var1 0.536  
MMR  
MDA  
Experience 0.638  
Var1 0.536  
MAMD Teeth 0.784 Var2 0.555 Degree 0.770  
The results in Table 8 show that the clustering quality of attribute selected using MAMD technique is higher than  
that of attribute selected by TR, MMR and MDA techniques.  
VI. CONCLUSION  
In the recent years, some techniques applying rough set theory for selecting clustering attributes have been  
proposed. However, although they look different, there is an inherent similarity among them, and the computational  
complexity is still an issue.  
In this paper, we review three rough set based techniques: Total Roughness (TR), Min-Min Roughness (MMR)  
and Maximum Dependency Attribute (MDA), and propose MAMD (Minimum value of Average Mantaras Distance),  
an alternative algorithm for hierarchical clustering attribute selection. MAMD uses Mantaras metric which is an  
information-theoretic metric on the set of partitions of a finite set of objects and seeks to determine a clustering  
attribute such that the average distance between the partition generated by this attribute and the partitions generated by  
other attributes of the objects has a minimum value. To evaluate and compare MAMD with three rough set based  
techniques, we use the concept of average intra-class similarity to measure the clustering quality of selected attribute.  
The experiment results show that the clustering quality of the attribute selected by our method is higher than that of  
attributes selected by TR, MMR and MDA methods. The proposed approach could be integrated into clustering  
algorithm based on attributes selection for categorical data.  
REFERENCES  
[1] Barbara, D., Li, Y., Couto, J.: COOLCAT: an entropy-based algorithm for categorical clustering. In: Proc. of  
CIKM 2002, 582–589, 2002.  
[2] Cao F. Y., Liang J. Y. , Li D. Y., Bai L., A new initialization method for categorical data clustering, Expert  
Syst. Appl. 36, 10223–10228, 2009.  
[3] Ganti, V., Gehrke, J., Ramakrishnan, R.: CACTUS – clustering categorical data using summaries. In: Fifth  
ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 73–83, 1999.  
[4] Guha, S., Rastogi, R., Shim, K.: ROCK: a robust clustering algorithm for categorical attributes. Information  
Systems, 25(5), 345–366, 2000.  
[5] Huang, Z.: Extensions to the k-averages algorithm for clustering large datasets with categorical values. Data  
Mining and Knowledge Discovery, 2(3), 283–304, 1998.  
[6] Han J., and Kamber M., Data Mining: Concepts and Techniques, Morgan Kanufmann, 2006.  
40  
AN INFORMATION-THEORETIC METRIC BASED METHOD FOR SELECTING CLUSTERING ATTRIBUTE  
[7] Herawan, T., Deris, M. M., Abawajy, J. H.: A rough set approach for selecting clustering attribute. Knowledge-  
Based Systems 23, 220–231, 2010.  
[8] Jain A. K., Data clustering: 50 years beyond k-averages, Pattern Recogn. Lett., 31(8), 651–666, 2010.  
[9] Jyoti Dr., Clustering categorical data using rough sets: a review. International Journal of Advanced Research  
in IT and Engineering, Vol. 2, No. 12, December, 30-37, 2013.  
[10] Lopez de Mantaras R., A Distance-Based Attribute Selection Measure for Decision Tree Induction. Machine  
Learning, 6, No 1, 81-92, 1991.  
[11] Mazlack, L. J., He, A., Zhu, Y., Coppock, S.: A rough set approach in choosing clustering attributes. In:  
Proceedings of the ISCA 13th International Conference (CAINE 2000), 1–6, 2000.  
[12] Parmar, D., Wu, T., Blackhurst, J.: MMR: an algorithm for clustering categorical data using rough set theory.  
Data and Knowledge Engineering, 63, 879–893, 2007.  
[13] Pawlak, Z.: Rough sets. International Journal of Computer and Information Science, 11, 341–356, 1982.  
[14] Suchita S. Mesakar, M. S. Chaudhari, Review Paper On Data Clustering Of Categorical Data. International  
Journal of Engineering Research & Technology, Vol. 1 Issue 10, December, 2012.  
MỘT PHƯƠNG PHÁP LỰA CHỌN THUỘC TÍNH GOM CỤM  
SỬ DỤNG METRIC LÝ THUYẾT THÔNG TIN  
Phạm Công Xuyên, Đỗ Sĩ Trường, Nguyễn Thanh Tùng  
TÓM TẮT — Bài toán gom cụm dữ liệu xuất hiện trong nhiều lĩnh vực khác nhau như Khai thác dữ liệu, Nhận dạng, Tin-sinh học,  
vv. Mục tiêu cơ bản của gom cụm là nhóm đối tượng thành các cụm sao cho các đối tượng trong cùng một cụm thì tương tự như  
nhau hơn là các đối tượng từ các cụm khác nhau. Gần đây, nhiều nhà nghiên cứu quan tâm đến vấn đề gom cụm dữ liệu phạm trù  
(categorical), trong đó các đối tượng dữ liệu được mô tả bởi các thuộc tính không phải thuộc tính số. Đặc biệt, phương pháp tiếp  
cận sử dụng lý thuyết tập thô trong gom cụm phân cấp (hierarchical) dữ liệu phạm trù đã thu hút nhiều sự chú ý. Chìa khóa của các  
phương pháp này là làm thế nào để chọn được một thuộc gom cụm tốt nhất tại mỗi thời điểm trong số nhiều thuộc tính ứng viên.  
Trong bài báo này, chúng tôi xem xét ba kỹ thuật dựa trên lý thuyết tập thô: Total Roughness (TR), Min-Min Roughness (MMR) và  
Maximum Dependency Attribute (MDA), và đề xuất MAMD (Minimum value of Average Mantaras Distance), một thuật toán mới  
cho việc lựa chọn thuộc tính phân cụm theo tiếp cận phân cấp. MAMD sử dụng metric Mantaras, một metric lý thuyết thông tin trên  
tập các phân hoạch của một tập hợp gồm hữu hạn các đối tượng và tìm cách xác định thuộc tính gom cụm sao cho khoảng cách  
trung bình giữa phân hoạch sinh ra bởi thuộc tính này và các phân hoạch sinh ra bởi các thuộc tính khác đạt giá trị nhỏ nhất. Để  
đánh giá và so sánh MAMD với ba kỹ thuật dựa trên lý thuyết tập thô, chúng tôi sử dụng khái niệm “Độ tương tự trung bình bên  
trong cụm” của một phép gom cụm để đo lường chất lượng gom cụm của thuộc tính được chọn. Kết quả thực nghiệm cho thấy chất  
lượng gom cụm của thuộc tính chọn được bằng phương pháp của chúng tôi là cao hơn so với các thuộc tính chọn bởi các phương  
pháp TR, MMR và MDA. Do đó, MAMD có thể được sử dụng như là một kỹ thuật hiệu quả lựa chọn thuộc tính trong phân cụm  
phân cấp.  
Từ khóa — Gom cụm, Lý thuyết tập thô, Lựa chọn thuộc tính, Mantaras metric, Gom cụm phân cấp.  
pdf 10 trang yennguyen 12140 Free
Download
Bạn đang xem tài liệu "An information-theoretic metric based method for selecting clustering attribute", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfan_information_theoretic_metric_based_method_for_selecting_c.pdf