Clustering with Missing Values: No Imputation …

1 Clustering with Missing Values: No ImputationRequiredKiri WagstaffJet Propulsion Laboratory, California Institute of Technology, 4800 Oak GroveDr., Pasadena, CA algorithms can identify groups in large data sets, such as starcatalogs and hyperspectral images. In general, Clustering methods cannot analyzeitems that have Missing data values. Common solutions either fill in the missingvalues ( Imputation ) or ignore the Missing data (marginalization). Imputed valuesare treated as just as reliable as the truly observed data, but they are only as good asthe assumptions used to create them. In contrast, we present a method for encodingpartially observed features as a set of supplemental soft constraints and introducethe KSC algorithm, which incorporates constraints into the Clustering process. Inexperiments on artificial data and data from the Sloan Digital Sky Survey, we showthat soft constraints are an effective way to enable Clustering with Missing IntroductionClustering is a powerful analysis tool that divides a set of items into a numberof distinct groups based on a problem-independent criterion, such as maximumlikelihood (the EM algorithm) or minimum variance (the k-means algorithm).

2 In astronomy, Clustering has been used to organize star catalogs such as POSS-II (Yoo et al., 1996) and classify observations such as IRAS spectra (Goebelet al., 1989). Notably, the Autoclass algorithm identified a new subclass ofstars based on the Clustering results (Goebel et al., 1989). These methods canalso provide data compression or summarization by quickly identifying themost representative items in a data challenge in astronomical data analysis isdata fusion: how to combineinformation about the same objects from various sources, such as a visible-wavelength catalog and an infra-red catalog. A critical problem that arisesis that items may have Missing values. Ideally, each object in the sky shouldappear in both catalogs. However, it is more likely that some objects will two instruments may not have covered precisely the same regions of thesky, or some objects may not emit at the wavelengths used by one of thecatalogs.

3 Missing values also occur due to observing conditions, instrumentsensitivity limitations, and other real-world WagstaffClustering algorithms generally have no internal way to handle missingvalues. Instead, a common solution is to fill in the Missing values in a pre-processing step. However, the filled-in values are inherently less reliable thanthe observed data. We propose a new approach to Clustering that dividesthe data features intoobserved features, which are known for all objects, andconstraining features, which contain Missing values. We generate a set of con-straints based on the known values for the constraining features. A modifiedclustering algorithm, KSC (for K-means with Soft Constraints ), combinesthis set of constraints with the regular observed features. In this paper, wediscuss our formulation of the Missing data problem, present the KSC algo-rithm, and evaluate it on artificial data as well as data from the Sloan DigitalSky Survey.

4 We find that KSC can significantly outperform data imputationmethods, without producing possibly misleading fill values in the Background and Related WorkGreen et al. (2001) (among others) identified two alternatives to handlingmissing Values: data Imputation , where values are estimated to fill in missingvalues, andmarginalization, where Missing values are ignored. However, im-puted data cannot and should not be considered as reliable as the actuallyobserved data. Troyanskaya et al. (2001) stated this clearly when evaluatingdifferent Imputation methods for biological data: However, it is important toexercise caution when drawing critical biological conclusions from data thatis partially imputed. [.. ] [E]stimated data should be flagged where possible[.. ] to avoid drawing unwarranted conclusions. Despite this warning, data Imputation remains common, with no mecha-nism for indicating that the imputed values are less reliable.

5 One approachis to replace all Missing values with the observed mean for that feature (alsoknown as the row average method in DNA microarray analysis). Anothermethod is to model the observed values and select one according to the truedistribution (if it is known). A more sophisticated approach is to infer thevalue of the Missing feature based on that item s observed features and itssimilarity to other (known) items in the data set (Troyanskaya et al., 2001).Ghahramani and Jordan (1994) presented a modified EM algorithm that canprocess data with Missing values. This method simultaneously estimates themaximum likelihood model parameters, data cluster assignments, and valuesfor the Missing features. Each of these methods suffers from an inability todiscount imputed values due to their lack of full therefore believe that marginalization, which does not create any newdata values, is a better solution.

6 Most previous work in marginalization hasfocused on supervised methods such as neural networks (Tresp et al., 1995)or Hidden Markov Models (Vizinho et al., 1999). In contrast, our approachhandles Missing values even we have no labeled training data. In previouswork, we developed a variant of k-means that produces output guaranteedClustering with Missing Values: No Imputation Required3to satisfy a set of hard constraints (Wagstaff et al., 2001). Hard constraintsdictate that certain pairs of items must or must not be grouped on this work, we present an algorithm that can incorporate softconstraints, which indicate how strongly a pair of items should or should notbe grouped together. In the next section, we will show how this algorithm canachieve good performance when Clustering data with Missing Clustering with Soft ConstraintsConstraints can effectively enable a Clustering algorithm to conform to back-ground knowledge (Wagstaff et al.)

7 , 2001; Klein et al., 2002). Previous workhas focused largely on the use of hard constraints that must be satisfied by thealgorithm. However, in the presence of uncertain or approximate information,and especially for real-world problems, soft constraints are more Soft ConstraintsIn this work, we divide the feature set intoFo, the set of observed features,andFm, the set of features with Missing values. We also refer toFmas theset ofconstrainingfeatures, because we use them to constrain the results ofthe Clustering algorithm; they represent a source of additional Wagstaff (2002), we represent a soft constraint between itemsdianddjas a triple: di, dj, s . The strength,s, is proportional to distance inFm. We create a constraint di, dj, s between each pair of itemsdi, djwithvalues forFm, wheres= f Fm( )2(1)We do not create constraints for items that have Missing values. The valueforsis negative because this value indicates the degree to whichdianddjshould be separated.

8 Next, we present an algorithm that can accommodatethese constraints while K-means Clustering with Soft ConstraintsWe have chosen k-means (MacQueen, 1967), one of the most common clus-tering algorithms in use, as our prototype for the development of a soft con-strained Clustering algorithm. The key idea is to cluster overFo, with con-straints based k-means algorithm iteratively searches for a good division ofnobjectsintokclusters. It seeks to minimize the total varianceVof a partition, , thesum of the (squared) distances from each itemdto its assigned clusterC:4 Kiri WagstaffTable algorithmKSC(k,D,SC,w)1. LetC1.. Ckbe the initial cluster For each instancedinD, assign it to the clusterCsuch that:C:= argminCi((1 w)dist(d, Ci)2 Vmax+wCVdCVmax)(2)whereCVdis the sum of (squared) violated constraints inSCthat Update each cluster centerCiby averaging all of the pointsdj Iterate between (2) and (3) until Return the partition{C1.}

9 Ck}.V= d Ddist(d, C)2 Distance from an item to a cluster is computed as the distance from the itemto the center of the cluster. When selecting the best host cluster for a givenitemd, the only component in this sum that changes isdist(d, C)2, so k-meanscan minimize variance by assigningdto the closest available cluster:C= argminCidist(d, Ci)2 When Clustering with soft constraints, we modify the objective functionto penalize for violated constraints. The KSC algorithm takes in the specifiednumber of clustersk, the data setD(withFoonly), a (possibly empty)set of constraintsSC, and a weighting factorwthat indicates the relativeimportance of the constraints versus variance (see Table 1).KSC uses a modified objective functionfthat combines normalized vari-ance and constraint violation values. The normalization enables a straightfor-ward specification of the relative importance of each source, via a weightingfactorw [0,1].

10 F= (1 w)VVmax+wCVCVmax(3)Note thatwis an overall weight whilesis an individual statement aboutthe relationship between two items. The quantityCVis sum of the squaredstrengths of violated constraints inSC. It is normalized byCVmax, the sum ofall squared constraint strengths, whether they are violated or not. A negativeconstraint, which indicates thatdianddjshould be in different clusters,is violated if they are placed into the same cluster. We also normalize thevariance of the partition by dividing byVmax, the largest possible variancegivenD. This is the variance obtained by assigning all items to a single deciding where to place itemd, the only constraint violations that maychange are ones that involved. Therefore, KSC only considers constraints inwhichdparticipates and assigns items to clusters as shown in Equation with Missing Values: No Imputation Required5-4-3-2-10123456-4-202468101214( a) Data set 1-4-202468101214-4-3-2-10123456(b) Data set 2-4-20246810-4-202468(c) Data set 3 Fig.