How do I approach a multi-class classification problem involving a 2-part taxonomy?

Question

I am trying to solve a classification problem and am unsure of the strategy to use. I am using scikit learn and am more interested in whether I have the correct approach rather than the implementation.

I have

• set T, where each item in the set is a string
• two sets L1 and L2, that are non-overlapping controlled lists of labels
• each item in T can map to one and only one item on L1 and one and only one item in L2
• L1 and L2 are related as part of a 2 part taxonomy with which I am tagging items in T

e.g.

• T = {'queen elizabeth's barnet', 'queen elizabeth's london', 'odeon leicester sq', 'odeon london', 'pizza express 189', 'piz expss 2', 'honda civic 25-jul'} L1 = {building, car, boat} L2 = {school, cinema, restaurant, honda, ford, cruise-boat}

• I have trained my classifier on previous data to tag ''queen elizabeth's barnet' with L1/building, L2/school and 'odeon london' with L1/building and L2/cinema

At the moment I am approaching the problem as a multi-class classification, where I am assigning one and only one label from L1 and one label from L2 to each item in T and treating the 2 classification tasks independently i.e. I have trained a classifier to predict L1 given T and separately predict L2 given T.

I am thinking whether this method is the best approach as it doesnt make use of the dependency/constraint between L1 and L2 - and am considering predicting L1 for a given T and then using the predicted L1 in the feature vector to predict L2 (or vice versa). Unsure as to whether this is the best approach given there is error in the prediction.

Any ideas/experience on how best to approach this problem?

Thanks in advance for any help!

Answer 1

I solved a similar problem a few months ago. What you are describing actually is a clear example of a hierarchical classification problem.

In these kind of problems, what you usually want to do is to focus on building a single classifier for L1 (call it your first-level classifier); and then N classifiers for L2 (where N is the number of possible classes in L1) - these are your second-level classifiers.

You already know how to train the first-level classifier. For the second-level ones, the only gotcha is to remember that your training sets must be composed of only the examples of the particular subclass each classifier is modelling (e.g for the second-level model for car, you'll only use examples tagged as honda or ford, but examples tagged as cinema would not be part of the training set of this model).

Finally, when using your models, you just classify each test example with the first-level classifier. This gives you your L1 output, but also determines which second-level model to use for L2.

There are other ways of representing these kind of problems, of course. But in those where you have such a clear taxonomy:

• each item in T can map to one and only one item on L1 and one and only one item in L2*)

Splitting the problem into 2 or more levels is the best way to go.