Information Sciences 408 (2017) 129–145
Contents lists available at ScienceDirect
Information Sciences journal homepage: www.elsevier.com/locate/ins
Axiomatic generalization of the membership degree weighting function for fuzzy C means clustering: Theoretical development and convergence analysis Arkajyoti Saha a, Swagatam Das b,∗ a b
Stat-Math Unit, Indian Statistical Institute, 203 B.T.Road, Kolkata 700108, West Bengal, India Electronics and Communication Sciences Unit, Indian Statistical Institute, 203 B.T.Road, Kolkata 700108, West Bengal, India
a r t i c l e
i n f o
Article history: Received 11 April 2016 Revised 1 March 2017 Accepted 21 March 2017 Available online 10 April 2017 Keywords: Fuzzy clustering Generalized weighting function CMWF Convergence analysis
a b s t r a c t For decades practitioners have been using the center-based partitional clustering algorithms like Fuzzy C Means (FCM), which rely on minimizing an objective function, comprising of an appropriately weighted sum of distances of each data point from the cluster representatives. Numerous generalizations in terms of choice of the distance function have been introduced for FCM since its inception. In a stark contrast to this fact, to the best of our knowledge, there has not been any significant effort to address the issue of convergence of the algorithm under the structured generalization of the weighting function. Here, by generalization we mean replacing the conventional weighting function uij m (where uij indicates the membership of data xi to cluster Cj and m is the real-valued fuzzifier with 1≤ m < ∞) with a more general function g(uij ) which can assume a wide variety of forms under some mild assumptions. In this article, for the first time, we present a novel axiomatic development of the general weighting function based on the membership degrees. We formulate the fuzzy clustering problem along with the intuitive justification of the technicalities behind the axiomatic approach. We develop an Alternative Optimization (AO) procedure to solve the main clustering problem by solving the partial optimization problems in an iterative way. The novelty of the article lies in the development of an axiomatic generalization of the weighting function of FCM, formulation of an AO algorithm for the fuzzy clustering problem with the extension to this general class of weighting functions, and a detailed convergence analysis of the proposed algorithm. © 2017 Elsevier Inc. All rights reserved.
1. Introduction Clustering is the unsupervised grouping or partitioning of a collection of patterns based on some similarity or dissimilarity measure and without any prior knowledge of the class labels. Each pattern or data point is represented as a vector of measurements or a point in some multi-dimensional space. Most often the unlabeled patterns are classified in such a way, that the patterns belonging to the same cluster (same label) are more similar to each other than they are to the patterns belonging to the other clusters [47]. A clustering algorithm is expected to learn the correct labels of the patterns for well-defined subgroups in the data. The absence of any kind of training dataset makes this method different from that of ∗
Corresponding author. E-mail addresses: arkajyotisaha93@gmail.com (A. Saha), swagatam.das@isical.ac.in, swagatamdas19@yahoo.co.in (S. Das).
http://dx.doi.org/10.1016/j.ins.2017.03.024 0020-0255/© 2017 Elsevier Inc. All rights reserved.
130
A. Saha, S. Das / Information Sciences 408 (2017) 129–145
supervised learning. Clustering has been extensively studied across varied disciplines like decision-making, exploratory data analysis, taxonomy, data mining, information retrieval, social network analysis, and image interpretation [26,27]. Data clustering algorithms come in two primary categories: hierarchical and partitional [27]. This paper focuses on the partitional clustering algorithms which directly organize the data into a set of clusters by optimizing some criterion function(e.g. a squared-error function indicating the intra-cluster spread). Both the local and global structures in the data can be reflected by the criterion function. The local structures may be emphasized by assigning clusters to the weighted mean of the data points. On the other hand, the global criteria usually involve minimizing some measure of dissimilarity in the objects within each cluster while maximizing the dissimilarity across different clusters. Partitional clustering algorithms can be either hard or fuzzy. In fuzzy clustering, clusters are treated as fuzzy sets and each pattern has a membership (in [0, 1]) of belonging to each cluster, rather than completely belonging to any one cluster as is the case for hard clustering. A cluster is represented by a vector prototype or quantizer, also commonly known as a cluster representative in the literature. Each data point is assigned a membership degree in each cluster, based on their similarity with the corresponding cluster representatives. FCM and its variants try to shift the representatives towards the actual centers of the regions (clusters) with a high aggregation of data points by minimizing the appropriately defined cost functions [46]. The formulation of the objective function of a fuzzy clustering algorithm consists of two parts. First one is the choice of the distance function, i.e. a way of measuring the level of dissimilarity between a pair of points. The second one is the weight or the importance of the dissimilarity between the ith point and the cluster representative of the jth cluster in the objective function. This weight or importance is expressed in terms of a suitable weighting function of the membership degree of the ith data point to the jth cluster; the higher the membership, higher is the weight. Fuzzy C-Means (FCM) is the most representative fuzzy partitional clustering algorithm till date. It was first introduced by Dunn [14] and subsequently generalized by Bezdek [6] by generalizing the fuzzifier value in the range [1,∞). Due to its natural ability to handle overlapping clusters, a lot of research efforts have been put into FCM and similar clustering algorithms. There have been a plethora of literature on the generalization of the conventional FCM algorithm in terms of the dissimilarity measure or the distance function used [4,9,22,30,34,35,42,45]. Convergence properties of the Alternative Optimization (AO) of FCM [7] and its variants have been extensively investigated for various distance functions including the conventional Euclidean distance. Some notable works in this direction can be found in [19,21,23]. Recently Fazendeiro and de Oliveira [15] reported the convergence analysis of an FCM variant (called FCM with the focal point) for an observer-biased clustering framework which aims at generating a reasonable set of clusters corresponding to different levels of granularity in different regions of the data space. Chaomurilige et al. [11] analytically investigated the optimal parameter selection of the GK (Gustafson Kessel) clustering algorithm, which is a variant of FCM derived by replacing the Euclidean distance with the Mahalanobis distance. Several cluster validity functions have also been investigated in conjunction with FCM to estimate the number of clusters, see, for example, recent works like [31,44]. Recently Saha and Das [41] reformulated the FCM algorithm with a separable geometric distance measure and theoretically demonstrated the robustness of the same towards noise feature perturbations. In contrast to the volume of analytical studies on the properties of FCM with various distance functions, there exists very few articles addressing the generalization of the membership degree weighting function. Generalization, in this context, essentially means using a more flexible function g (uij ) of the membership degree uij of the ith data point xi to belong to the jth cluster Cj . The weighting function g(uij ) is used to find out the weight of the distance of data point xi from cluster prototype zj in the objective function of FCM. We will present this notion more formally in Section 2. Note that the conventional form of FCM assumes g(ui j ) = ui j m , where m is the so-called fuzzifier and 1≤ m < ∞. m determines the degree of overlap among the clusters and also helps in convexifying the objective function. There are some works proposing and justifying a few intuitive variations of the membership degree weighting function in FCM [28,29], but as far as our knowledge is concerned, no convergence analysis is available for those variations of FCM. Yu et al. [49] took an analytical approach to select the proper fuzzifier m for conventional FCM by exploiting a relation between the fixed points of FCM and the dataset itself. Ganguly et al. [18] used a multi-dimensional membership vector for each data point replacing the traditional, scalar membership value defined in the original FCM. However, they preserved the conventional form of the membership degree weighting function. Thus, while use of the generalized dissimilarity measures in FCM and the corresponding convergence analyses attracted so much attention in recent past, why is it exactly the opposite case, regarding the weighting function? What might be the possible reasons behind the fact that, after Bezdek [6] proposed a generalization of [14] in terms of the fuzzifier, there does not exist any significant literature regarding further generalization of the weighing function while preserving the convergence properties of FCM? We point out a couple of reasons, that may provide some insight into the matter: 1. First, development of various distance measures (between two points in a space or between two probability measures), is a question of independent interest and has a plethora of literature of its own [10,12,13,33]. Hence, a generalization of clustering process in terms of dissimilarity measure is always backed by the theory behind the development of that distance measure in the first place. On the other hand, there exists no such literature regarding the generalization of the weighting function, because, this is an issue, only relevant for the fuzzy clustering problems. Hence, there does not exist axiomatic approach towards the development of generalized membership degree weighting functions. 2. As far as the convergence analysis is concerned, there is a major road block in the generalization of a fuzzy clustering algorithm in terms of the weighting function. Whenever a new distance function is developed, development of its center
A. Saha, S. Das / Information Sciences 408 (2017) 129–145
131
or population minimizer [39] i.e. the minimizer of the weighted sum of a group of points from a particular point, is an intrinsic part of it [3,5,37,38]. This plays a pivotal role in the convergence analysis of fuzzy clustering algorithms with general distance measures. For the reason mentioned above, there is no such existing literature regarding the weighting function, as the optimization problem is not even defined in any framework, other than fuzzy clustering. In this work, we analytically investigate the use other permissible forms of the membership degree weighting function so that the algorithm may possess some additional degrees of freedom (in terms of choosing this function) besides enjoying the strong local convergence properties of FCM. The contributions of the article can be summarized in the following way: 1. We develop an axiomatic approach of generalization of the membership degree weighting function for FCM. We provide intuitive justification of the axiomatic development. We also discuss some common examples of this general class of weighting functions, which includes the common function (um ) already existing in the literature. ij 2. We propose a general class of fuzzy clustering problems with the extension of the generalized weighting functions and present an AO based clustering algorithm for the clustering purpose. Here, we also demonstrate that the previous attempts of intuitive generalization of this function [28,29] can be derived as special cases of the proposed generalization. 3. We discuss the issues like the existence and the uniqueness of solutions of the optimization problems underlying the AO algorithm and carry out a full-fledged convergence analysis to obtain a similar convergence property as that of the conventional FCM. Organization of the paper is in order. In Section 2, we develop an axiomatic approach of extension of the weighting function, along with the motivation of such generalization. We provide some generic examples of the generalized membership degree weight functions. We also formulate the clustering problem along with intuitive justification of the axiomatic development of the general class of weighting functions and develop an AO algorithm to solve it. In Section 3, we carry out a full-fledged convergence analysis of the proposed algorithm. In Section 4, we conclude by presenting a brief summary of the findings and discussing the probable future extensions of the development presented in this article. 2. Clustering with generalized weighting function In this section, we present the motivation of the generalization and the fundamentals of the axiomatic approach. Next we develop the fuzzy clustering procedure with the general class of membership degree weighting functions. 2.1. Motivation for generalization The choice of distance measure in the FCM determines the shapes of the clusters that will be detected by the FCM algorithm (e.g. squared Euclidean - spherical, Mahalanobis distance - elliptical etc.). In this paper, we are concerned with the contribution of a specific data point to the objective function, given the membership degrees uij . In the classical k-means algorithm, when we optimize the objective function with respect to the membership matrix (keeping the cluster prototypes fixed), we basically solve a locally defined optimization problem. Hence, the solutions are obtained at the boundary points i.e. {0, 1}. In presence of ambiguous data and in-distinctive cluster boundaries, assignment of a data point completely to one single cluster is not a very realistic choice to make. In that case, a point is assigned to one or more clusters with varying degree of membership. In order to achieve that, the optimization task with respect to the membership matrix was turned into a convex optimization problem by introducing the notion of a fuzzifier. Here, the contribution of a data point (with membership uij ) in the objective function, was related to the membership degree, through the function uij → uij m , m > 1. Here, to the best of our knowledge, no justification was provided for the choice of uij m as the weighting function to make the optimization problem convex, when it was first proposed [6,14]. A detailed exploration of the significance of fuzzifier and its implications was carried out in [28,29]. The authors established a relationship between the value of the fuzzifier m and the smoothness of transition from a high membership degree in one cluster to the other. Higher the fuzzifier, smoother the transition i.e. as m → 1, we obtain crispier partition and as m → ∞, we get equal membership degrees to all clusters with all cluster representatives or centers converging to the global mean of the data set. From the membership update scheme of the conventional FCM algorithm, it is clearly evident that a data point has non-zero membership in all clusters, unless a data point actually coincides with one of the cluster representatives. This implication produces somehow counter-intuitive results, as this will indicate that, no matter how far a data is from a cluster representative and how well it is represented by other clusters, it will have non-zero membership in all the clusters (except for the rare case, where the data point actually coincides with a cluster representative) [29]. The disadvantages of such membership allocation can lead to the following undesired results: 1. In the case of clustering a data where clusters have unequal data densities, the cluster(s) with the higher data density attracts the cluster representative(s) of the other cluster(s) with lower data density. This leads to counter-intuitive clustering performances in the conventional FCM framework. In Fig. 1, it is demonstrated that in the aforementioned scenario, the representative of the cluster with lower data density is attracted towards the representative of the cluster with higher density, which leads to dubious results.
A. Saha, S. Das / Information Sciences 408 (2017) 129–145
-1 -5
-4
-3
-2
Y axis -5
-4
-3
-2
Y axis
-1
0
0
1
1
2
2
132
-5
-4
-3
-2
-1
0
1
X axis
(a)
2
-5
-4
-3
-2
-1
0
1
2
X axis
(b)
as the membership degree weighting function. Fig. 1. (a) Original Dataset, (b) Clustering performance with um ij
2. We consider a situation, where, we have already clustered a data set. Now we add an outlier in the data and recluster the extended data set with one more cluster as the original dataset. In an ideal scenario, the outlier should be clustered separately in the new cluster, and the earlier cluster structure should have remained as it was. But this is not the actual scenario, that takes place in case of clustering with conventional FCM [29]. Hence, the choice of uij m as the weighting function does fail in certain cases, the aforementioned two being the most prominent of them. With the exploration of the shortcomings of the conventional fuzzifier based FCM, there were some attempts to address the problem by proposing some specific weighting functions [28,29]. This approach had the following problems: 1. To the best of our knowledge, no convergence analysis corresponding to the proposed membership degree weighting functions, are available in the literature. 2. Though some justifications were provided to chalk out the basic properties (increasing and convex) of any such function, but the choice was one single function, that satisfied the necessary condition. It hardly represented the class of all possible weighting functions. In the modern day of huge data influx, where, the existence of outliers in the data or unevenly distributed data is more of a norm than an exception, it can be effective to generalize the notion of the weighting function in an axiomatic approach as well as to investigate the corresponding convergence properties. The present article attempts to make a humble contribution in this context. 2.2. Generalized membership-degree weighting function We define a general class of weighting functions, based on which we will develop the fuzzy clustering algorithm. We call this general class of functions as Consistent Membership-degree Weighting Function (CMWF). For the sake of notational clarity, we will denote the membership of any ith data point to cluster Cj or uij simply by a subscript-free scalar variable u. The CMWF class of functions can be formally defined in the following way. Definition 1. A function g : (0, 1) → [0, 1] is called a consistent membership degree weighting function, if it satisfies the following criteria: 1. g is strictly increasing on (0, 1). 2.
lim g(u ) = 0
(1a)
lim g(u ) = 1
(1b)
u→0+
u→1−
3. g is strictly convex function on (0, 1).
A. Saha, S. Das / Information Sciences 408 (2017) 129–145
133
4. g is differentiable on (0, 1). The significance and intuitions behind the technical conditions on CMWF, will be discussed in detail in Section 2.5. As a brief summary of the motivation, it can be said, the first condition arises from the fundamental notion of the weight function, whereas the second condition is necessary for the sake of a well-defined clustering problem, maintaining consistency with the general notion of weighting functions. The third condition also arises from the basic notion but is instrumental in convergence analysis. Here, we emphasis that the first assumption implies that, g is differentiable almost on everywhere on (0, 1) (i.e. non-differentiable at almost countably many points). The fourth condition strengthens the differentiability property of g by making it everywhere differentiable on (0, 1), which plays a pivotal role in the development of the convergence analysis. 2.3. Generic examples of CMWF In this subsection, we discuss some generic examples of members of interest in the CMWF family. Example 1. The first example and the corresponding clustering algorithm (will be defined in Section 2.5) was first proposed in [14] with the weight function u → u2 . Later [6] generalized the weighting function by using the mapping u → um ; m > 1, where the m is conventionally called the fuzzifier. To the best of our knowledge, the class of weighting functions generated by varying the value of m is the only such class available in literature and used for fuzzy clustering till date. Recently, a theoretical approach towards the choice of fuzzifier m for a particular dataset under consideration was developed in literature [24]. This general class of weighting functions is generated by the following member of CMWF:
g1,m (u ) = um , m > 1. Now, we will show that this belongs to the class of CMWFs. First, this is a strictly increasing, strictly convex function, which is obvious from considering the first (g (u ) = mum−1 > 0; ∀u ∈ (0, 1 )) and the second derivative (g (u ) = m(m − 1 )um−2 > 0; ∀u ∈ (0, 1 )). Now, the second condition is also trivially satisfied, as limu→0+ um = 0 and limu→1− um = 1 Example 2. A second generic example of CMWF is given by the following function:
g2 ( u ) =
eu − 1 . e−1
The aforementioned function is strictly increasing, strictly convex function from the properties of exponential function (the first derivative is positive and second derivative is always positive). The second condition also follows trivially as limu→0+ eu = 1 and limu→1− eu = e. Example 3. Another generic example of CMWF is given by the following function: m
eu − 1 , m > 1. e−1
g3,m (u ) =
The aforementioned function is strictly increasing, strictly convex function from the fact that composition of two strictly increasing strictly convex functions is again strictly convex and strictly increasing (g3,m = g2 ◦ g1,m ). The second condition m m also follows trivially as limx→0+ eu = 1 and limu→1− eu = e. As far as kernel functions are concerned, they are generally centered around the origin. From the fundamental nature of kernel functions, they are usually decreasing in [0, 1]. Moreover, the kernel functions are not strictly convex, if we consider their respective whole domains. Nonetheless, we can derive a CMWF from kernel functions or shift them to make it strictly increasing and strictly convex in [0, 1]. We present an example of each of the cases in the perspective of the Gaussian kernel functions : Example 4. First of all, we look at the following function :
g4 ( u ) =
e
u2 2
−1
1 2
e −1
. u2
In the aforementioned function, e 2 plays the functional part (which is obtained from the inverse of the functional part of a standard Gaussian density function), while the other constants are used for normalization. By construction, g4 is differentiable on (0, 1) and satisfies the limit conditions. We also check that,
g 4 (u ) =
ue
u2 2
1
e2 − 1
, ⇒ g 4 (u ) > 0; ∀u ∈ (0, 1 ).
This proves that the function is strictly increasing on (0, 1).
g 4 (u ) =
e
u2 2
+ u2 e 1
e2 − 1
u2 2
, ⇒ g 4 (u ) > 0; ∀u ∈ (0, 1 ).
134
A. Saha, S. Das / Information Sciences 408 (2017) 129–145
This proves that the function is strictly convex on (0, 1), which also concludes the proof of the fact that the function under consideration is a valid CMWF. Example 5. On the other hand, we can obtain a CMWF from the Gaussian kernel, just by making a location shift as follows:
g5 ( u ) =
e−
(u−2 )2 2
e
− 12
− e−2
− e−2
. (u−2 )2
In the aforementioned function, e− 2 plays the functional part (which is obtained from the inverse of the functional part of a standard Gaussian density function), while the other constants are used for normalization. By construction, g5 is differentiable on (0, 1) and satisfies the limit conditions. We also check that,
g 5 (u ) =
− ( u − 2 )e
(u−2 )2 2
1
e− 2 − e−2
, ⇒ g 5 (u ) > 0; ∀u ∈ (0, 1 ).
This proves that the function is strictly increasing on (0, 1).
g 5 (u ) =
−e
(u−2 )2 2
+ ( u − 2 )2 e
(u−2 )2 2
1
e− 2 − e−2
, ⇒ g 5 (u ) > 0∀u ∈ (0, 1 ).
The positivity of g 5 (u ) follows from the fact that (u − 2 )2 − 1 > 0, ∀u ∈ (0, 1 ). This proves that the function is strictly convex on (0, 1), which also concludes the proof of the fact that the function under consideration is a valid CMWF. 2.4. Relationship with the existing generalized weighting functions Here, we demonstrate that the previous attempts of intuitive generalization of the membership degree weighting function, can be obtained as a special case of the proposed CMWF family . 1. The weighting function proposed in [29] can be obtained as a special case of the CMWF family, with the following choice of the weighting function
g6,β (u ) =
1−β 2 2β u + u, 1+β 1+β
β > 0.
Now, we show that g6,β is in CMWF. First, this is a strictly increasing, strictly convex function, which is obvious from con−β sidering the first (g 6,β (u ) = 2 11+ βu+
2β 1+β
1−β > 0; ∀u ∈ (0, 1 )) and the second derivative (g 6,β (u ) = 2 1+ β > 0; ∀u ∈ (0, 1 )).
Now, the second condition is also trivially satisfied, as limu→0+ g6,β (u ) = 0 and limu→1− g6,β (u ) =
1−β 1+β
+
2β 1+β
=1
2. The weighting function proposed in [28] can be obtained as a special case of the CMWF family, with the following choice of the function
g7,β (u ) =
eβ u − 1 , eβ − 1
β>0
Now, we show that g7,β is in CMWF. First, this is a strictly increasing, strictly convex function, which is obvious from βu
βu
e −1
e −1
considering the first (g 7,β (u ) = β e β −1 > 0; ∀u ∈ (0, 1 )) and the second derivative (g 7,β (u ) = β 2 e β −1 > 0; ∀u ∈ (0, 1 )). Now, the second condition is also trivially satisfied, as limu→0+ g7,β (u ) = 0 and limu→1− g7,β (u ) = 1. 2.5. Clustering problem formulation and algorithm development In this section, we present the general class of clustering problems with CMWF. We first formulate the problem, next by means of the iterative sequence of solutions of several optimization problems, we develop an AO algorithm for solving the clustering problem. 2.5.1. Problem formulation Let X = {x1 , x2 , · · · , xn }, xi ∈ Rd , ∀i = 1, 2, · · · , n be the given set of patterns, which we want to partition into c (prefixed) clusters with 2 ≤ c ≤ n. Let B ⊂ Rd be the convex hull of X . The general clustering problem with any member of CMWF can be formulated as follows:
P : minimize fg (U, Z ) =
n c
g˜(ui j )d (z j , xi ),
(2)
i=1 j=1
where
d ( z j , xi ) =
d l=1
(z j,l − xi,l )2 ,
(3)
A. Saha, S. Das / Information Sciences 408 (2017) 129–145
135
g(u ) if u ∈ (0, 1 ), 0, if u = 0, 1, otherwise,
(4)
ui j = 1, ∀i = 1, 2, · · · , n,
(5a)
g˜(u ) = subject to c j=1
0<
n
ui j < n, ∀ j = 1, 2, · · · , c,
(5b)
i=1
ui j ∈ [0, 1], ∀i = 1, 2, · · · , n; ∀ j = 1, 2, · · · , c,
(5c)
Z = {z1 , z2 , · · · , zc }, z j ∈ B ⊆ Rd , ∀ j = 1, 2, · · · , c; Z ∈ B c .
(5d)
Here, the first three restrictions (5a)–(5c) are conventional restrictions on the membership matrix. The fourth one (5d) restricts the optimization to the convex hull of the patterns, which we will later show is equivalent to optimizing in the whole Rd corresponding to each zj . The distance function under consideration (3) is squared Euclidean distance. g˜(u ) in (4) is just the canonical extension of g from (0, 1) to [0, 1], such that g˜ is continuous at 0 and 1. We impose four restrictions (strictly increasing, existence of limits at boundary points, strictly convex, and differentiable) on the weighting function. In what follows, we explain in detail, why these conditions can be obtained from intuitive notion of the weighting function. We present the mathematical and intuitive justification of them as follows: 1. Increasing function: Here, h(uij ) denotes the weight of contribution of the distance between the ith data point and the cluster representative corresponding to the jth cluster. Quite naturally the higher the membership of a data point in a particular cluster, higher should be its contribution. In order to express this mathematically, we consider the problem of optimizing the objective function with respect to the membership matrix, with fixed cluster representatives. Now, if g is non increasing, in order to minimize the objective function, we will assign highest membership in the furthest cluster, which is completely counter-intuitive. Hence, we need g to be an increasing function. 2. Convexity: For a particular point and a specific cluster with high membership degree for the concerned point, change of weight of the corresponding distance due to a small change in membership degree, should be higher than that corresponding to a cluster, in which, the point has lower membership degree. This justifies the condition of convexity of the membership degree weighting function . In order to mathematically observe this, we consider the problem of optimizing the objective function with respect to the membership matrix, with fixed cluster representatives. We start from the membership allocation given by ui (denoting the ith row of the membership matrix), where ui j0 ui j , if di, j0 di, j , ∀ j = 1, 2, · · · , c; and di, j is the distance between ith data point and representative of the jth cluster. In order to further reduce the objective function value, let us assume that we decrease the ui, j0 value by and increase another uij by the same amount. In that case, the change in the objective function will be,
= (g(ui j + ) − g(ui j ))di, j − (g(ui j0 ) − g(ui j0 − ))di, j0 Since, di, j0 di, j , a necessary condition under which the objective function will decrease is given by,
g( u i j + ) − g( u i j ) < g( u i j 0 ) − g( u i j 0 − ) . Dividing both sides by will imply that the slope is increasing and this will lead to the convexity of the weighting function. This strictly convex property of the weighting function will also play pivotal role in the convergence analysis of the proposed algorithm. 3. Existence of limits at boundary points: As the membership value tends to zero, the weight of the corresponding distance should tend to zero, which is ensured by (1a). On the other hand, if the membership approaches its highest value (i.e. 1), the weight of the corresponding distance in objective function should approach the maximum value, i.e. 1. The existence of these two limits are technical assumptions, needed to extend g to the closed interval [0, 1], which makes g(0), g(1) well defined and the extended function g˜ continuous on [0, 1]. 4. Differentiability: g being convex, it is differentiable almost everywhere on (0, 1) (i.e. non-differentiable at countably many points). The technical assumption of everywhere differentiability plays pivotal role in convergence analysis. 2.5.2. The AO based algorithm development In this section, we develop an AO based optimization procedure for the proposed clustering problem. We start with a prefixed permissible fractional error and an initial estimate of the cluster representatives. We then optimize the objective function (2) with respect to membership matrix, such that it satisfies the conditions (5a)–(5c). For the sake of notational simplicity, we define the class of the membership matrices as follows:
Uc,n = {U | U is an n × c real matrix and satisfies (5a ) − (5c )},
136
A. Saha, S. Das / Information Sciences 408 (2017) 129–145
Next, we optimize the objective function (2) with respect to cluster representatives such that the restriction (5d) is maintained. We perform this iterative process, until the difference between the values of the objective function corresponding to two consecutive iterations become smaller than the permissible fractional error. Algorithm 1 describes the fuzzy clustering ALGORITHM 1: Clustering with CMWF. Data: Data points, number of clusters, permissible fractional error, choice of CMWF, i.e. g. Result: Membership matrix of objects in clusters, cluster representatives. initialization; c ← number of clusters; ← permissible fractional error; Z (0 ) ← initial clusters satisfying (5d); t ← 0; while fg (U(t−1 ) , Z (t−1 ) ) − fg (U(t ) , Z (t ) ) fg (U(t−1 ) , Z (t−1 ) ) do U(t+1 ) = argminU∈Uc,n fg (U, Z (t ) ); Z (t+1 ) = argminZ j ∈Bc fg (U(t+1 ) , Z );
t ← t + 1; end
with CMWF. 3. Convergence analysis of clustering with CMWF We carry out a complete convergence analysis of the fuzzy clustering with CMWF, proposed in Algorithm 1. We first address the existence and uniqueness of the solutions of partial optimization problems with respect to the membership matrix and cluster representatives. Next we develop the convergence properties of the proposed algorithm. 3.1. Existence and uniqueness of the solutions of partial optimization problems We address the partial optimization problems in the proposed algorithm (Algorithm 1) starting with the following theorem. Theorem 1. For fixed U∗ ∈ Uc,n , the problem P1 : minimize fg (U∗ , Z ), Z ∈ B c , has a unique solution. Proof. The function to be minimized in problem P1 is a strictly convex function with respect to Z (from the fact that the squared Euclidean distance d(y, x) is a strictly convex function, with respect to y) and the optimization task is carried out on a convex set, hence, there exists at most one solution. Now, the function under consideration is also a continuous function with respect to Z (from the fact that the squared Euclidean distance d(y, x) is a continuous function, with respect to y), hence, attains its maxima and minima in a compact set, which is indeed the case here (B being the convex hull of X , is closed and bounded, i.e. compact). Hence, the minimization task under consideration, has atleast one solution in the feasible region. Employing the two aforementioned statements, we guarantee the existence of unique solution of the optimization task P1 in the feasible region. Theorem 2. Let J1 : B c → R, J1 (Z ) = fg (U∗ , Z ); z j ∈ B, ∀ j = 1, 2, · · · , c, where U∗ ∈ Uc,n is fixed. Then Z ∗ is a global minimum of J1 if and only if z∗j is given by:
z∗j =
n i=1
g˜(ui j )xi /
n
g˜(ui j ) ; j = 1, 2, · · · , c.
(6)
i=1
Proof. The condition in the theorem is derived as a first order necessary condition by setting the partial derivative of the objective function with respect to zj equal to zero. From the strict convexity of the objective function with respect to zj , it follows that those conditions are also sufficient conditions to uniquely determine the minimizer. Theorem 3. For fixed Z ∗ = {z∗1 , z∗2 , · · · , zc }, z∗j ∈ B c , the problem P2 : minimize fg (U, Z ∗ ), U ∈ Uc,n , has a unique solution under the assumption i∗ = { j | d (z∗j , xi ) = 0} = φ ; ∀i = 1, 2, · · · , n. Proof. Under the assumption, the function to be minimized in problem P2 is a strictly convex function with respect to U (from the first condition of CMWF) and the optimization task is carried out on a convex set (Uc,n is a convex set), there exists at most one solution. Now, the function under consideration is also a continuous function with respect to U (from the fact that being strictly increasing and strictly convex, g is continuous on (0, 1), so is g˜; moreover, from the way it is defined (4), g˜ is continuous
A. Saha, S. Das / Information Sciences 408 (2017) 129–145
137
at 0 and 1). Hence, it attains its maxima and minima in a compact set, which is indeed the case here (UÂŻ c,n = Uc,n , hence, Uc,n is closed. Being a bounded set, it is also compact). Thus, the minimization task under consideration, has at least one solution in the feasible region. Employing the two aforementioned statements, we guarantee the existence of unique solution of the optimization task P2 in the feasible region. Theorem 4. Let J2 : Uc,n → R, J2 (U ) = fg (U, Z ∗ ); U∗ ∈ Uc,n , where z∗j ∈ B; ∀ j = 1, 2, ¡ ¡ ¡ , c is ďŹ xed. Then U∗ is a global minimum of J2 if and only if U∗ satisďŹ es the following equations, ∀i = 1, 2, ¡ ¡ ¡ , n;
j | d (z∗j , xi ) = 0 ;
i∗ = if i∗ = φ ,
u∗i j = v∗i j 2 ,
(7a)
g˜ (v∗i j 2 )d (z∗j , xi ) = g˜ (v∗i j 2 )d (z∗j , xi ); c
∀ j = j ∈ 1, 2, ¡ ¡ ¡ , c ,
v∗i j 2 = 1.
(7b)
(7c)
j=1
If i∗ = φ
u∗i j =
⎧ ⎨ 0 with u∗ik = 1 i f j ∈ i∗ , ⎊
z∗k =xi
(7d)
0
otherwise.
Proof. Minimization of J2 over Uc,n is a Kuhn–Tucker problem with cn + c many inequality constraints given by (5a) and (5c) as well as n many equality constraints given by (5b). We can merge (5a) and (5c) by making the substitution, ui j = v2i j , and in that case, we have the following optimization task at hand:
RP2 : minimize RJ2 (V ) =
n c
g˜(v2i j )d (z∗j , xi ),
i=1 j=1
such that c
v2i j = 1 i = 1, 2, ¡ ¡ ¡ , n.
j=1
Let Ν = (Ν1 , Ν2 , ¡ ¡ ¡ , Νn ) be the vector of Lagrange multipliers corresponding to the n equality constraints. Now, the Lagrangian can be written in the following way:
LJ2 (V, Îť ) = RJ2 (V ) +
n i=1
Îťi
c
v2i j − 1 .
j=1
First, from the strict convexity of gËœ(x ) on (0, 1), it follows that under the linear constraints of (5b) on U, for some ďŹ xed i, u∗i j = 0 for some j, if and only if | i∗ | = φ . Hence, under the assumption | i∗ | = φ , we get the desired conditions by setting the ďŹ rst order condition equal to 0 and by employing Theorem 3. If i∗ = φ , (i.e. the data point under consideration actually coincides with a cluster representative) with the membership assignment in (7d), the contribution of the ith point in the objective function will be 0. It can be trivially seen that, any other membership assignment will lead to a positive contribution, contradicting its candidature for an optimizer of the objective function. Now, we will show that the optimizer thus obtained, actually satisďŹ es the inequality constraints given in (5b). Assume ∃j0 ∈ {1, 2, , c}, such that ni=1 u∗i j = 0, i.e. ui j0 = 0; i = 1, 2, ¡ ¡ ¡ , n, i.e. i∗ = φ ; ∀i and j0 ∈/ âˆŞni=1 i∗ . Hence, | âˆŞni=1 i∗ | 0 c − 1 < n, but i∗ ∊ ∗j = φ , ∀i = j (if i∗ ∊ ∗j = φ , then d (xi , x j ) = 0, a contradiction!). Hence | âˆŞni=1 i∗ | = ni=1 | i∗ | n, which is a contradiction. Hence, there does not exist such j0 , which completes the proof of the theorem. 3.2. Convergence properties of CMWF based clustering In this section, we use Zangwill’s global convergence theorem [50] to derive the convergence results regarding the AO based clustering with CMWF, proposed in Algorithm 1. In order to update the membership matrix and cluster representatives, we deďŹ ne the following operators:
138
A. Saha, S. Das / Information Sciences 408 (2017) 129–145
DeďŹ nition 2. Tmemb : B c → Uc,n , Tmemb (Z ) = U = [ui j ], where, uij is given by the following rule (Theorem 4):
i = j | d ( z j , x i ) = 0 ;
if i = φ ,
ui j = vi j 2 ,
(8a)
g (vi j 2 )d (z j , xi ) = g (vi j 2 )d (z j , xi ); c
∀ j = j ∈ 1, 2, ¡ ¡ ¡ , c ,
(8b)
vi j 2 = 1.
(8c)
j=1
If i = φ
0 with
ui j =
uik = 1
if j ∈ i ,
(8d)
zk =xi
0
otherwise.
DeďŹ nition 3.
Tcent : Uc,n → B c , Tcent (U ) = Z = (z1 , z2 , ¡ ¡ ¡ , zc ), where the vectors (z1 , z2 , ¡ ¡ ¡ , zc ), z j ∈ B, j = 1, 2, ¡ ¡ ¡ , c are calculated as:
n
zj =
g˜(ui j )xi
i=1
n
g˜(ui j ) .
(9)
i=1
We ďŹ rst deďŹ ne the clustering operator in the following way: DeďŹ nition 4.
J : (Uc,n × B c ) → (Uc,n × B c ), J = Ocent ◌ Omemb , where
Omemb : Uc,n × B c → Uc,n ; Omemb (U, Z ) = Tmemb (Z ), Ocent : B c → Uc,n × B c ; Ocent (U ) = (U, Tcent (U )), J (U, Z ) = (Tmemb (Z ), Tcent (Tmemb (Z ) ) ). Lemma 1. Uc,n × B c is compact. Proof. Uc,n and B c were proved to be compact in Theorems 1 and 3 respectively. Hence, the lemma follows.
DeďŹ nition 5. We deďŹ ne a subset T of optimal points in Uc,n Ă— B c as follows
T =
(U∗ , Z ∗ ) ∈ Uc,n Ă— Bc |
fg (U∗ , Z ∗ ) fg (U, Z ∗ ), ∀U ∈ Uc,n , U = U∗ , fg (U∗ , Z ∗ ) < fg (U∗ , Z ), ∀Z ∈ B c , Z = Z ∗ .
Lemma 2. The set deďŹ ned in (10) satisďŹ es the following two conditions: 1. If h ∈ / T , then fg (h∗ ) < fg (h ), ∀h∗ ∈ J (h ), h, h∗ ∈ Uc,n Ă— B c . 2. If h ∈ T , then fg (h∗ ) fg (h ), ∀h∗ ∈ J (h ), h, h∗ ∈ Uc,n Ă— B c . Proof. For any (U∗, Z∗ ) ∈ Uc,n Ă— B c , the following chain of inequalities hold true:
fg (J (U∗ , Z ∗ )) = fg (Tmemb (Z ∗ ), Tcent (Tmemb (Z ∗ ))) fg (Tmemb (Z ∗ ), Z ∗ ) fg (U∗ , Z ∗ ). Equality holds if and only if,
(10)
A. Saha, S. Das / Information Sciences 408 (2017) 129–145
139
U∗ ∈ Tmemb (Z ∗ ); and Z ∗ = Tcent (U∗ ), which implies that (U∗ , Z ∗ ) is in T .
Lemma 3. Under the assumption, i = φ , ∀i = 1, 2, ¡ ¡ ¡ , n; the map, Tmemb is a point-to-point continuous map. Proof. Theorem 3 implies that the map under consideration is a point-to-point map. In order to address the issue of continuity, we proceed as follows. We deďŹ ne the following set of functions:
Bi, j1 , j2 : B c Ă— Uc,n → R; Bi, j1 , j2 (Z, U ) = gËœ (ui j1 )d (z j1 , xi ) − gËœ (ui j2 )d (z j2 , xi );
(11a)
Di : B c × Uc,n → R; Di (Z, U ) =
c
ui j − 1, i = 1, 2, ¡ ¡ ¡ , n.
(11b)
j=1
Let us deďŹ ne the kernel of a function f : X → R as follows:
φ ( f ) = x ∈ X | f (x ) = 0 .
Now, Bi, j1 , j2 (∀i = 1, 2, ¡ ¡ ¡ n; j1 , j2 ∈ 1, 2, ¡ ¡ ¡ , c; , j1 = j2 ) is a continuous function (gËœ being convex and differentiable, is also continuously differentiable, hence gËœ is continuous), hence, their kernel is closed. Di (∀i = 1, 2, ¡ ¡ ¡ , n ) is also continuous, hence has a closed kernel. Being intersection of closed sets, the set given by:
S=
∊ni=1 ∊c−1 ∊cj2 = j1 +1 φ (Bi, j1 , j2 ) ∊ j1 =1
∊ni=1 φ (Di )
is also closed. Now, by deďŹ nition, S ⊆ B c Ă— Uc,n . From the very deďŹ nition of Tmemb , we can rewrite R as follows:
R = Z , Tmemb (Z ) | Z ∈ B c
Hence R is also the graph of the function Tmemb . Now, we apply the closed graph theorem to prove the continuity of Tmemb . Closed graph theorem: ([36], p. 171) The function from a topological space to a compact Hausdorff space is continuous, if and only if the graph of the function (the graph of T : P → Y is the set {((x, y ) ∈ P Ă— Y | T (x ) = y )}) is closed. Using the fact that Uc,n is a compact set and S is a closed set, from the closed graph theorem it follows that Tmemb is continuous. ∗
∗
Lemma 4. The map Tmemb is closed at Z R1 if (U, Z R1 ) ∈ / T for some U ∈ Uc,n . (t )
(t )
∗
(t )
∞ (Z R1 ∈ B c ) converging to Z R1 and {UR1 }∞ Proof. We have to prove the following: for all sequences {Z R1 }t=0 t=0 (t )
∗
∗
∗
[∈ Tmemb (Z R1 )] converging to UR1 ; we have that, UR1 ∈ Tmemb (Z R1 ). We shall show that the closedness property holds true individually for membership vector corresponding to each of the patterns xi , ∀i = 1, 2, ¡ ¡ ¡ , n. In order to show that, we deďŹ ne the following: R(t )
R∗
i(t ) = { j | d (z j 1 , xi ) = 0}; i∗ = { j | d (z j 1 , xi ) = 0}. R
(t )
R∗
∞ to z 1 and the continuity of dissimilarity measure, we can ďŹ nd M If | i∗ | = 0, using the convergence of {z j 1 }t=0 fuzz1 such j
that, ∀t > Mfuzz1 , | i(t ) | = 0, implying the lemma from Lemma 3. If | i∗ | > 0, ∀c > 1, we can ďŹ nd ∀c ( > 0) Mfuzz2 such that R
(t )
R
(t )
∀t > Mfuzz2 , max j∈ i∗ d (z j 1 , xi ) < c min j∈/ i∗ distg (z j 1 , xi ), which implies the lemma. /T. Lemma 5. The map J is closed at (UR2 , Z R2 ) if (UR2 , Z R2 ) ∈ Proof. Lemma 4 and the continuity of Tcent implies this.
∞ either terminates at a point in T (as deďŹ ned in (10)) or has a Theorem 5. ∀ Z (0 ) ∈ B c , the sequence, {J (Tmemb (Z (0 ) ), Z (0 ) )}t=1 subsequence that converges to a point in T .
Proof. We ďŹ rst restate below the Zangwill’s global convergence theorem which is used to prove Theorem 5. Zangwill’s global convergence theorem [50]: Let R be a set of minimizers of a continuous objective function on H. ∞ Let A : H → H be a point-to-set map which determines an algorithm that given a point s0 ∈ H, generates a sequence {st }t=0 through the iteration st+1 ∈ A(st ). We further assume
A. Saha, S. Das / Information Sciences 408 (2017) 129–145
-5
-4
-3
-2
Y axis
-1
0
1
2
140
-5
-4
-3
-2
-1
0
1
2
X axis Fig. 2. Clustering performance of the FCM with CMWF of Example 3 (Section 2.3) as the weighting function.
∞ ∈ C ⊆ H, where C is a compact set. 1. The sequence {st }t=0 2. The continuous objective function on H satisfies the following: (a) If s ∈ / R, then (s ) < (s ), ∀s ∈ A(H ), (b) If s ∈ R, then (s ) (s ), ∀s ∈ A(H ). 3. The map A is closed at s if s ∈ / R (if A is actually a point-to-point map instead of a point-to-set map, the condition (c) of the theorem turns out to be simply the continuity of A.) ∞ is in R. Then the limit of any convergent subsequence of {st }t=0 We take A to be J, H to be Uc,n × B c ; s0 to be (U(0 ) , Z (0 ) ); C to be the whole of H (compactness of H is guaranteed by Lemma 1); to be fg (being the sum of continuous functions, fg is a continuous function), R to be T (10 ) (Lemma 2 justifies the choice). By Lemma 5, J is closed on this particular choice of H. Thus, from Zangwill’s convergence theorem, ∞ has a limit in T . Next ∀ (Z (0 ) ) ∈ B c , we consider the sequence the limit of any convergent subsequence of {U(t ) , Z (t ) }t=0 ( t ) ( 0 ) ( 0 ) ∞ {J (Tmemb (Z ), Z }t=0 which is contained in the compact set given by H. Hence by Bolzano–Weierstrass theorem [16] it ∞ , ∀Z ( 0 ) ∈ B c has a convergent subsequence. These statements imply that the sequence given by {J (t ) (Tmemb (Z (0 ) ), Z (0 ) )}t=0 either terminates at a point in T given by (10) or has a subsequence that converges to a point in T .
This provides us a complete convergence analysis of the proposed general class of algorithms with CMWF. The developed convergence property is exactly same as that corresponding to the classical FCM with squared Euclidean distance. With the choice of the CMWF, that generates the conventional FCM weighting function (discussed in Example 1, Section 2), we obtain the convergence result corresponding to classical FCM [6,8]. Hence, this article presents a novel generalization (with respect to the weighting functions) of the classical FCm along with its convergence properties.
4. Experimental results In this section, we present a sample performance comparison (on several simulated and real life datasets) of a specific member of the proposed generalized algorithm with the classical FCM, just to highlight the usefulness of the proposed CMWF family. Before discussing the main comparative study, we illustrate a simple proof of concept result with the dataset shown in Fig. 1(a). Fig. 2 shows the clustering obtained by FCM with the weighting function of Example 3 in Section 2.3. It is evident that the dataset is perfectly clustered with the choice of this CMWF.
A. Saha, S. Das / Information Sciences 408 (2017) 129–145
141
Table 1 Summary of the used datasets (here, n, d and c stand for the no. of data points, no. of features, and actual clusters respectively). Data
n
d
c
Spherical 5_2 [1] Spherical 6_2 [1] st900 [2] elliptical_10_2 [2] R15 [43] S1 [17] S3 [17] Iris Data [32] Seed Data [32] Wine Data [32] Wisconsin Breast Cancer Data [32] Wisconsin Diagnostic Breast Cancer Data [32]
250 300 900 500 50 0 0 50 0 0 50 0 0 150 210 178 699 569
2 2 2 2 2 2 2 4 8 13 10 32
5 6 9 10 15 15 15 3 3 3 2 2
Table 2 Comparison of ARI values. Best total and mean values are marked in boldface. Data
FCM with CMWF
Classical FCM
Spherical 5_2 Spherical 6_2 st900 elliptical_10_2 R15 S1 S3 Iris Data Seed Data Wine Data Wisconsin Breast Cancer Data Wisconsin Diagnostic Breast Cancer Data Total Mean
0.922 0.962 0.839 0.903 0.933 0.962 0.701 0.801 0.716 0.4136 0.863 0.55 9.575 0.798
0.877 (0.012) 0.8898 (0.01) 0.839 (1) 0.841 (0.001) 0.8906 (0.15) 0.925 (0.05) 0.691 (0.45) 0.729 (0.001) 0.716 (1) 0.3539 (0.172) 0.79 (0.05) 0.491 (0.001) 9.0313 0.753
4.1. Benchmark dataset Here, we consider a total of 12 datasets of which 7 are synthetic and 5 from real world. Summary of the datasets along with the relevant citations are provided in Table 1. Description of the synthetic datasets can be found in the respective references. In particular, the datasets R15, S1, and S3 can be downloaded from http://cs.joensuu.fi/sipu/datasets/. Each of S1 and S3 contain 15 Gaussian clusters with different degrees of overlap among the clusters. The dataset R15 was generated using 15 similar two-dimensional Gaussian distributions. 4.2. Performance measure Here we employ hard partition based validity functions. In order to achieve hard partition from soft partition, we assign the point to the cluster with the highest membership. In case of a tie, it is assigned to any cluster with each candidate having equal probability. Let T = t1 , t2 , · · · , tR and S = s1 , s2 , · · · , sc be two valid partitions of the given data. Let T be the actual partition and S be the obtained partition in some clustering algorithm, Now, we wish to evaluate the goodness of S. nij is the number of objects present in both cluster ti and sj ; ni. is the number of objects present in cluster ti ; n.j is the number of objects present in cluster sj . In order to compare the clustering performance of the different algorithms, we use a well accepted measure called Adjusted Rand Index (ARI) [25,48]. ARI can be formally expressed in the following way:
ARI (T , S ) =
i, j
1 n 2
i
i.
2
n i j 2
+
−
n. j n n
n . j j
2
i.
i
j
2
−
2
/
2
n. j n n i
i.
2
j
2
/
2
4.3. Computational protocols The computational protocols that we followed throughout the simulations are in order.
142
A. Saha, S. Das / Information Sciences 408 (2017) 129–145
Fig. 3. The best clustering performance of our algorithm on (a) Spherical 5_2, (b) Spherical 6_2, (c) st900, (d) elliptical_10_2, (e) R15, (f) S1. (For interpretation of the references to colour in the text, the reader is referred to the web version of this article.)
A. Saha, S. Das / Information Sciences 408 (2017) 129–145
143
Fig. 4. The best clustering performance of our algorithm on (a) S3, (b) Iris, (c) Seed, (d) Wine, (e) Wisconsin Breast Cancer, (f) Wisconsin Diagnostic Breast Cancer Data. (For interpretation of the references to colour in the text, the reader is referred to the web version of this article.)
144
A. Saha, S. Das / Information Sciences 408 (2017) 129–145
Choice of CMWF : From the very definition of CMWF, it is obvious that mathematically, there are infinitely many candidates for them. Due to the impossibility of demonstration of a complete performance comparison among all possible CMWFs, we choose and fix g4 (Example 4, Section 2.3) as our choice of CMWF. We again draw readers’ attention to the fact that, a performance comparison among different choices of CMWF is not the focus or the purpose of the present theoretical article. This can be taken as an interesting future research topic. Algorithms under consideration : Proposed FCM with the specific choice of CMWF (A1), FCM with the conventional weighting function (A2). Both the algorithms used the conventional squared Euclidean distance function. 4.4. Results and statistical comparison For each of the 12 datasets under consideration, we carry out the Wilcoxon’s rank sum test (paired) between the performance by the algorithms (over 30 independent runs) under consideration, to see if we have a statistically significant improvement in our algorithm from the others. Here best performance is reported, based on mean ARI value achieved in 30 runs. For each run, algorithms A1 and A2 started with the same initial cluster representatives so that any performance difference between them may be attributed to their internal operators only. For a specific dataset R, let the median of the difference of the ARI corresponding to algorithms ([ARI of A1 - ARI of A2]; corresponding to each of the 30 runs) A1 and A2 be denoted by m. We perform paired Wilcoxon’s rank-sum test on the following hypothesis testing setup:
H0 : m = 0 vs. H1 : m > 0 In Table 2, we report the best performance, based upon mean value in 30 runs. In parenthesis, we report the corresponding P-values in parenthesis in the column corresponding to Classical FCM. From Table 2, we observe that our algorithm achieved best average ARI value in all the datasets, which give us some experimental evidence on the practical usefulness of the proposed algorithm. We graphically present the best clustering performances (Figs. 3 and 4) corresponding to our proposed generalized algorithms. In case of 2D simulated datasets, different color along with a different sign is used to identify different clusters in the scatter plot. In case of the real world datasets, with more than two features, we present the parallel coordinate plot of the clustered datasets, where each cluster is denoted by a different color. From the P-values obtained in Table 2, we see that 7 out of the 12 tests have a P-value less than or equal to 0.05. Hence, there is enough statistically significant evidence (significance level 0.05) in the data to conclude that the ARI obtained using FCM with CMWF is bigger than that obtained with classical FCM. In the rest of the cases, the average value of the obtained ARI using FCM with CMWF is better than that corresponding to the classical FCM . 5. Conclusion Starting with a general class of membership-based weighting functions, in this article we presented a novel class of the generalized FCM algorithms. We undertook a detailed analysis of the mathematical properties of the sub-optimization problems involved in the FCM formulation and also investigated the convergence properties (corresponding to a suitable set of optimal points) of the proposed clustering algorithm. It is evident that the CMWF-based clustering scheme can also be generalized to any FCM variant with other distance measures. After the classical FCM algorithm [6] was introduced in literature, to the best of our knowledge, this is the first time, an article has directly addressed the issue of structured axiomatic generalization of the weighting function and has established its convergence properties which are comparable to that of the classical FCM [6]. The theoretical development of the new generalized CMWF based clustering algorithm provides us with a flexible class of weighting functions which can be used for the development of data-specific clustering algorithms with improved performances. Members from the CMWF class can be integrated with other advanced variants of FCM like the neutrosophic c-means clustering algorithm [20], interval type-2 FCM [40] etc. What is the best way to choose an appropriate weighting function given the data? How can we approximate the updating rule corresponding to the weighting function, when a closed form expression is not readily available? Even partial answers to such theoretical questions would have a significant practical impact and deserve further investigations. We wish to continue our research work in this direction. References [1] S. Bandyopadhyay, U. Maulik, Genetic clustering for automatic evolution of clusters and application to image classification, Pattern Recognit. 35 (6) (2002) 1197–1208. [2] S. Bandyopadhyay, S.K. Pal, Classification and Learning using Genetic Algorithms: Applications in Bioinformatics and Web Intelligence, Springer Science & Business Media, 2007. [3] A. Banerjee, X. Guo, H. Wang, On the optimality of conditional expectation as a Bregman predictor, Inf. Theory IEEE Trans. 51 (7) (2005) 2664–2669. [4] A. Banerjee, S. Merugu, I.S. Dhillon, J. Ghosh, Clustering with Bregman divergences, J. Mach. Learn. Res. 6 (2005) 1705–1749. [5] A. Ben-Tal, A. Charnes, M. Teboulle, Entropic means, J. Math. Anal. Appl. 139 (2) (1989) 537–551. [6] J.C. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms, Kluwer Academic Publishers, Norwell, MA, USA, 1981. [7] J.C. Bezdek, R.J. Hathaway, Convergence of alternating optimization, Neural Parallel Sci. Comput. 11 (4) (2003) 351–368.
A. Saha, S. Das / Information Sciences 408 (2017) 129–145
145
[8] J.C. Bezdek, R.J. Hathaway, M.J. Sabin, W.T. Tucker, Convergence theory for fuzzy c-means: counterexamples and repairs, Syst. Man Cybern. IEEE Trans. 17 (5) (1987) 873–877. [9] L. Bobrowski, J.C. Bezdek, c-means clustering with the l1 and l∞ norms, Syst. Man Cybern. IEEE Trans. 21 (3) (1991) 545–554. [10] L.M. Bregman, The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming, USSR Comput. Math. Math. Phys. 7 (3) (1967) 200–217. [11] Chaomurilige, J. Yu, M.-S. Yang, Analysis of parameter selection for gustafson–kessel fuzzy clustering using jacobian matrix, IEEE Trans. Fuzzy Syst. 23 (6) (2015) 2329–2342. [12] I. Csisz, et al., On topological properties of f-divergences, Studia Sci. Math. Hungar. 2 (1967) 329–339. [13] I. Csiszár, I-divergence geometry of probability distributions and minimization problems, Ann. Probab. (1975) 146–158. [14] J.C. Dunn, A fuzzy relative of the isodata process and its use in detecting compact well-separated clusters, Cybern. Syst. (1973) 32–57. [15] P. Fazendeiro, J.V. de Oliveira, Observer-biased fuzzy clustering, IEEE Trans. Fuzzy Syst. 23 (1) (2015) 85–97. [16] P. Fitzpatrick, Advanced Calculus, vol. 5, American Mathematical Soc., 2006. [17] P. Fränti, O. Virmajoki, Iterative shrinking method for clustering problems, Pattern Recognit. 39 (5) (2006) 761–775. [18] S. Ganguly, D. Bose, A. Konar, Clustering using vector membership: an extension of the fuzzy c-means algorithm, in: 2013 Fifth International Conference on Advanced Computing (ICoAC), 2013, pp. 27–32, doi:10.1109/ICoAC.2013.6921922. [19] L. Groll, J. Jakel, A new convergence proof of fuzzy c-means, IEEE Trans. Fuzzy Syst. 13 (5) (2005) 717–720, doi:10.1109/TFUZZ.2005.856560. [20] Y. Guo, A. Sengur, Ncm: neutrosophic c-means clustering algorithm, Pattern Recognit. 48 (8) (2015) 2710–2724. http://dx.doi.org/10.1016/j.patcog.2015. 02.018. [21] L.O. Hall, D.B. Goldgof, Convergence of the single-pass and online fuzzy c-means algorithms, IEEE Trans. Fuzzy Syst. 19 (4) (2011) 792–794, doi:10. 1109/TFUZZ.2011.2143418. [22] R.J. Hathaway, J.C. Bezdek, Y. Hu, Generalized fuzzy c-means clustering strategies using lp norm distances, Fuzzy Syst. IEEE Trans. 8 (5) (20 0 0) 576–582. [23] F. Hoppner, F. Klawonn, A contribution to convergence theory of fuzzy c-means and derivatives, IEEE Trans. Fuzzy Syst. 11 (5) (2003) 682–694, doi:10. 1109/TFUZZ.2003.817858. [24] M. Huang, Z. Xia, H. Wang, Q. Zeng, Q. Wang, The range of the value for the fuzzifier of the fuzzy c-means algorithm, Pattern Recognit. Lett. 33 (16) (2012) 2280–2284. [25] L. Hubert, P. Arabie, Comparing partitions, J. classification 2 (1) (1985) 193–218. [26] A.K. Jain, Data clustering: 50 years beyond k-means, Pattern Recognit. Lett. 31 (8) (2010) 651–666. [27] A.K. Jain, M.N. Murty, P.J. Flynn, Data clustering: a review, ACM Comput. Surv. 31 (3) (1999) 264–323. [28] F. Klawonn, F. Höppner, An alternative approach to the fuzzifier in fuzzy clustering to obtain better clustering results, in: Proceedings of the 3rd Eusflat Conference, 2003, pp. 730–734. [29] F. Klawonn, F. Höppner, What is fuzzy about fuzzy clustering? Understanding and improving the concept of the fuzzifier, in: Advances in Intelligent Data Analysis V, Springer, 2003, pp. 254–264. [30] F. Klawonn, A. Keller, Fuzzy clustering based on modified distance measures, in: Advances in Intelligent Data Analysis, Springer, 1999, pp. 291–301. [31] Y. Lei, J. Bezdek, J. Chan, N. Vinh, S. Romano, J. Bailey, Extending information-theoretic validity indices for fuzzy clustering, IEEE Trans. Fuzzy Syst. PP (99) (2016), doi:10.1109/TFUZZ.2016.2584644. 1–1 [32] M. Lichman, UCI machine learning repository, 2013. [33] J. Lin, Divergence measures based on the shannon entropy, Inf. Theory IEEE Trans. 37 (1) (1991) 145–151. [34] S. Miyamoto, Y. Agusta, An efficient algorithm for l1 fuzzy c-means and its termination, Control Cybern. 24 (1995) 421–436. [35] S. Miyamoto, Y. Agusta, Algorithms for L1 and Lp fuzzy c-means and their convergence, in: Data Science, Classification, and Related Methods, Springer, 1998, pp. 295–302. [36] J.R. Munkres, Topology, second ed., Prentice Hall, Prentice Hall, Upper Saddle River, NJ 07458, 20 0 0. [37] F. Nielsen, S. Boltz, The burbea-rao and bhattacharyya centroids, Inf. Theory IEEE Trans. 57 (8) (2011) 5455–5466. [38] F. Nielsen, R. Nock, Sided and symmetrized Bregman centroids, Inf. Theory IEEE Trans. 55 (6) (2009) 2882–2904. [39] R. Nock, F. Nielsen, S.I. Amari, On conformal divergences and their population minimizers, IEEE Trans. Inf. Theory 62 (1) (2016) 527–538, doi:10.1109/ TIT.2015.2448072. [40] C. Qiu, J. Xiao, L. Han, M.N. Iqbal, Enhanced interval type-2 fuzzy c-means algorithm with improved initial center, Pattern Recognit. Lett. 38 (2014) 86–92. [41] A. Saha, S. Das, Geometric divergence based fuzzy clustering with strong resilience to noise features, Pattern Recognit. Lett. 79 (2016) 60–67. [42] M. Teboulle, A unified continuous optimization framework for center-based clustering methods, J. Mach. Learn. Res. 8 (2007) 65–102. [43] C.J. Veenman, M.J. Reinders, E. Backer, A maximum variance cluster algorithm, Pattern Anal. Mach. Intell. IEEE Trans. 24 (9) (2002) 1273–1280. [44] C.H. Wu, C.S. Ouyang, L.W. Chen, L.W. Lu, A new fuzzy clustering validity index with a median factor for centroid-based clustering, IEEE Trans. Fuzzy Syst. 23 (3) (2015) 701–718, doi:10.1109/TFUZZ.2014.2322495. [45] J. Wu, H. Xiong, C. Liu, J. Chen, A generalization of distance functions for fuzzy-means clustering with centroids of arithmetic means, Fuzzy Syst. IEEE Trans. 20 (3) (2012) 557–571. [46] S.D. Xenaki, K.D. Koutroumbas, A.A. Rontogiannis, A novel adaptive possibilistic clustering algorithm, IEEE Trans. Fuzzy Syst. 24 (4) (2016) 791–810, doi:10.1109/TFUZZ.2015.2486806. [47] R. Xu, D. Wunsch, et al., Survey of clustering algorithms, Neural Netw. IEEE Trans. 16 (3) (2005) 645–678. [48] K.Y. Yeung, W.L. Ruzzo, Details of the adjusted rand index and clustering algorithms, supplement to the paper “an empirical study on principal component analysis for clustering gene expression data”, Bioinformatics 17 (9) (2001) 763–774. [49] J. Yu, Q. Cheng, H. Huang, Analysis of the weighting exponent in the fcm, IEEE Trans. Syst. Man Cybern. Part B 34 (1) (2004) 634–639, doi:10.1109/ TSMCB.2003.810951. [50] W.I. Zangwill, Nonlinear Programming: A Unified Approach, vol. 196, Prentice-Hall Englewood Cliffs, NJ, 1969.