Модификация алгоритма случайного леса для классификации нестационарных потоковых данных

Алексей Витальевич Жуков; Денис Николаевич Сидоров

doi:10.14529/mmp160408

Авторы

Алексей Витальевич Жуков Институт математики, экономики и информатики; Иркутский национальный исследовательский технческий университет
Денис Николаевич Сидоров Институт систем энергетики им. Л.А. Мелентьева РАН;Институт математики, экономики и информатики; Иркутский национальный исследовательский технческий университет

DOI:

https://doi.org/10.14529/mmp160408

Ключевые слова:

классификация, смещение концепта, случайный лес, решающие деревья, композиции.

Аннотация

Предложен метод классификации нестационарных потоковых данных. К таким данным относятся характеристики поведения сложных систем, процессы, обладающие высокой степенью стохастичности, такие как скорость ветра. В данной работе предложена эффективная модификация алгоритма случайного леса, позволяющая повысить точность классификации состояния путем взвешивания ответов отдельных классификаторов композиции. Опираясь на метод Accuracy Weighted Ensemble (AWE), взвешивание производится в соответствии с оценкой ошибки каждого классификатора на новых данных. Такая оценка производится с использованием метода k ближайших соседей и внутренней структуры случайного леса. В качестве стратегии обновления композиции используется замена классификаторов с низкой точностью на новых данных. Приводятся результаты тестирования предложенного метода и сравнение с другими современными методами.

Биографии авторов

Алексей Витальевич Жуков, Институт математики, экономики и информатики; Иркутский национальный исследовательский технческий университет

аспирант кафедры "Информационные технологии"

Денис Николаевич Сидоров, Институт систем энергетики им. Л.А. Мелентьева РАН;Институт математики, экономики и информатики; Иркутский национальный исследовательский технческий университет

доктор физико-математических наук, ведущий научный сотрудник

Библиографические ссылки

Tomin N., Zhukov A., Sidorov D., Kurbatsky V., Panasetsky D., Spiryaev V. Random Forest Based Model for Preventing Large-Scale Emergencies in Power Systems. International Journal of Artificial Intelligence, 2015, vol. 13, no. 1, pp. 221-228.

Breiman L. Random Forests. Machine Learning, 2001, vol. 45, no. 1, pp. 5-32. DOI: 10.1023/A:1010933404324

Breiman L. Bagging Predictors. Machine Learning. 1996, vol. 24, no. 2, pp. 123-140. DOI: 10.1023/A:1018054314350.

Ho Tin Kam. The Random Subspace Method for Constructing Decision Forests. Pattern Analysis and Machine Intelligence, IEEE Transactions, 1998, vol. 20, no. 8, pp. 832-844. DOI: 10.1109/34.709601

Zliobaite Indre. Learning under Concept Drift: an Overview. arXiv preprint arXiv:1010.4784. 2010.

Haixun Wang, Wei Fan, Yu P.S., Han J. Mining Concept-Drifting Data Streams Using Ensemble Classifiers. Proceedings of SIGKDD, August 24-27, 2003, Washington, DC, 2003, pp. 226-235.

Gama J. Knowledge Discovery from Data Streams. Singapore, CRC Press Publ., 2010. DOI: 10.1201/EBK1439826119

Kuncheva L. Classifier Ensembles for Changing Environment. Multiple Classifier Systems, 2004 5th Intl. Workshop, Springer-Verlag, 2004, pp. 1-15. DOI: 10.1007/978-3-540-25966-4_1

Haixun Wang, Wei Fan, Yu P.S., Han J. Mining Concept-Drifting Data Streams Using Ensemble Classifiers. Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2003, pp. 226-235. DOI: 10.1145/956750.956778

Aiping Wang, Guowei Wan, Zhiquan Cheng, Sikun Li. An Incremental Extremely Random Forest Classifier for Online Learning and Tracking. Image Processing (ICIP), 2009 16th IEEE International Conference. IEEE, 2009, pp. 1449-1452.

Geurts P., Ernst D., Wehenkel L. Extremely Randomized Trees. Machine Learning, 2006, vol. 63, no. 1, pp. 3-42. DOI: 10.1007/s10994-006-6226-1

Santner J., Saffari A., Leistneret C. et al. On-Line Random Forests. Computer Vision Workshops (ICCV Workshops), 2009 IEEE 12th International Conference. IEEE, 2009, pp. 1393-1400.

Oza N.C. Online Bagging and Boosting. Systems, Man and Cybernetics, 2005 IEEE International Conference. IEEE, vol. 3, 2005, pp. 2340-2345. DOI: 10.1109/icsmc.2005.1571498

Abdulsalam H., Skillicorn D.B., Martin P. Classification Using Streaming Random Forests. Knowledge and Data Engineering, IEEE Transactions. 2011, vol. 23, no. 1, pp. 22-36.

Lakshminarayanan B., Roy D.M., Teh Yee Whye. Mondrian Forests: Efficient Online Random Forests. Advances in Neural Information Processing Systems, 2014, pp. 3140-3148.

Kelly M.G., Hand D.J., Adams N.M. The Impact of Changing Populations on Classifier Performance. Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 1999, pp. 367-371. DOI: 10.1145/312129.312285

Zhukov A., Kurbatsky V., Tomin N. et al. Random Forest Based Model for Emergency State Monitoring in Power Systems. Mathematical Method for Pattern Recognition: Book of Abstract of the 17th All-Russian Conference with Interneational Participation. Svetlogorsk, TORUS PRESS, 2015, pp. 274.

Scornet E. Random Forests and Kernel Methods. IEEE Transactions on Information Theory, 2016, vol. 62, no. 3, pp. 1485-1500. DOI: 10.1109/TIT.2016.2514489

Blake C.L., Merz C.J. UCI Repository of Machine Learning Databases. 1998.

Brzezinski D. Mining Data Streams with Concept Drift. Diss. MS Thesis. Dept. of Computing Science and Management. Poznan University of Technology, 2010.

Brzezinski D., Stefanowski J. Reacting to Different Types of Concept Drift: The Accuracy Updated Ensemble Algorithm. Neural Networks and Learning Systems, IEEE Transactions, 2014, vol. 25, no. 1, pp. 81-94.