Abstract-Network operators are continuously confronted with online events, such as online messages, blog updates, etc. Due to the huge volume of these events and the fast changes of the topics, it is critical to manage them promptly and effectively. There have been many softwares and algorithms developed to conduct automatic classification over these stream data. Conventional approaches focus on single-label scenarios, where each event can only be tagged with one label. However, in many stream data, each event can be tagged with more than one labels. Effective stream classification systems should be able to consider the unique properties of multi-label stream data, such as large data volumes, label correlations and concept drifts. To address these challenges, in this paper, we propose an efficient and effective method for multi-label stream classification based on an ensemble of fading random trees. The proposed model can efficiently process high-speed multi-label stream data with concept drifts. Empirical studies on real-world tasks demonstrate that our method can maintain a high accuracy in multi-label stream classification, while providing a very efficient solution to the task. Index Terms-Data stream, data mining, multi-label classifica tion, random tree Due to the recent advances in computer networks and data storage, network operators are continuously confronted with large amount of online events which are produced at a very high speed. Examples of such online events include text streams of online news, emails.twitter posts, credit card transactions, stock market data, network traffic records, etc. These data are called stream data. It is important to manage them promptly and effectively. For example, in email systems, researchers want to be able to automatically classify vast amount of incoming emails into different categories, like spams, personal emails, business emails, important emails, etc.; In bank systems, people are interested in monitoring the credit card transactions and classify all the incoming transac tions in real-time. Although there have been many softwares and algorithms developed to conduct automatic classification over these online events, it remains a challenging task due to following factors: (1) vast amount of data arrive at high speed [9] . The whole data can seldom fit into the memory, while they need to be analyzed in real time. Therefore an efficient system for online events should be able to process data in one-pass and use only limited memory to deal with 95 Philip S. Yu Chicago, IL, USA Email: psyu@cs.uic.edu the potentially infinite data streams; (2) usually, the concepts within the events can evolve or drift over time [34] . For example, the behavior of the online users may change over time depending on various factors. Effective systems for online events should be able to adapt to the concept changes and revise itself accordingly. Motivated by these challenges, stream classification has received considerable attention in the last decade. In the literature, stream classification problem has been extensively studied [9] [3] , which assume, explicitly or implicitly, that each online event can only be assigned with one class label. However, in many real-world applications, each online event can be associated with more than one label. For example, an online news article about 'Steve Jobs resigns as Apple CEO' can be annotated with labels like IT, legend, company, etc. The analysis and management of the online documents can be greatly improved if one can train a model to automatically tag each document with multiple labels in real time. This setting is also known as multi-label classification which aims at designing models to classify each instance into multiple categories. It has been shown useful in many real world applications such as text categorization [24] , [2S] and bioinformatics [10] . Formally, the multi-label stream classification problem cor responds to training a model to associate each instance in a high-speed data stream with a label set in the space of all possible label sets, i.e. the power set of all labels. The label set space can be extremely large even with a small number of possible labels. Multi-label classification is particularly challenging in data stream scenarios. The reason is that, conventional multi-label classification approaches work under the batch settings which assume all the data are able to fit into the memory and the models can be trained with mUltiple passes through the entire dataset. But in stream data, the data continuously flood in with very high speed, which make it impossible to be stored in the memory. Stream classification algorithms should only take one-pass through the data stream to train the model, and the model should be able to responds to the stream data in real time. 97S-1-93696S-36-7
Moreover, Kong and Yu REF propose also an ensemble-based method for multi-label stream classification.
An ensemble-based approach to fast classification of multi-label data streams
7th International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom)
7th International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom)
Computer Science