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.