Perform clustering on individual data in categories

I am looking for ways to perform clustering on an aggregated category while still using individual data.

For example, assume we have a multitude users that we have acquired through different channels. I would like to cluster groups of channels together, so that it is easier to deal with similar channels in similar ways. However, if I aggregate the user data into averages for each channel, then because these averages are heavily driven by outliers (high-spenders), it doesn't give that much insight to the behavior of the majority of users from that channel.

Is there a way to use the individual user data but still gain insight into and cluster based on the channel they come from?

• I could not relate these sentences: "I would like to cluster groups of channels together, so that it is easier to deal with similar channels in similar ways." and "However, if I aggregate the user data into averages for each channel..."
– Emre
Jan 26 '16 at 22:22
• So I have a ton of individual user data, and each user comes from a certain channel. I want to perform the clustering on the channel that they came from. To do this, I've been just aggregating the data from the users to come up with summary statistics for each channel. However, I would like to still use the individual user data but perform the clustering on the channel. Jan 26 '16 at 22:32

As always clustering is about what is the meaning of distance, since that encodes at least some part of your question. So you question is which channels are similar, where similarity is defined on users. Usually you do not assume some nesting on your instances, but what you have is basically a nesting of users in channels. So you have to incorporate this kind of nesting into the distance / similarity function.

I would start with some observation on similarity function. We denote similarity between instance $i$ and $j$ with $d(i,j)$. Usually this function obeys the following condition $d(i,j)\ge0$ for any $i$ and $j$. Note that we usually have equality only on identical data points. The main consequence of this observation is that we can have basically an identity at user level. What you want is an identity at channel level.

One way would be to define the similarity function like:

$$d_c(i,j) = I_{c_i\ne c_j}d(i,j)$$

where $I_{c_i\ne c_j}$ is $1$ when channel of instance $i$ is different that channel of instance $j$. The main effect is that now all the points from the same channel are considered identical since the distance between them is zero. When the identity function is $1$ the distance is given by your real business distance which should be constructed by you and answer your question.

If you use such kind of function in a hierarchical clustering basically it will start to find first some clusters which are identically with your grouping on channels and later on it will join clusters which are similar. This kind of approach will work even with a kmeans algorithm and perhaps with most of the clustering approaches.

A slight different approach would be to define your $I$ function to return $1-\lambda$ when cluster is different and $\lambda$ when channels are equal, and have $\lambda$ a positive value close to $0$. This will not guarantee that all the clients will go into the same cluster, but it gives you the benefit that you have a slider which you can use to fine tune the compromise between all user of the same channel goes into the same cluster and a distance measure which is more robust to outliers.

A totally different approach from an implementation point of view would be to define a more complex function directly on channel samples. This would be similar with how hierarchical clustering works since in order to joins to clusters it should have a distance function which would measure inter clusters similarity. See more on linkage-criteria. For example average linkage clustering. Note that I said that the approach is different only algorithmic. I would bet that the results would be similar with the first approach.

A totally different approach would be to use a more robust criteria. It is known that sample average is not robust since one point can blow away the estimation. Median instead is much stable. You can use a median or a trimmed mean to have a more robust aggregation values. This would have the advantage that the clustering would be much faster since you would work with channels instead of clients and the running time for computing the clustering would be reduced.

And finally, another approach which comes to my mind would be to go further with comparing channels, but this time using a distance which would be based on statistical tests. I will give you a scenario to clarify. Suppose that your users have an attribute named Weight, which as expected would be a continuous variable. How could you define a distance between the Weight of users of one channel and Weight of users of other channel? If you can assume a distribution, like a Gaussian on that weight you can build a two sample t-test on the two samples which are the two clusters. If you can't assume a distribution you can employ a homogeneity / independent test like two sample KS test. KS test is valuable since does not assume any distribution and is sensitive to both changes is shape and location. If you have nominal attributes you can employ a chi-square independence test. Be careful with what you can use from that tests. In order to have equal contribution for each attribute used in distance function you have to you p-values. Also note that if the test is significant it will have a small p-value, since the null hypotheses for both tests is the independence assumption, which can be translated as same marginal for both samples. So, smaller p-values means bigger distance. You can use $1-\text{p_value}$ or even you can try $\frac{1}{\text{p_value}}$.

• Thanks a ton! I really appreciate all of the thought and time put into your response. This is incredibly helpful! Feb 1 '16 at 2:45
• Helpfull and inspirative! Feb 1 '16 at 20:53
• So I'm wondering how a k-means algorithm would work for the distance metric you defined. Isn't k-means supposed to minimize the within-cluster sum of squares from points to centroids? But the centroids wouldn't have a channel designation. The distance metric is specified for pairwise distance between points, not between points and centroids, unless there's a way to accommodate this? Thanks again for the help! Feb 3 '16 at 20:52
• Obviously I wouldn't have to use k-means, I was just wondering, since you said it could work even with k-means. Feb 3 '16 at 20:54
• Aren't centroids points in the d(i,j) space though and therefore have no channel? For example, if my distance metric was just euclidean distance on R2, then pairwise distance between points takes into account the channel, and points from the same channel have 0 distance among themselves, but distance from any data point to a centroid will just be the euclidean distance, since centroids have no channel. Thus, since kmeans iterates on distance from points to centroids, it would just behave like a normal kmeans not taking channel into account. Let me know if I'm misunderstanding kmeans though! Feb 4 '16 at 21:14

The simplest thing that comes to mind is cluster the users for each channel then compare the channels by their cluster parameters. If you use a non-probabilistic model such as k-means, you could compare the cluster parameters directly. With a large number of clusters this would not be a good idea, for somewhat technical reasons. If you use a probabilistic model you would look at something like the KLD.