Rough ISODATA Algorithm

Introduction

In machine learning studies, practitioners come across data sets of varying nature thereby making it necessary to develop specialized methodologies for extracting hidden information in the data set. Broadly speaking, objects in the data set may possess random, fuzzy or rough characteristics. Randomness comes into picture when uncertainty is present in the values assumed by objects in the dataset. For example, in datasets related to responses of patients, in the process of recovery from illness one can see lot of uncertainties due to various random factors, even though they receive the same type of treatment. Fuzziness comes into picture when impreciseness exists in the form of vagueness in the values assumed by the variables. For example, the laboratory measurements with respect to different diagnostic tests can hardly be treated as crisp values and in practice, they are usually of imprecise nature. Very rarely, one can get the exact status of a person with respect to the variables of these kinds because the environment in which they are recorded influences the experimental values. To deal with these kinds of fuzzy data sets machine-learning researchers use the theory of fuzzy sets developed by Zadeh (1965). Interesting discussion on this aspect can be found in Azar (2010). The third type of data namely rough data arises in the form of coarseness. For example, two individuals may possess the same set of attributes but belong to different classes for which no proper explanation can be given. Examples of such datasets can be found in Pawlak (1982).

The idea of using rough sets in cluster analysis was initially proposed by Lingras, Yan and West (2002) in which a comparative study on conventional and rough k-means clustering had been carried out. Following this, Lingras and West (2004) considered an application of rough k-means for clustering of web users. Mitra (2004) considered an evolutionary solution for rough k-means clustering. Further studies in relation to rough k-means clustering have been carried out by Peters and Borkowski (2004), Peters (2005, 2006), Peters and Lampart (2006) and Peters, Lampart and Weber (2008). Lingras and Peters (2012) described how a core concept of rough sets, the lower and upper approximation of a set, can be used in clustering. In their work, rough clusters were shown to be useful for representing groups of highway sections, web users, and supermarket customers. A main limitation of these works is that the application of rough k-means algorithm requires the knowledge of k, namely the number of clusters. This paper provides a solution for this limitation. An algorithm similar to the ISODATA algorithm of Ball and Hall (1967) is proposed for creation of rough clusters without actually assuming the value of k. It is to be noted that fuzzy relative of the ISODATA algorithm was developed by Dunn (1973) and another related work based on a technique called Probabilistic relaxation labelling was also studied by Lam (1996).

The paper is organized as follows: The paper begins with brief descriptions of crisp k-means and fuzzy k-means. In order to enhance the readability of the paper it is followed by a complete detailed description on rough k-means clustering algorithm due to Lingras et al (2002). The paper introduces a new rough clustering algorithm, namely, rough ISODATA algorithm and the concluding section discusses the outcome of the experimental studies carried out with the help of real life data sets to study the efficiency of the proposed algorithm.