ПОПУЛЯЦИОННЫЙ АЛГОРИТМ ПОСТРОЕНИЯ ДЕРЕВА РЕШЕНИЙ МЕТОДОМ КРИСТАЛЛИЗАЦИИ РОССЫПИ АЛЬТЕРНАТИВ

  • Б. K. Лебедев Южный федеральный университет
  • О. Б. Лебедев Южный федеральный университет
  • В.Б. Лебедев Московский государственный технический университет имени Н.Э. Баумана
Ключевые слова: Классификация, дерево решений, оптимизация, популяционный алгоритм, адаптивное поведение, метод кристаллизации россыпи альтернатив

Аннотация

В ряде случаев возникает необходимость установления соответствия между заяв-
ленным и фактическим значением категориальной переменной на основе совокупности
признаков объекта. В этом случае возникает потребность в классификаторе с оптималь-
ной последовательностью рассматриваемых атрибутов с заданным значением целевой
функции. Значением целевой переменной может быть: да, нет, номер сорта, номер класса
и т.д. В работе решается задача построения классификационной модели в виде оптималь-
ной последовательность рассматриваемых атрибутов и их значений, входящих в состав
маршрута от корневой вершины к концевой вершине с заданным значением целевой пере-
менной. Если требуется классификатор, включающий возможность альтернативных от-
ветов, то вначале строятся независимо друг от друга оптимальные маршруты для каж-
дого значения целевой переменной, а затем эти маршруты объединяются («склеиваются»)
в единое бинарное дерево решений. В алгоритме построения классификатора на основе
метода кристаллизации россыпи альтернатив, каждое решение Qk интерпретируется в
виде в ориентированного маршрута Mk на бинарном дереве решений. Назовем порядковый
номер элемента в ориентированном маршруте Mk позицией siS={si|i=1,2,…,nA}. Элемен-
том маршрута Mk является пара (xi,ui-), где xi соответствует Ai. ui- в маршруте Mk явля-
ется ребром, выходящим из xi и соответствует выбранному вместе с Ai значению Ai. Вто-
рой индекс элемента ui- определится после выбора Ai, помещенного в соседнюю с sj позицию
sj+1. Работа алгоритма построения дерева решений базируется на использовании коллек-
тивной эволюционной памяти, под которой подразумевается информация, отражающая
историю поиска решения. Алгоритм учитывает тенденции к использованию альтернатив
из наилучших найденных решений. Особенностями являются наличие непрямого обмена
информацией – стигмержи. Совокупность данных об альтернативах и их оценках состав-
ляет россыпь альтернатив. Рассмотрены ключевые моменты анализа альтернатив в про-
цессе эволюционной коллективной адаптации. Экспериментальные исследования показали,
что разработанный алгоритм находит решения, не уступающие по качеству, а иногда и
превосходящие своих аналогов в среднем на 3–4 %. Временная сложность алгоритма, полу-
ченная экспериментальным путем, лежит в пределах О(n2)-О(n3).

Литература

1. Witten Ian H., Frank Eibe, Hall Mark A. Data Mining: Practical Machine Learning Tools and
Techniques. 3rd Edition. Morgan Kaufmann, 2011, 178 p.
2. Zhuravlev Yu.I., Ryazanov V.V., Sen'ko O.V. «Raspoznavanie». Matematicheskie metody.
Programmnaya sistema. Prakticheskie primeneniya [Recognition". Mathematical methods.
Software system. Practical applications]. Moscow: Fazis, 2006, 122 p.
3. Berikov V.S., Lbov G.S. Sovremennye tendentsii v klasternom analize [Modern trends in cluster
analysis], Vserossiyskiy konkursnyy otbor obzorno-analiticheskikh statey po prioritetnomu
napravleniyu «Informatsionno-telekommunikatsionnye sistemy» [All-Russian competitive selection
of review and analytical articles in the priority direction "Information and telecommunication
systems], 2008, 126 p.
4. Barsegyan A.A., Kupriyanov M.S., Stepanenko V.V., Kholod I.I. Metody i modeli analiza
dannykh: OLAP i Data Mining [Methods and models for data analysis: OLAP and Data Mining].
Saint Petersburg: BKhV-Peterburg, 2004, 93 p.
5. Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye
prirodoy: ucheb. posobie [Modern search engine optimization algorithms. Algorithms inspired
by nature: textbook]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2014, 448 p.
6. Wang X. Hybrid nature-inspired computation method for optimization: Doctoral Dissertation.
Helsinki University of Technology, TKK Dissertations, Espoo 2009, 161 p.
7. Lebedev B.K., Lebedev O.B., Lebedev V.B. Gibridizatsiya roevogo intellekta i geneticheskoy
evolyutsii na primere razmeshcheniya [Hybridization of swarm intelligence and genetic evolution
on the example of placement], Programmnye produkty, sistemy i algoritmy [Software
products, systems and algorithms], 2017, No.4.
8. Lebedev B.K., Lebedev O.B. Gibridnyy bioinspirirovannyy algoritm resheniya zadachi
simvol'noy regressii [Hybrid bioinspired algorithm for solving the problem of symbolic regression],
Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015,
No. 6 (167), pp. 28-41.
9. Kureychik V.M., Lebedev B.K., Lebedev O.B. Poiskovaya adaptatsiya: teoriya i praktika
[Search engine adaptation: theory and practice]. Moscow: Fizmatlit, 2006, 288 p.
10. Lebedev B.K., Lebedev V.B. Optimizatsiya metodom kristallizatsii rossypi al'ternativ [Optimization
by the method of сrystallization of alternatives field], Izvestiya YuFU. Tekhnicheskie
nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 11-17.
11. Lebedev B.K., Lebedev O.B., Lebedeva E.M. Raspredelenie resursov na osnove gibridnykh
modeley roevogo intellekta [Resource allocation based on hybrid models of swarm intelligence],
Nauchno-tekhnicheskiy vestnik informatsionnykh tekhnologiy, mekhaniki i optiki [Scientific
and technical bulletin of information technologies, mechanics and optics], 2017, Vol.
17, No. 6, pp. 1063-1073.
12. Kureychik V.V., Kureychik Vl.Vl. Arkhitektura gibridnogo poiska pri proektirovanii [Architecture
of hybrid search in design], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering
Sciences], 2012, No. 7 (132), pp. 22-27.
13. Lebedev B.K., Lebedev O.B., Lebedeva E.O. Reshenie zadachi simvol'noy regressii metodami
geneticheskogo poiska [The solution of the problem of symbolic regression by methods of genetic
search], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences],
2015, No. 2 (163), pp. 212-225.
14. Kennedy J., Eberhart R.C. Particle swarm optimization, In Proceedings of IEEE International
Conference on Neural Networks, 1995, pp. 1942-1948.
15. Clerc M. Particle Swarm Optimization. ISTE, London, UK, 2006, 133 р.
16. Lebedev B.K., Lebedev V.B. Evolyutsionnaya protsedura obucheniya pri raspoznavanii obrazov
[Evolutionary training procedure for pattern recognition], Izvestiya TRTU [Izvestiya TSURE],
2004, No. 8 (43), pp. 83-88.
17. Lebedev B.K., Lebedev O.B., Lebedeva E.O. Razbienie na klassy metodom al'ternativnoy
kollektivnoy adaptatsii [Division into classes by the method of alternative collective adaptation],
Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2016,
No. 7 (180), pp. 89-101.
18. Cong J., Romesis M., Xie M. Optimality, Scalability and Stability Study of Partitioning and
Placement Algorithms, Proc. of the International Symposium on Physical Design. Monterey,
CA, 2003, pp. 88-94.
19. Zakharov D.O, Karpenko A.P. Issledovanie effektivnosti populyatsionnogo algoritma ligi
chempionov dlya zadachi global'noy optimizatsii [Research of the efficiency of the population algorithm
of the Champions League for the global optimization problem], Matematika i matematicheskoe
modelirovanie [Mathematics and Mathematical Modeling], 2020, No. 2, pp. 25-45.
20. Karpenko A.P. Metody povysheniya effektivnosti populyatsionnykh algoritmov global'noy
optimizatsii [Methods for increasing the efficiency of population algorithms for global optimization],
Mater. V mezhregional'noy nauchno-prakticheskoy konferentsii [Proceedings of the V
interregional scientific and practical conference]. Sevastopol': Izd-vo: Sevastopol'skiy
gosudarstvennyy universitet, 2019, pp. 87-88.
21. Kuchuganov V.N., Kuchuganov A.V., Kaksimov D.R. Algoritm klasterizatsii mnozhestva
detaley po chertezham [Algorithm for clustering a set of parts according to drawings],
Programmirovanie [Programming]. Moscow: Izd-vo: Rossiyskaya akademiya nauk, 2020,
pp. 29-38.
Опубликован
2020-11-22
Выпуск
Раздел
РАЗДЕЛ I. ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ И НЕЧЕТКИЕ СИСТЕМЫ