Ask for suggestions on clustering methods on a large dataset with mixed types of variables

Question

I need to build segmentation on a large customer dataset with more than 300K records and many variables, including continuous like income and age, ordinal like education level and membership level, nominal variables like occupation and race, binary like gender. I use SAS to perform this task and someone suggest me to do the following? 1. artificially assign numeric values to categorical variables if they have order in some sense, otherwise transform to binary (0,1) 2. proc varclus to reduce variables 3. proc fastclus to generate many small clusters and reduce data size 4. proc cluster for hierarchical clustering based on output files from last step, and determine optimal number of clusters 5. proc tree for final segment result

Is this a valid method? BesidesI have following questions:

1. I would like to know methods to identify and remove outliers other than excluding extreme or abnormal cases from univariate analysis. I also wonder how should I treat missing values in cluster analysis.(at present, I will fill in missing data with means if the missing percentage is not that high, and will stop using variables with lots of missing)

2. For variable selection, my understanding on proc varclus/factor is they only work with numeric variables. Although categorical variables can be transformed into numeric, yet it seems not that sensible from a statistical perspective. what are appropriate ways to select categorical variables?

3. proc fastclus deal with large dataset well, but I wonder it is suitable for my cases since there are mixed types of data. How can I deal with this large data size? is it appropriate for me to just transform categorical to numeric variables and use them in this procedure?

4. proc cluster can use distance matrix other than Euclidean. Therefore, I may use proc distance to calculate Gower's distance which work with all level of measurement as input for clustering. However, it is infeasible for such large dataset. Is that mean this method can not be used on big data? Any idea to solve this problems?

5. Since Wald method should not use Gower's distance, then what are suitable methods for Gower's distance

It will be great if someone can suggest me any appropriate approaches to my segmentation work. thank you.

Answer 1

Similarly to the previous answers, most of the following answer of mine is not specific to SAS, as I use R. However, there is one exception to that - please see below. It seems that there exist substantial research efforts towards development of clustering algorithms for mixed data. More specifically, some algorithms were developed and/or adapted with a focus on categorical data.

In particular, some adaptations of traditional k-means clustering approach include k-modes, fuzzy k-modes, k-histograms and k-populations (for example, see this paper). Other solutions to the problem include hierarchical clustering, including ROCK, CACTUS and others. Probability-based clustering approaches for categorical data include already mentioned Two-Step cluster analysis procedure (seems to be SPSS-specific).

Recently some other streams of research, related to the topic, have appeared. They include using such approaches, as neural networks and genetic algorithms (for examples, comparisons and references, see this paper and this paper), information theory (for example, see this paper and this paper). An interest to the model-based clustering, specifically based on latent class analysis, is also growing (for example, see this paper and this paper - latent tree models - seems to be a mix of latent-based and hierarchical approaches).

Speaking of latent class analysis (LCA), finally, I would like to share the promised SAS-specific relevant information. This paper describes a LCA-based approach, called latent class clustering, and its implementation, using a free SAS add-in, which is available for download on this page.

Answer 2

I won't be answering list items in your question. Partly because it is SAS specific (I don't use SAS). My answer is a sort of general precaution.

Using variables of different type to cluster cases isn't particularly good idea. Because it is unclear how to weight such different variables. Should a continuous feature be weighted equally as a 10-class nominal one? Or weighted 9 times greater because there is 9 dummy variables hiding behind that nominal one? Or weight should be somehow estimated to be in-between (for example based on comparing variance of the one with enthropy of the other)?

Also, attributes of different character naturally call for different distance measure. Euclidean or Manhattan distance are good for scale (interval) variables but using them with binary variables is questionnable. Binary features with "asymmetric" meaning (present vs absent) usually require such coefficients as Jaccard or Ochiai, while Dice coefficient is better for nominal (dichotomous or polytomous converted into dummy) features. It is possible to use popular composite similarity measures like Gower, of course. One should note, however, that Gower is only for hierarchical cluster analysis, and hierarchical clustering is poorly suited for large amount of objects, both practically and theoretically (1, 2). And Gower isn't euclidean or metric distance, it is improper to use hierarchical methods like Ward of centroid with it (may use average, complete, single linkage methods). Finally, it relatively tedious task to investigate/interpret how the clusters erected by the analysis differ in regards to every feature constituting Gower measure, due to their different nature.

Of course, you could work-out a plan to do clustring by subsamples if your overall sample is so large, and then to combine results somehow (various ways are possible) to arrive at a common result, but is quite a hard work.

In SPSS, there exist TwoStep cluster analysis that can efficiently cluster huge amount of objects and also can process interval and nominal variables together. It has also some options to advice the number of clusters and to track down outliers. However it doesn't process ordinal or binary data so far and it has its assumptions; it is not a panacea. (You may search on this site for two-step cluster if you wish.)

Clustering based on mixed-type data is purely a heuristic idea and lacks mathematical or esthetical merit behind it.

There exist a nonlinear transformation in statistical anlysis, called optimal scaling which can convert categorical types of variable into quantitative interval one, but it must have a goal function to "optimize" the transformation for. Theoretically, it could be used for cluster analysis (like it is used with PCA and other dimensionality reduction techniques) but I haven't seen it used so nor tried to use so myself, for now.

Answer 3

I can't give you guidance with SAS, because I donkt use it. I use open source only.

I agree with the answer by ttphns that you should be really careful in combining attributes of different types. You need to weight them carefully (earning $10 more than the other is different from having a shoe size 10 larger) - but do you have a theoretical foundation why your weighting is correct? If your weighting is bad, features might have 0 influence, or the result may depend on a single feature only... I'd go as far as claiming your results become as good as random, and that almost any desired result can be obtained by modifying the weights. So how meaningful will the results be?

As for scalability:

1. If the result is meaningful, it should already be visible on a sample!
2. First make sure your approach works (e.g. on a manageable sample) then consider scale. Wasting time to “big data” something which doesn't work is a popular mistake.
   3. Validate your result. Split your data set - if you get very different results on every part, the result maybe is random.