Unsupervised clustering and feature discrimination with application to image database categ

Unsupervised Clustering and Feature Discrimination with Application to

Image Database Categorization

Hichem Frigui', Nozha Boujemaa2, and Soon-Ann Lim'

Department of Electrical & Computer Engineering

University of Memphis Memphis, TN 38152

{ hfrigui,salim} @memphis.edu

INRIA Rocquencourt

Domaine de Voluceau BP105 Rocquencourt

78153 Le Chesnay Cedex, France

Nozha.Boujemaa@inria.fr

Abstract

We introduce a new algorithm that performs clustering

and feature weighting simultaneously and in an unsu-

pervised manner. The clustering approach is based on

a model of mutual synchronization of pulse-coupled OS- cillators. The feature set is divided into logical subsets

of features, and a degree of relevance is dynamically assigned to each subset based on its partial degree of

similarity. The performance of the proposed algorithm

is illustrated by using it to categorize a collection of im-

ages using three sets of features. '

1. Introduction

When clustering in a high dimensional feature space, as

in the case of image database categorization, the influ-

ence of the features is generally not equally important in the definition of the category to which similar patterns

belong. For instance, shape features are highly relevant

for a class of images of mechanical parts, while texture and color features are irrelevant. If we treat all features

equally, we cannot obtain a meaningful description of a

given class of images.

Several methods have been proposed for feature selec-

tion and weighting [ 1, 14, 181. In feature selection, the

task's dimensionality is reduced by completely elimi-

nating irrelevant features. This amounts to assigning bi- nary relevance weights to the features. Feature weight-

ing is an extension of the selection process where the

features are assigned continuous weights which can be

regarded as degrees of relevance. Continuous weight-

ing provides a richer feature relevance representation. Therefore, it tends to outperform feature selection from

an accuracy point of view in tasks where some features are useful but less important than others. Most fea-

ture weighting (and selection) methods assume that fea-

ture relevance is invariant over the task's domain, and

hence learn a single set of weights for the entire data

set. This assumption can impose unnecessary and per- nicious constraints on the learning task when the data

set is made of different categories or classes which are

expected to have different sub-structures. If the data is

labeled, then it is possible to apply a feature weight-

ing algorithm to each class independently, and learn a

different set of weights. On the other hand, if the data

set is unlabeled, then existing feature weighting algo-

rithms cannot be used to learn cluster dependent feature

weights. In this case, one possible solution is to per-

form clustering using a covariance matrix induced met-

ric. The learned variance of each feature can be used to

assign a degree of relevance. Unfortunately, learning a

relevance weight for each feature may lead to poor gen-

eralization. This is because most of the detected clusters tend to have only a few relevant features.

In this paper, we propose an algorithm that performs clustering and feature weighting simultaneously. This

algorithm is an extension of our recently introduced

clustering algorithm called Self-organization of Oscil-

lators Network (SOON). The feature set is divided into

logical subsets of features, and a degree of relevance is

dynamically assigned to each subset. In each iteration,

we first compute a partial degree of similarity for each

subset of features. Then, based on these values, a degree

of relevance is assigned to each subset. The basic idea is to assign larger weights to subsets with smaller dis- tances since they are considered more reliable. Finally,

0-7803-7@78-3/0U$l0.00 (C)u)ol IEEE Page: 401

the partial degrees of similarity and their weights are ag-

gregated to generate an overall degree of similarity. We

investigate two techniques to assign a relevance weight.

The first one is based on a fuzzy membership degree,

and the second one is based on the ordered weighted

averaging operator (OWA).

The rest of the paper is organized as follows. In sec-

tion 2, we review relevant literature. In section 3, we

present our algorithm. In section 4, we illustrate the per-

formance of the proposed algorithm by using it to cate- gorize a collection of images. Finally, section 5 contains

the summary conclusions.

2. Background

2.1. Feature Discrimination

Feature selection and weighting techniques generally

rely on a criterion function and a search strategy. The