9
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ 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). $\endgroup$
    – Vladislavs Dovgalecs
    Apr 25, 2015 at 6:15
  • $\begingroup$ @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. $\endgroup$
    – D.W.
    Apr 25, 2015 at 6:41
  • $\begingroup$ 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? $\endgroup$
    – Vladislavs Dovgalecs
    Apr 25, 2015 at 7:05
  • 1
    $\begingroup$ 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). $\endgroup$
    – ttnphns
    Apr 25, 2015 at 8:40
  • $\begingroup$ 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! $\endgroup$
    – Has QUIT--Anony-Mousse
    Apr 25, 2015 at 9:07

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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.) $\endgroup$
    – D.W.
    Apr 25, 2015 at 6:56
  • $\begingroup$ I don't see why you couldn't include that restriction. I'm not sure if the resulting model has a name, though. $\endgroup$
    – David J. Harris
    Apr 25, 2015 at 17:51
1
$\begingroup$

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:

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.