# How to find weights for a dissimiliarity measure

I want to learn (deduce) attribute weights for my dissimilarity measure that I can use for clustering.

I have some examples $(a_i,b_i)$ of pairs of objects that are "similar" (should be in the same cluster), as well as some examples $(c_i,d_i)$ of pairs of objects that are "not similar" (should not be in the same cluster). Each object has a number of attributes: if you like, we can think of each object as a $d$-dimensional vector of features, where each feature is a non-negative integer. Are there techniques to use such examples of similar/dissimilar objects to estimate from them optimal feature weights for a dissimilarity measure?

If it it helps, in my application, it would probably be reasonable to focus on learning a dissimilarity measure that's a weighted L2 norm:

$$d(x,y) = \sum_j \alpha_j (x[j] - y[j])^2.$$

where the weights $\alpha_j$ are not known and should be learned. (Or, some kind of weighted cosine similarity measure might be reasonable too.) Are there good algorithms to learn the weights $\alpha_j$ for such a measure, given the examples? Or are there any other methods for learning a similarity measure / dissimilarity measure that I should consider?

The number of dimensions is unfortunately very large (thousands or higher; it's derived from bag-of-words features). However, I do have many tens of thousands of examples. I then have hundreds of thousands of objects that I want to cluster, so it's important to generalize from the examples to learn a good dissimilarity metric.

I gather that this falls into the rubric of semi-supervised clustering, and it sounds like it might be of the "similarity-adapting" vein, but I haven't been able to find clear descriptions of algorithms to use for this purpose.

• Very interesting problem. If I get your problem right, you are given a mainly empty matrix with its elements encoding pairwise similarity or dissimilarity. Some elements are filled in but most are missing. I would try to fill that matrix first (e.g. using low-rank assumption for example). – Vladislavs Dovgalecs Apr 25 '15 at 6:15
• @xeon, that would be one approach, but it ignores the features. My hypothesis is that some features are highly relevant and some features are not relevant, and that looking at the difference in the relevant features gives a reasonable dissimilarity metric -- but how do we find that metric? Just trying to complete the matrix as you suggest ignores this structure and thus doesn't take full advantage of the data we have. – D.W. Apr 25 '15 at 6:41
• What is your final goal? It is not just to learn the distance metric, right? You want to categorize the data points, aren't you? – Vladislavs Dovgalecs Apr 25 '15 at 7:05
• There are things that I think you haven't elucidated very clear. Do the whole set of example pairs form a complete binary (1=similar;0=dissimilar) matrix or some cells information is missing? Is the matrix "noncontradictory" - that is, the example objects partition into nonoverlapping classes? Also, note that no learning method can (or should be used to) advice you the type of measure (such as be it L2 or L1 norm, for example) because such choice is theoretical (it depends of kind of attributes, conceptualization of feature space, method of clustering you are going to use then). – ttnphns Apr 25 '15 at 8:40
• This is too broad to be reasonably answered here. There is a large amount of literature dedicated both to feature weighting, selection and to learning of distance functions. I think I've seen even a conference on similarity learning or so! – Has QUIT--Anony-Mousse Apr 25 '15 at 9:07

This is a big issue in some areas of machine learning. I'm not as familiar with it as I'd like, but I think these should get you started.

Given that your data is so high-dimensional (and probably sparse?), you might not need anything too nonlinear. Maybe neighborhood components analysis is the best place to start? It's closest to the idea of a weighted $L_2$ norm, like you suggested in your question.

• Yes, the data is sparse. This looks extremely helpful, thank you. Is there a variant of neighborhood components analysis where the matrix $Q$ is restricted to be diagonal (equivalently $A$ is diagonal)? (It looks like this might correspond to the class of dissimilarity measures mentioned in my question above.) – D.W. Apr 25 '15 at 6:56
• I don't see why you couldn't include that restriction. I'm not sure if the resulting model has a name, though. – David J. Harris Apr 25 '15 at 17:51

Putting an $a_i$ weight on a feature in your similarity measure is equivalent so scaling your data set by $1/w_i$.

In other words, you are asking about data preprocessing and scaling. This is too broad to be answered well in a single question. Look for:

• feature selection
• feature weighting
• normalization
• dimensionality reduction
• other projection techniques
• other distance functions
• "learning to rank"

There is a massive amount of literature and even conference tracks dedicated to this. Some methods to get you started: