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.
 A: 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.


*

*Dimensionality Reduction by Learning an Invariant Mapping (DrLIM) seems to work very well on some data sets.

*Neighborhood components analysis is a very nice linear algorithm, and nonlinear versions have been developed as well.

*There's a whole literature that deals with this issue from the perspective of "learning a kernel".  I don't know much about it, but this paper is highly cited.
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.
A: 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:


*

*Fisher's linear discriminant analysis

*Large Margin Nearest Neighbors
