Язык статьи - русский
Ссылка для цитирования: Забашта А.С., Фильченков А.А. Построения наборов данных для задачи классификации по их характеристическому описанию // Научно-технический вестник информационных технологий, механики и оптики. 2017. Т. 17.
№ 3. С. 498–505. doi: 10.17586/2226-1494-2017-17-3-498-505
Аннотация
Предмет исследования.Представлен метод построения экземпляров данных для задачи классификации по заданному характеристическому описанию в виде вектора мета-признаков для задачи классификации. Предложен наивный метод для решения той же задачи, используемый в качестве референтного. Исследовано характеристическое пространство экземпляров задач классификации, а также методы обхода этого пространства. Метод. Предложенный метод основывается на генетическом алгоритме, где в качестве минимизируемой целевой функции используется расстояние в характеристическом пространстве от вектора описания построенного экземпляра задачи классификации до заданного. Для работы генетического алгоритма разработаны операторы кроссовера и мутации экземпляров задачи классификации, использующие операции добавления или удаления признаков и объектов. Основные результаты. Для проверки предложенного метода выбраны нетривиальные двухмерные мета-признаковые пространства, построенные над статистическими, информационно-теоретическими и структурными характеристиками экземпляров задачи. Для сравнения использован наивный метод, не учитывающий характеристического описания. При равных ограничениях в 6500 рассмотренных экземпляров задачи классификации предложенный в работе метод обошел наивный на всех тестах. Погрешность уменьшена в среднем в 30 раз. Практическая значимость. Предложенный метод построения наборов данных для задачи классификации по их характеристическому описанию позволяет получить неизвестные экземпляры задачи классификации, которые нужны для оценки работы классификаторов в определенных областях мета-признакового пространства при построении систем автоматического выбора алгоритмов.
Ключевые слова: машинное обучение, мета-обучение, задача классификации, эволюционные вычисления, генетический алгоритм
Благодарности. Работа выполнена при финансовой поддержке Правительства Российской Федерации, грант 074-U01 и РФФИ, грант 16-37-60115-мол_а_дк
Список литературы
1. Cook S.A., Mitchell D.G. Finding hard instances of the satisfiability problem // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1997. V. 35. P. 1–17. doi:
10.1090/dimacs/035/01
2. Horie S., Watanabe O. Hard instance generation for SAT // Lecture Notes in Computer Science. 1997. V. 1350. P. 22–31. doi:
10.1007/3-540-63890-3_4
3. Selman B., Mitchell D.G., Levesque H.J. Generating hard satisfiability problems // Artificial Intelligence. 1996. V. 81. N 1-2. P. 17–29.
4. Xu K., Boussemart F., Hemery F., Lecoutre C. Random constraint satisfaction: easy generation of hard (satisfiable) instances // Artificial Intelligence. 2007. V. 171. N 8. P. 514–534. doi:
10.1016/j.artint.2007.04.001
5. van Hemert J.I. Evolving combinatorial problem instances that are difficult to solve // Evolutionary Computation. 2006. V. 14. N 4. P. 433–462. doi:
10.1162/evco.2006.14.4.433
6. Ajtai M. Generating hard instances of the short basis problem // Lecture Notes in Computer Science. 1999. V. 1644. P. 1–9.
7. Буздалов М.В. Генерация тестов для олимпиадных задач по программированию с использованием генетических алгоритмов // Научно-технический вестник информационных технологий, механики и оптики. 2011. № 2(72). С. 72–77.
8. Буздалов М.В. Генерация тестов для олимпиадных задач по теории графов с использованием эволюционных стратегий // Научно-технический вестник информационных технологий, механики и оптики. 2011. № 6(76). С. 123–127.
9. Smith-Miles K., Tan T.T. Measuring algorithm footprints in instance space // IEEE Congress on Evolutionary Computation. Brisbane, Australia, 2012. P. 3446–3453. doi:
10.1109/CEC.2012.6252992
10. Asahiro Y., Iwama K., Miyano E. Random generation of test instances with controlled attributes // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1996. V. 26. P. 377–393. doi:
10.1090/dimacs/026/18
11. Smith-Miles K., Wreford B., Lopes L., Insani N. Predicting metaheuristic performance on graph coloring problems using data mining // Studies in Computational Intelligence. 2013. V. 434. P. 417–432. doi:
10.1007/978-3-642-30671-6-16
12. Smith-Miles K., Baatar D., Wreford B., Lewis R. Towards objective measures of algorithm performance across instance space // Computers and Operations Research. 2014. V. 45. P. 12–24. doi:
10.1016/j.cor.2013.11.015
13. Giraud-Carrier C. Metalearning – a tutorial // Tutorial at 7th Int. Conf. on Machine Learning and Applications, ICMLA. San Diego, California, 2008. P. 11–13.
14. Brazdil P., Giraud-Carrier C., Soares C., Vilalta R. Metalearning. Applications to Data Mining. Springer, 2009. 176 p. doi:
10.1007/978-3-540-73263-1
15. Wolpert D.H., Macready W.G. No free lunch theorems for optimization // IEEE Transactions on Evolutionary Computation. 1997. V. 1. N 1. P. 67–82. doi:
10.1109/4235.585893
16. Wolpert D.H. The supervised learning no-free-lunch theorems // Soft Computing and Industry. 2002. P. 25–42.doi:
10.1007/978-1-4471-0123-9_3
17. Воронцов К.В. Математические методы обучения по прецедентам (теория обучения машин) [Электронный ресурс]. Режим доступа: http://docplayer.ru/2064-K-v-voroncov-http-www-ccas-ru-voron-voron-ccas-ru.html, свободный. Яз. рус. (дата обращения 24.03.2017). 140 c.
18. Николенко С.И., Тулупьев А.Л. Самообучающиеся системы. М.: МЦНМО, 2009. 287 с.
19. Jin Y., Branke J. Evolutionary optimization in uncertain environments – a survey // IEEE Transactions on Evolutionary Computation. 2005. V. 9. N3.P. 303–317.doi:
10.1109/TEVC.2005.846356
20. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. Москва, Физматлит, 2006. 319 с.
21. Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by simulated annealing // Science. 1983. V. 220. N 4598. P. 671–680.
22. Скобцов Ю.А. Основы эволюционных вычислений. Донецк: ДонНТУ, 2008.326 с.
23. Vanschoren J., van Rijn J.N., Bischl B., Torgo L. OpenML: networked science in machine learning // ACM SIGKDD Explorations Newsletter. 2014. V. 15(2). P. 49–60. doi:
10.1145/2641190.2641198
24. Filchenkov A., Pendryak A. Datasets meta-feature description for recommending feature selection algorithm // Proc. Artificial Intelligence and Natural Language and Information Extraction, Social Media and Web Search FRUCT. St. Petersburg, Russia, 2015. P. 11–18. doi:
10.1109/AINL-ISMW-FRUCT.2015.7382962
25. Indyk P., Motwani R. Approximate nearest neighbors: towards removing the curse of dimensionality // Proc. 13th Annual ACM Symposium on Theory of Computing. Dallas, USA, 1998. P. 604–613.