I currently have a representation of an object as a graph, and I have some similarity measure on that graph. I currently determine the class of a query object by trying to match its graph representation against every instance in the training set, and I assign the query's class as the class of the best graph matching.

Some classes have many similar features that would be good matching nodes, but certain nodes distinguish them from specific classes. For example, nodes 1 and 3 might match well in both classes class A and class B, but a match of node 2 distinguishes the object as belonging to class A. In that case, I would want node 2 to have a higher weight, as it is more important to discriminating between the two classes. At the same time, nodes 1 and 2 might match well for classes A and C, but a matching of node 3 distinguishes the object as class A, so node 3 would be more important and should be weighted as such.

This kind of discrimination between classes seems difficult to achieve. What is the best machine learning approach to perform this kind of weighted discrimination?

edit Adding details. Although two nodes in a graph may match, they are almost never identical. Imagine the graph being different parts of an image, and you have some similarity measure to define how similar two image parts are. Since two images are almost never identical, they will pretty well never be exact matches.

  • $\begingroup$ I still try to imagine how your "data" can be transformed into a format I am used to work with ;). But there are a lot of open questions for me. Can you provide a link to an example algorithm which transforms an image to a graph ? Which similarity measure to do you use ? I am especially interested to see whether/how it matches components between two graphs or it processes the graph as whole. $\endgroup$ – steffen Jan 26 '12 at 15:25
  • $\begingroup$ I additionally suggest to move (!= double post) this question to stackoverflow. Although I am seriously not happy with such a move (Crossvalidated is dedicated for ML !), one cannot ignore the fact that more ML people are hanging around on stackoverflow (as far as I see). $\endgroup$ – steffen Jan 27 '12 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.