Internal Validity Index for Fuzzy Clustering Based on Relative Uncertainty

Refik Tanju Sirmenand Burak Berk üstünda?

1Graduate School of Science Engineering&Technology,Istanbul Technical University,Istanbul,34469,Turkey

2Faculty of Computer&Informatics,Istanbul Technical University,Istanbul,34469,Turkey

Abstract: Unsupervised clustering and clustering validity are used as essential instruments of data analytics.Despite clustering being realized under uncertainty,validity indices do not deliver any quantitative evaluation of the uncertainties in the suggested partitionings.Also,validity measures may be biased towards the underlying clustering method.Moreover,neglecting a confidence requirement may result in over-partitioning.In the absence of an error estimate or a confidence parameter,probable clustering errors are forwarded to the later stages of the system.Whereas,having an uncertainty margin of the projected labeling can be very fruitful for many applications such as machine learning.Herein,the validity issue was approached through estimation of the uncertainty and a novel low complexity index proposed for fuzzy clustering.It involves only uni-dimensional membership weights,regardless of the data dimension,stipulates no specific distribution,and is independent of the underlying similarity measure.Inclusive tests and comparisons returned that it can reliably estimate the optimum number of partitions under different data distributions,besides behaving more robust to over partitioning.Also,in the comparative correlation analysis between true clustering error rates and some known internal validity indices,the suggested index exhibited the highest strong correlations.This relationship has been also proven stable through additional statistical acceptance tests.Thus the provided relative uncertainty measure can be used as a probable error estimate in the clustering as well.Besides,it is the only method known that can exclusively identify data points in dubiety and is adjustable according to the required confidence level.

Keywords: Machine learning;data science;clustering validity;fuzzy clustering;uncertainty;intelligent systems;data analytics

1 Introduction

Clustering is a widely used interdisciplinary technique for classifying dimensional data objects by categorizing them into subsets based on specified similarity or dissimilarity measures.Due to it facilitates modeling and discovery of relevant knowledge in data [1]it is an essential part of many intelligent systems in vast areas,with a recognized prominence.Data analysis applications claim to explore multivariate real-life data of certain domains and extract hidden structures in them for various practices.Clustering is therefore one of the key methods of decision-making in machine learning as well[2].

There are diverse dichotomies in terms of clustering types,such as hardvs.soft,hierarchicalvs.flat,model-basedvs.cost-based,parametricvs.non-parametric,each with its implementations,serving different clustering aims [3].These aims are worked to achieve through different algorithms that use relevant measures like inter-cluster separation,intra-cluster compactness,density,gap,normality,etc.Algorithms can comply with different approaches such as centroid-based k-means(cf.[4]for its origins),agglomerative hierarchical single[5]and complete linkage[6],spectral[7],mixture probability models[8,9],density-based DBSCAN[10],and so on.

Among a choice of algorithms,each with its relative advantages [11],fuzzy methods generalize hard-decision techniques by using fuzzy measures and distributing the membership degrees to each cluster[12,13].This approach helps to deal with inexact systems by providing feasibility to utilize fuzzy outcomes and perform rule-based classifications.Continuous progress observed in the applications of this technology is evident.A wealth of material is available on the topic including[14-16].

Quite many of the ongoing efforts are on the analysis and improvement of the clustering accuracy,also on the complexity performances[17-20].Some studies instead try to further explore the clustering theory,which could even serve to develop new approaches and algorithms.In[21],the statistical aspects of clustering are discussed and the focal questions are dealt with from the statistical perspective.Also[22]explains how correlation clustering can be a potent addition to data mining.Besides,the quality and efficiency are assessed and some useful metrics are suggested in several studies like[23-26].

Dependent largely on the structure of data,clusters obtained by a method may not necessarily be revealing for the respective application.Hence the validity of the partitioning needs to be evaluated so that the data model and the applied methods can be refined.As seen in Fig.1 and also suggested in[27],cluster validation“should be part of any cluster analysis as integral to developing a classification model”.

Figure 1:The ground of clustering validation

This quantitative evaluation process involves the following main issues:[27]a) Checking the randomness of the data,which can be determined by measuring cluster tendency.(Some measures such as Hopkins statistics,stability index,or some visual methods have been proposed to test the spatial randomness of the data [28-31]).b) Estimating the optimal number of clusters.c) Determining the compliance of the results to the data without any prior information.d)Comparing the results against an externally provided template.e)Comparing two sets of clusters to specify the relatively better one.

The first three tasks require unsupervised methods that use only the intrinsic information to be obtained from the data,thus called internal methods.In contrast,supervised methods deal with measuring how well the results fit the prespecified external information (typically class labels) not available in the data set.Rather than being a distinct type,relative methods are a special use of related measures,to compare results obtained from different methods or the same method with different parameters[27,32].

1.1 Literature Overview

There are quite a few comparable internal and external methods and criteria that have been proposed to quantify validity.The validity function offered in[33]helps measure the cluster overlaps.The validity of a partition has also been discussed in many texts as [34]and an overall average compactness and separation measure was suggested for fuzzy clustering.Some works summarize,compare and evaluate the proposed validation measures from different aspects[35,36].

Since the ground truth reference is available in external validation,the decision of which clustering result is closer to the truth over a comparison criterion is independent of the underlying methods or data structures.Comparison criteria involve pair-counting and/or information-theoretic measures,entropy,purity,or the like which generally relate to diversity.Some recognized ones include the Jaccard coefficient[37],the Rand index[38],the adjusted Rand index[39],the adjusted mutual information[26](better especially when dealing with unbalanced small clusters[40]),the Hubert statistics[40],and the principal component analysis based stability score[41].In addition,[3]and[42]provide an overview of comparison criteria and their properties,and[26]specifically discusses some information-theoretic measures.

Internal indices on the other hand realize their evaluations in the absence of reference information about the data.Therefore,measures need to be devised from the data statistics.Hierarchical clustering schemes are mostly validated using the specific cophenetic correlation coefficient measure [43,44].However,typical unsupervised measures for single schemes arecompactness,which represents how cohesive the objects in a cluster are,separation,which represents how distinct one cluster is from the others,or a combination of these [27].A vast literature is available explaining them with variations,such as[3,27,42].Validity is determined through statistical hypothesis testing based on these criteria.Besides,the other major objective that internal indices serve is to estimate the optimum number of clusters,by testing a range of cluster counts and determining the number that best yields the criteria.

Validity indices specifically designed for fuzzy clustering calculate measures usually over fuzzy membership.While some require using also the data,others solely or mainly involve membership weights[45,46].In this case,the sensitivity to the fuzzifier and the cluster count needs to be accounted for[3].

Some commonly used internal indices include Calinski et al.[47],Davies et al.[48],Silhouette[49],Xie et al.[34],Dunn’s Index[50],and its modified versions such as Generalized[51],Alternative[52,53],and Modified[54]Dunn’s Index.Further internal measures are discussed in[42].Also in[55],10 validity indices specifically for fuzzy clustering are reviewed.

1.2 Observations and Rationale

Validity indices competently deliver the essential inherent properties.Suggested methods measure the criteria through the inter-cluster and intra-cluster variances,entropies,and the like,evaluate the(dis)similarities,scrutinize the analysis as a whole,and then approximate the overall validity.However,it should be noted that the main clustering decisions may be made on some samples(the size issue),or distorted sets (the measuring-error issue).It was emphasized in [3]p.596 that,internal cluster validation “is more difficult than assessing the model fit or quality of prediction in regression or supervised classification,because in cluster analysis,normally true class information is not available”.

Unsupervised methods optimize their objective functions over the established criteria.Yet maybe such functions,to some extent,are measuring their conformity with the underlying clustering method,as much as the quality of the clustering result[56].Moreover,a method may likely favor clusterings realized on the same criteria as itself.A detailed discussion on some validity indices that produce misleading results for the k-means algorithm on data with skewed distributions is presented in [42].Also[57]shows that some analyzed indices were observed to be biased in certain conditions.

Furthermore,clustering is a classification kind process applied under uncertainty.Algorithms of the purpose are designed to partition given data,even though there should be no meaningful clusters in a random population[28],[31].Since the number of partitions can theoretically go up to the number of data points,methods based mainly on improving (dis)similarity criteria by ignoring a confidence parameter may result in over-partitioning.Besides,in the validation of fuzzy clusterings,statistics of data points assigned with higher degrees of confidence have a subordinate relevance for credence,since they comprise limited information about uncertainty,that indeed appears in weakly assigned members.

Clustering is most probably part of a larger application.The decisive need in such an ambiguous case heavily based on statistics is a plausible method that estimates the probability margin of the anticipated actual error.In the absence of such an estimate,the resultant clustering has acquiesced as is.By with such a surmise,any probable clustering error would be dragged forward to the later stages of the system,regardless of the technique employed.Conversely,having such a measure of uncertainty,for a single observation or the whole clustering,would be very instrumental.Therefore,the accuracy performance of the performed clustering could be better approached by estimating the degree of uncertainty,apart from validity.Nevertheless,uncertainty and validity are not reciprocal.

From these,we can conclude that a labeling decision is,in a sense,a statistical test of the hypothesis that a sample data point comes from a particular cluster population at some level of confidence.Including a confidence level premeditated according to the application needs,therefore,reduces the inherent uncertainty in evaluations.As the term validation suggests,the correct estimation of optimal partitions is the premise of a valid clustering so that fewer labeling errors.Thus,a higher correlation between the measured validity index and actual clustering error rate indicates a stronger monotonic relationship.

1.3 Method and Organization

Indeed respecting the fruitful efforts,revisiting the communal perception of the objective of validation in light of these considerations may be beneficial.As both intra-cluster similarity and inter-cluster dissimilarity increase,mean uncertainty in labeling should consequently decrease.Viz,the objective of clustering validation may be reformulated as minimizing the mean uncertainty in labeling assignments measured against defined criteria.Maximizing overall statistical confidence mathematically complies with maximizing the weights of the determined memberships in fuzzy clustering.This approach will also enable identifying data objects at dubiety state.The prominence of such information for other fields like machine learning is apparent.

This study tries to address these issues and suggests a purposive measure that provides an estimate for the level of uncertainty in realized fuzzy-family clusterings.The ensuing section reformulates the objective function as optimization of intra-cluster discordance and inter-cluster proximity,over uncertainties.The measure can be derived mainly by perusing weakly classified members’appointed probability weights with a designated margin of confidence,as introduced below.

The method has been tested on numerous samples in diverse distributions and the results were compared with some well-known internal validity indices.An exclusive comparative analysis of the correlations between the indices and the measured actual clustering errors is also presented here.In addition,acceptance tests were applied to the obtained results as well,which are generally neglected.

In the remainder of this paper,Section 2 discusses the topic from the stated perspective,explains the envisaged methods,and introduces the proposed measures,Section 3 describes the details of the tests applied,including the acceptance tests,and Section 4 presents the obtained results.This is followed in Section 5 by the assessments and conclusions in respect to the canonical index properties set out.

2 Materials and Method

Relying on the discussions so far,we can view the decision to label a sample data point into a particular cluster as a statistical test of the hypothesis that it comes from that cluster population at a certain level of confidence.Including the confidence level in evaluations will help manage inherent uncertainty in decisions.Established on this approach,the purpose of a validity index can be reformulated as minimizing mean uncertainty of the overall clustering process,measured on defined criteria.

The objective function of the proposed novel internal clustering validity index reaches its minimum at the point where compactness and separation of clusters are optimal,accorded by the given level of confidence.Below first the necessary definitions are provided within this framework of the relevant mathematical rationale.Then,the method is explained in detail,and its main advantages over other indexes are broadly highlighted.

2.1 Relative Uncertainty and Clustering

Clustering is a decision-making process under uncertainty relying on quantitative criteria.Under uncertainty,every observation is subject to distortion,by measurement errors and/or various interfering effects.The distance of observation to the sample mean i.e.,Δm=|-m| is the absolute uncertainty.Yet,how large the absolute uncertainty compared to the mean defines below therelative uncertainty:[58]

As the expression (1) suggests,theδmdecreases byΔm.To explore further,the commonly used k-means algorithm,as an example,tries to converge to local minima(through the Voronoi iteration)to reduce the sum of squared distances between the data points and the centroid[59].Yet,the fuzzy c-means‘FCM’algorithm introduces the additional fuzzification exponent parameter that decides the level of cluster fuzziness[12,13].By minimizing the objective function,the data points are associated with every cluster withmcweights(respecting the rule ofΣmc=1,0 ≤mc≤1,1 ≤c ≤k,k:number of clusters),as themvalues indicate the membership probabilities.Ultimately the points are assigned to the clusters of the highest probabilities,i.e.,mia=max(mic)is the assignment membership weight.The relevance of the assigned miavalues depends on the decided number of clusterskand the distances to cluster centroids determined by the associated data points.Accordingly,as the accuracy of miavalues enhances,the meanΔm,and correspondinglyδmdecreases,so does the mean relative uncertainty of the system.

The above remarks lead us to the hypothesis that when the data set is divided into the optimal number of clustersKand the points are labeled to establish this optimality,the overall relative uncertainty of the system is expected to be at a minimum.Therefore,the validity of clusterings can be estimated by measuring and comparing the total relative uncertainties.Furthermore,from the uncertainty perspective,the magnitude of the fuzzy assignment weight is statistically irrelevant,as long as it satisfies the desired confidence level.Hence the question ofvaliditycan be reformulated as,whether the hypothesis that the data points truly come from the associated cluster populations proves,at a certain level of confidence.As with the number of assumed partitionskcan theoretically go up to the number of data pointsn,it can be suspected that basing the validity method solely on improving similarity and dissimilarity criteria ignoring the confidence and uncertainty parameters may lead to over-partitioning,defined as k＞K.

This requires designating an interval that specifies the upper and lower margins of error,for a given confidence level.Moreover,for our topic,a weight beyond the upper bound is an indication that no cluster other than the one yielding the highest probability is close enough to be graded(i.e.,astrongmembership).Therefore,we only need to consider here the lower bound when determining uncertainties.Any association below this bound can be assumedweakand thus uncertain.

2.2 Uncertainty Boundary and Weak Members

Themprobabilities essentially depend on the intra-cluster and inter-cluster variances (i.e.,thecompactness,andseparation).Due to numerous detrimental effects,data points may shift too close to a neighbor cluster’s boundary,which could cause labeling errors.Such 2 points are marked in Fig.2.Here a 3D example reference space is assumed,which can be easily abstracted to N dimensions.Different colors represent different clusters.Thedaanddnare the vectorial distances of the points on the similarity measure to the assigned and the next-most-probable clusters’centroids ciaand cinrespectively.That means,for data pointi,dia=||i-cia||and din=||i-cin||.

Figure 2:Peripheral weak members

The members on the periphery of a cluster are the ones being under the most risk of incorrect labeling if there exists another cluster too close.Ipso facto,suchweak membersare assigned with lowermweights.Deciding an uncertainty boundary(will be denoted byδb)gives us the capability of classifying the members assigned with lower weights asweak members.Say{w}represents the weakmembers set.Then a data pointiwith an assignment(i.e.,the maximum)membership weight mialess thanδbis to be identified as a weak member.Below the expression(2)provides the formal definition of a weak member.

The compactness of every cluster could vary due to different distribution effects,so a-roughly derived-overallδbwould be misleading.Thus uncertainty boundaries should be exclusively computed on a per-cluster basis for the desired confidence level (which is 1-α),and the weak members are identified in accordance.Eq.(3)gives the general formula of the uncertainty boundary.Here μmandσmrepresent the mean and standard deviation ofmweights,zαis the reference z-score for designated confidence(1-α),andnis the number of members.

2.3 Dubiety Boundary and Members in Dubiety

When all data points of a cluster are right at their centroids then μ(da) andσ(da) should return zero.For all cases other than this theoretical one,μ(da)＞0.On the other hand,if dia/din=1 then the pointiis at thelimbussince it is at an equal distance to both centroids as expression(4)depicts.Thelimbostate manifests the highest level of uncertainty.

In the‘FCM’algorithm[12,13],the membership weight miaof data pointiin the clusterais defined as below in Eq.(5)(k:number of clusters,ca,cc:centroids,e:fuzzification exponent):

In this equation,||i-ca||and||i-cc||are essentially consistent with the above-mentioned distances.Then,dia/dicgives the proportion of the distances to different cluster centroids.As this proportion gets closer to 1,the anticipated confidence level in the classification decision for pointidecreases.Correspondingly,let us say miaand minbe the maximum and the next highest fuzzy membership weights ofirespectively.So,

Aproximityvalueγclose to 1 in Eq.(6)indicates that it is not clear which cluster the data point belongs to(which corresponds to the case of a Silhouette index close to zero).Analogous to Eq.(2),if represents the set of members in dubiety state,we can designate the members,as in Eq.(7):

This means that cluster members withγivalues less than or equal to the dubiety boundary constitute the set of members in dubiety state adjacent to other clusters.The following definition formally provides a generic boundary to identify data points in dubiety state,with the foregoing‘limbus’at the lowest end.

Based on Chebyshev’s inequality,the probability of the observations beingrstandard deviations away from the mean is at least(1-1/r2)[58].Eq.(9)justifies the dubiety boundary definition in Eq.(8).

Hence,proximity values lower than or equal tobboundary should fall into the dubiety range.Formulating the dubiety boundary based on Chebyshev’s inequality makes it valid not only for Gaussian but for a wide class of arbitrary probability distributions[60].

2.4 The Relative Uncertainty Index of Clustering

The optimal number of partitions (K) of a given dataset at the desired level of confidence is expected to achieve where the overall uncertainty rate is minimum.Theoretically,kcan go up tonas it is presumed that the data set is suitable for partitioning.1It may be necessary to decide on cluster tendency first(please cf.related references in the previous section).So,the relative uncertainty index(that will be referred to as‘rU’hereafter)forkpartitions can be formulated as in Eqs.(10)and(11):

Here,πcandγcrespectively denote thediscordance(as the opposite ofcoherence)andproximity(as the opposite ofseparation)of clusterc.Thus the objective function is to minimize the rUkvalue as in Eq.(11).The cluster discordance can be computed through Eqs.(12)and(13)given below.

δbaand ncare theuncertainty boundaryand the number of members of the clusterc.Also,tαis the student’st-value corresponding toα,and smais the standard deviation of mavalues(i.e.,normalized miaweights,please cf.Eq.(19))for cluster members.Since(Δmia/)is the intrinsic relative uncertainty in the pointi’s membership weight (cf.Eq.(1)),then (δi×nc) in Eq.(12) gives the total relative uncertainty ofc,which represents the intra-clusterdiscordance.

On the other hand,referring to Eq.(6),clusterproximitybased on uncertainties can be computed as:

Likeδbain Eq.(13),δbnin Eq.(18) is theadjacencyboundary for the mivalues (i.e.,normalized minweights,cf.Eq.(19)),and smnis the standard deviation of mnvalues.So in Eqs.(16)and(17),ma＜δbafor data pointiindicates thatiis in the weak members set{wc},and similarly if mn＞δbnit is in the adjacency set{ac}.Union of them constitutes theproximityset{γc}of clustercdefined in Eq.(15).The mean of theγimatrix of{γc}members thus corresponds to the averageseparationfrom nearest clusters,i.e.,Eq.(14)(npis the set members count).

An important issue to note is that all of the raw miaand minmembership weights must be normalized first by their standard deviations as described in Eq.(19)below(where mixhere denotes miaor min)to make the cluster-wise calculations invariant to thekchanges.Such normalization makes all membership values more robust to their monotonic dependence onkand sensitivity to the fuzzification exponent,so that serves to prevent under partitioning by using the same order of magnitudes.(A section is devoted to the importance and effects of measure normalization in[42].)

In epitome,the unitless relative uncertainty index rUkprovides a blind estimate of the average relative uncertainty of the fuzzy clustering operation for k partitions.The optimum number of partitions K is the k where rUkreaches its minimum,by minimizing theπcwhile maximizing theγc.

It should be heeded that being the desired confidence level(1-α)can be set gives the additional ability to adjust the index according to the respective application.Moreover,besides providing an estimation of the optimum number of partitions,the presented ‘rU’index can specifically identify members in dubiety and the weak members of each cluster(via Eq.(7),and Eq.(16)).

2.5 Index Properties

Some desirable properties of an internal validity index can be deemed as follows:

? Reliability:A reliable index is expected to yield consistent results on data with as many different underlying frequency distributions as possible,without assuming Gaussian or such.

? Validity:Under and over partitioning would result in higher clustering errors.As the title suggests,the correct estimation of optimal k is the premise of valid clustering,so then fewer labeling errors.Hence,the calculated index is expected to correlate with measured true clustering errors.

? Robustness to over-partitioning:Since unsupervised methods attempt to partition data even it does not contain any clusters,the need to priorly apply cluster tendency tests arises[28,31].Thus,over(and under)partitioning is a threat the index should avoid.

? Independence of measure:With no stipulation on the measure(as Euclidean,Mahalanobis,or such),it is supposed to run independently of the underlying similarity measure.

? Informativeness:Calculation outcomes can be elucidative on intrinsic statistics of the data to serve further scopes.

? Optimality:Deriving adequate internal statistics from a sample set rather than the entire population data (which may not always be possible) is desirable.This practice would mean lower time and memory complexities.

? Efficiency:Another creditable property is the efficiency of the index,mainly in terms of time complexity,which may become quite significant especially in real-time applications.

Numerous diverse tests were conducted mainly towards these canonical properties we suggest,and the results were also compared with some of the well-known internal validity indices,as shared below.Another point worth mentioning is thatacceptance testsas well,which are mostly neglected,were applied to the results obtained under different conditions.Tests are explained in the ensuing sections.

3 Tests and Comparisons

3.1 Test Data

The tests were performed on various numeric structural data both artificially generated2The datasets generated during the current study are available from the corresponding author upon request.as well as retrieved from online repositories (e.g.,http://cs.joensuu.fi/sipu/datasets,https://www.kaggle.com/datasets,https://data.world/datasets/clustering,http://archive.ics.uci.edu/ml,with files such as S2,S3 [61],A1,A2 [62],Mall_Customers.csv,etc.).3Specifics of the test data were 2 ≤D ≤13(one with D=912),50 ≤n ≤5250,3 ≤K ≤35(where‘D’,‘n’,and‘K’here respectively represent dimension,size,and number of designed partitions),in distributions Gaussian,Poisson,Weibull,Nonspecific.Being the test data in different distributions was particularly mulled.

3.2 Clustering

Clustering was carried out using the ‘FCM’algorithm,with random initiation.A non-partial clustering was assumed,thus no group was left empty when all of the points were eventually assigned.Also,the data was assumed non-overlapping,so then the data points were associated with the cluster of the highest membership probability.The fuzzification exponent parameter was 2.0,the minimum improvement per iteration was 10-6,and the maximum number of iterations was 200.Parameters were selected in common standards for all subjects,as no significant effects were observed on validation tests.

3.3 K-estimation Tests

For all cases,validity metrics were computed for the ‘rU’index,as well as 8 additional wellknown internal indices,namely Calinski-Harabasz,Davies-Bouldin,Silhouette,Dunn,Alternative,Generalized,and Modified Dunn,besides Xie-Beni.(Abbreviations CH,DB,S,D,AD,GD,MD,XB are used to respectively stand for these indices throughout this text.)Every set was tested at least 35 times for each K,as incrementing n in steps of 25.Besides,the whole clustering and index computation process was repeated at least 25 times before determining the optimal k on average,to avoid the possible effect of the random initiation in the‘FCM’.

3.4 Correlation Analysis

For correlation analysis,additional artificial noisy data sets were generated in Gaussian,Weibull,and Poisson probability density distributions (each with K=8,n＞600),for Gaussians to represent the middle,and the other 2 represent two possible extremes.Various tests were conducted on at least 600 different sets for every noise environment.

Correlation coefficients were computed to scrutinize the strength of the relationship between the relative behaviors of the measured accuracy performances and the validity indices including rU.The specified confidence level for correlation was 95%during the tests,and the maximum acceptable performance error wasFPr＜0.05(please see the related title below).

Pearson’s product-moment correlation coefficients were assumed principal,yet Spearman’s rank correlation coefficients were evaluated as well.Computed coefficient magnitudes were interpreted as±r2indicating:.0-.19:very weak,.20-.39:weak,.40-.59:moderate,.60-.79:strong,.80-1.0:very strong[63].

3.5 Performance Criteria

Clustering accuracy performance was measured by comparing the estimated and provided ground-truth labels using two external indices depicted below:

?FPr:The false-positive clustering error rate ‘FPr’identifies the rate of false-positive (FP)mappings obtained from the comparisons that can be stated as in Eq.(20) (ciois the original ground-truth label,ciais the assigned label,andnis the number of data points in the population).

When a complete(i.e.,non-partial)clustering was assumed,as all of the points got assigned,no group was left empty.Since we were to compare against the ground-truth partitions,a non-overlapping point could not belong to more than one group simultaneously,and it is eventually assigned to a particular one,because of the complete clustering assumption.This means an FP assignment that occurred in some cluster should be the concurrent counterpart of a false-negative(FN)assignment in another cluster,and under these conditions,ΣFP=ΣFN.

?aRI:To cover the overlaps,also the Adjusted-Rand index[40]was computed,which is a version of the Rand index adjusted for chance,as described in[38].

3.6 Acceptance Tests

Even if significant correlation coefficients satisfying the confidence level were observed in all studied environments,the significance of the differences between the correlation coefficients obtained in different environments should also be tested before the correlation can be eventually accepted.(We encourage to confer to[64].)Hence,the hypotheses have been established to test the significance of the differences asH0:ρ1-ρ2=0andH1:ρ1-ρ2＞0(ρbeing the correlation coefficient).

Since the sample populations were gathered from three principal environments(namely Gaussian,Poisson,and Weibull),the tests were conducted for every pair,let’s sayρg-ρp,ρp-ρw,andρg-ρw.Afterward,if all three of the pairwise tests returned that theH0was not rejected at the desired level of confidence then the consistency of the correlation decision was accepted for that variable;it was rejected otherwise.

For the null-hypothesis tests,the criterion of significance was assumed as 0.05 (i.e.,zα=1.96).The tests were applied separately both to the attained Pearson and Spearman correlation coefficients for every variable in question.Pairwise z-scores zgp,zpw,zgwwere computed and compared with the reference z-scorezα.In conclusion,if zxy＜zαthen the null hypothesis could not be rejected at the specified level of confidence,thus the differences between the predictive values were not of significance.(Note that attaining all 6 separate zxy＜zαresults was mandatory for accepting the consistency of a single variable.)

The collected results from the tests are summarized and discussed below.

4 Results and Discussions

4.1 K Estimations

The optimum number of partitionskestimations by the proposed‘rU’index were quite consistent with the other indices.Fig.3 exemplifies divergences between k-estimates and true K on 148 samples of D=2,160 ≤n ≤480,3 ≤K ≤15,in different distributions.The bars indicate the absolute mean divergence percentages of K estimations from the true K.

Figure 3:K-k divergences

However,peculiar cases that deserve to be marked were also observed.Fig.4 (left-hand side)shows some sample data (D=2,n=160,K=4) in clusters using different colors (Red crosses point the centroids;the weak members are marked with magenta circles,and members in dubiety with black diamonds).On the right-hand side,the optimum number of partitions estimated by the indices is marked with red circles(occurring at the minimum or maximum depending on the objective function of the related index).

Figure 4:Clustering and K estimations of data set m2_4_160

In this example,almost all tested indices correctly estimated the designed 4 partitions when examined within the range of 2＜k＜12.However,most indices returned higher estimates when the inspection window was expanded,as pictured in Fig.5.The left-hand side of the figure shows the estimations for the range of 2-22,while the right-hand side shows the range of 2-74.Even occasionally,more than 1 local optimum may appear(as can be seen with the‘D’and‘MD’indices in k:2-22 range).

Figure 5:Over partitioning of m2_4_160

Several such peculiarities were encountered during tests.This observation tells that even if the optimumKvalue can be accurately determined within a given range,over partitioning can occur when the range is expended without considering the uncertainties in the putative clusters.

4.2 Correlation Results

Conducted tests to explore relationships between the considered indices and the true errors returned various levels of correlations,as listed in Tab.1(G,P,and W respectively denote the Gaussian,Poisson,and Weibull distribution environments).As it can be noticed in the table,the proposed‘rU’index exhibited the highest(very strong)correlations among all in each noise environment tested.

Table 1:Correlations results

4.3 Complexity Comparison

The ‘rU’index uses only the membership weights,while many of the others need to reach the data itself.It can be counted as a benefit in terms of memory requirements.Besides,performing primary calculations only on the weak members also marks the additional optimality of the ‘rU’.This optimality reflects on the time complexity as,the‘rU’index involves only the uni-dimensional 1stand 2ndlevel membership weight matrices for the calculations,regardless of the data dimension.Hence the time complexity of distance calculations,such as compactness and separation,increases at some indices according to the data dimension,while in the ‘rU’it remains monotonically dependent only on the size.

Tab.2 implies that the time complexity of the ‘rU’is considerably better compared to many[51,54,65].Consequently,observed run times vindicated the relative efficiency of the‘rU’.While the‘S’index exhibited the far worst runtimes of all,the‘XB’yielded faster processing than the‘rU’,yet it showed weaker correlations with the measured clustering errors,besides failed in the acceptance tests.

Table 2:Time complexities

4.4 Acceptance Tests

It was also observed that the‘rU’index passed all acceptance tests,while the Xie-Beni index failed in some cases due to higher z-differences over the critical value(z=1.96),as seen in Tab.3.This casts doubt that such indices may be likely to exhibit instabilities on some data distributions.

Table 3:Acceptance test results

5 Conclusion

The prevalence of research on clustering and cluster validation,which are among the essential tools of data analytics,reveals the importance of the topic.Although the clustering process is exercised under uncertainty,and validity indices provide explanatory insights into the intrinsic properties of the data,they do not deliver any quantitative assessment of the possible uncertainties in the realized partitioning.They may also be biased because they measure,to some extent,their conformity with the underlying clustering criteria.Several studies report such misleading results.Besides,it is also observed that ignoring the required confidence level may lead to over partitioning.On the other hand,considering a confidence parameter can reduce the risk of over partitioning,thereby better preventing potential errors from being carried towards subsequent phases of applications like machine learning where clustering is likely a part of.Moreover,having an uncertainty estimation can be also utilized to refine predictive functions.

In light of these motivations,this study mainly focuses on clustering validation and proposes a novel internal method designed specifically for fuzzy clustering,based on relative uncertainty.Through discussions of the “validity of validation” itself,it incorporates the confidence parameter to the evaluation of criteria and reestablishes the objective as optimization of the level of uncertainty.To this end,here introduced the mathematical definition of weak members,as well as the method of estimating uncertainty,apart from validity.The method is independent of size,underlying density distribution,similarity measure,or clustering algorithm that membership weights are obtained with.

The proposed relative uncertainty index,named ‘rU’,satisfies all canonical aspects of an unsupervised validity measure.Inclusive tests and comparisons have shown that it can reliably estimate the optimum number of partitions in different data distributions without stipulating Gaussian or any other and it is comparatively robust to over partitioning.It uses only one-dimensional membership weights regardless of the data dimensions,similarity measure,and the like.The impact of the resultant low complexity from this optimality has also been positively observed in runtime efficiencies.

A competent clustering validity measure is expected to correlate with true error rates.Relevant tests have also shown the highest strong correlations between true error statistics and the‘rU’index in all test environments,compared to the others.This relationship has been proven consistent through statistical acceptance tests as well,which is mostly neglected.

Along with the mentioned contributions,it is probably the first fuzzy validation measure adjustable to the application needs,as includes the confidence parameter in the evaluation.The uncertainty measure as an error probability estimate can be used as a metric as well,in the credence of the realized fuzzy clustering.Another significant novelty that can be quite instrumental for tuning the later stages of the system involved is the ability to exclusively identify the weak members in the designated clusters.

The efficacy of the proposed method is most likely to manifest itself especially with unbalanced or distorted distributions with higher uncertainty.However,the fact that it was specially designed for fuzzy clustering should be noted as a limitation.Besides,datasets more suitable for hierarchical clustering need to be studied separately.A further research opportunity opened is associating the provided uncertainty estimate to an appertaining cost function for incorporating the risk assessment into classification decision rules.Also,designing a layered iterative classification algorithm that makes use of the diagnosis of weak members is another promising future work.

Acknowledgement:The authors would like to thank the editors for reviewing this manuscript.

Funding Statement:The authors received no specific funding for this study.

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.