Transcript The proposed ART-like clustering algorithm

A hierarchical approach to ARTlike Clustering Algorithm
Author : Mu-Chun Su
Yi-Chun Liu
Graduate : Chien-Ming Hsiao
Outline

Motivation
Objective
Introduction

The proposed ART-like clustering algorithm

Conclusion

Personal Opinion


Motivation

Two crucial problems for most of
clustering algorithm
1.
2.
The determining of the optimal number of
clusters
The determining of the similarity measure base
on which patterns are assigned to
corresponding clusters
Objective

Propose a hierarchical approach to ART-like
clustering algorithm which is able to deal with
data consisting of arbitrarily geometrical-shaped
clusters

Feasible solution to the two problems of determining
the number of clusters and clustering
Introduction (1/2)
Cluster validity problem



The estimation of the number of clusters in the data set
To solving the cluster validity problem usually
involves
(1) increasing the number of clusters
(2) merging the existing cluster

computing some certain cluster validity measures in each
run, until partition into optimal number of clusters is
obtain
Introduction (2/2)




It is easy to consider the idea of a data cluster on a rather
informal basis
It is very difficult to give a formal and universal
definition of a cluster.
Most of the conventional clustering methods assume
that patterns having similar locations or constant density
create a single cluster
Different similarity measures will result in different
clustering results
The proposed ART-like clustering
algorithm

The adaptive resonance theory (ART) networks
are able to cluster data without pre-specifying the
number of clusters.


The vigilance parameter to some extent implicitly prespecifies
How much confidence do we have on the
clustering results created by ART networks ?
The proposed ART-like clustering
algorithm

Hierarchical clustering method



Agglomerative
Divisive
To use the advantage provided by a dendrogram to
increase our confidence on selecting a more
trustable clustering results created by ART-like
clustering algorithm
The proposed ART-like clustering
algorithm
Fig.1 The idea of using of a set of ellipses to approximate
an arbitrarily-shaped cluster
The proposed ART-like clustering
algorithm

Adopt the neurons with quadratic neuron-type
junctions


To cluster data into hyperellipsoids
The output of a quadratic neuron indicates the
similarity between the present input and the prototype
of the hyperellipsoid embedded in the synaptic
weights of the neurons
The proposed ART-like clustering
algorithm

The output of a quadratic neuron is computed by
using the following equations :
n
y jk  x    w jki xi
i 1
net j  x     y jk  x   b jk 
n
2
k 1
Out j  x   e
 s j 2 net j  x 
where b jk , s j , and w jki are adjustable weights, x  x1 ,, xn  is an input pattern,
T
y j   y j1 ,, y jn  is the transform ed version of the input pattern x, and Out j x 
T
is the output function of neuron j
The proposed ART-like clustering
algorithm

Stage one : generate a single-layer neural
network


Step 1.1 : specify the initial value of the vigilance parameter and
corresponding parameters
Step 1.2 : if the present input pattern is the first pattern then generate a
quadratic neuron whose weights are initialized
b1 0  x
1 if k  i
w1ki 0  
0 o.w

Step 1.3 find the wining neuron j among the neurons generated in the
network, using the following criterion:
*
j *  j  arg min Out j x 
j 1,, J
The proposed ART-like clustering
algorithm

Step1.4 : if the output of the winning neuron is larger than
the threshold. Then adjust the synaptic weights of the
winning neurons
b jk new  b jk old   b 2s 2j Out j x  y jk x   b jk 
w jki new  w jki old    w  2s 2j Out j x  y jk x   b jk xi 
otherwise, a new quadratic neuron is generated and
initialized as follows:
b1 0  x
1 if k  i
w1ki 0  
0 o.w

Step 1.5 : present next data pattern into the network and
repeat steps 1.3-1.4 until all data patterns are processed.
The proposed ART-like clustering
algorithm

Stage two : generate a dendrogram for the generated
neural network

Step 2.1: set the cycle number k to be 0, determine the value
of a real-valued constantαwhose value is in the range (0,1),
and initialize an N * J matrix E to be a zero matrix.
Step 2.2: fill out the elements in the matrix E
k+1

k+1
 1 if Out j x i    k 1
eij  
0 o.w.

for 1  i  N ,1  j  J
Step 2.3: find so-called equivalent sets by examining the
matrix E
Step 2.4: Increase the value of k by one and repeat steps 2.22.3 until the number of cycles reaches a pre-specified limit
or the number of equivalent sets, N , becomes just one.
k+1

K 1
e
The proposed ART-like clustering
algorithm
The proposed ART-like clustering
algorithm
Conclusion


Utilize the dendrogram to help us to
visually select believable clusters and
clustering.
Any clustering result must be viewed with
extreme suspicion since the performance of
most of the clustering algorithms more or
less depends on some parameters.
Personal Opinion

No clustering algorithm can claim it works
perfectly for any application.