Data Mining and Knowledge Discovery Handbook, 2 Edition part 70. Knowledge Discovery demonstrates intelligent computing at its best, and is the most desirable and interesting end-product of Information Technology. To be able to discover and to extract knowledge from data is a task that many researchers and practitioners are endeavoring to accomplish. There is a lot of hidden knowledge waiting to be discovered – this is the challenge created by today’s abundance of data. Data Mining and Knowledge Discovery Handbook, 2nd Edition organizes the most current concepts, theories, standards, methodologies, trends, challenges and applications of data mining (DM) and knowledge discovery. | 670 Grigorios Tsoumakas loannis Katakis and loannis Vlahavas Ex. Label 1a A1 1b A4 2a A3 2b A4 3 A1 4a A2 4b A3 4c A4 a Ex. Label Weight 1a A1 1b A4 2a A3 2b A4 3 A1 4a A2 4b A3 4c A4 b Ex. Label 1 A4 2 A4 3 A1 4 A4 c Ex. Label 1 A1 2 A3 3 A1 4 A2 d Ex. Label 1 A1 2 A4 3 A1 4 A3 e Ex. Label 3 A1 f Fig. . Transformation of the data set in Figure using a copy b copy-weight c select-max d select-min e select-random one of the possible and f ignore Label powerset LP is a simple but effective problem transformation method that works as follows It considers each unique set of labels that exists in a multi-label training set as one of the classes of a new single-label classification task. Figure shows the result of transforming the data set of Figure using LP. Ex. Label 1 A1 4 2 A3 4 3 A1 4 A2 3 4 Fig. . Transformed data set using the label powerset method Given a new instance the single-label classifier of LP outputs the most probable class which is actually a set of labels. If this classifier can output a probability distribution over all classes then LP can also rank the labels following the approach in Read 2008 . Table shows an example of a probability distribution that could be produced by LP trained on the data of Figure given a new instance x with unknown label set. To obtain a label ranking we calculate for each label the sum of the probabilities of the classes that contain it. This way LP can solve the complete MLR task. Table . Example of obtaining a ranking from LP c p clx A1 A2 A3 A4 A1 4 1 0 0 1 A3 4 0 0 1 1 A1 1 0 0 0 A2 3 4 0 1 1 1 clx Aj The computational complexity of LP with respect to q depends on the complexity of the base classifier with respect to the number of classes which is equal to the number of distinct label sets in the training set. This number is upper bounded by min m 2q and despite that it 34 Mining Multi-label Data 671 .
