Научная электронная библиотека ULRICH'S Periodicals Directory

Сибирский государственный университет
науки и технологий имени академика М.Ф. Решетнева

Сибирский аэрокосмический журнал
ISSN 2712-8970 (Print) ISSN 2782-5760 (on-line)

Сведения об образовательной организации

UDK 519.6 Doi: 10.31772/2587-6066-2020-21-3-347-354
МОДЕЛИ И АЛГОРИТМЫ АВТОМАТИЧЕСКОЙ ГРУППИРОВКИ ОБЪЕКТОВ НА ОСНОВЕ МОДЕЛИ K-СРЕДНИХ
Г. Ш. Шкаберина, Л. А. Казаковцев, Ж. Ли
Сибирский государственный университет науки и технологий имени академика М. Ф. Решетнева; Российская Федерация, 660037, г. Красноярск, просп. им. газ. «Красноярский рабочий», 31
Работа посвящена исследованию и разработке новых алгоритмов автоматической группировки объектов, которые позволяют повысить точность и стабильность результата решения практических задач, например, таких как задача выделения однородных партий промышленной продукции. В статье исследуется применение алгоритма k-средних с Евклидовым, Манхэттенским, Махаланобиса мерами расстояния для задачи автоматической группировки объектов с большим количеством параметров. Представлена новая модель для решения задач автоматической группировки промышленной продукции на основе модели k-средних с мерой расстояния Махаланобиса. Данная модель использует процедуру обучения путем вычисления усредненной оценки ковариационной матрицы для обучающей выборки (выборка с предварительно размеченными данными). Предложен новый алгоритм автоматической группировки объектов, основанный на оптимизационной модели k-средних с мерой расстояния Махаланобиса и средневзвешенной ковариационной матрицей, рассчитанной по обучающей выборке. Алгоритм позволяет снизить долю ошибок (повысить индекс Рэнда) при выявлении однородных производственных партий продукции по результатам тестовых испытаний. Представлен новый подход к разработке генетических алгоритмов для задачи k-средних с применением единой жадной агломеративной эвристической процедуры в качестве оператора скрещивания и оператора мутации. Вычислительный эксперимент показал, что новая процедура мутации является быстрой и эффективной по сравнению с исходной мутацией генетического алгоритма, показана высокая скорость сходимости целевой функции. Применение данного алгоритма позволяет статистически значимо повысить точность результата (улучшить достигаемое значение целевой функции в рамках выбранной математической модели решения задачи автоматической группировки), а также его стабильность за фиксированное время по сравнению с известными алгоритмами автоматической группировки. Результаты показывают, что идея включения нового оператора мутации в генетическом алгоритме значительно улучшает результаты простейшего генетического алгоритма для задачи k-средних.
Ключевые слова: автоматическая группировка, k-средних, расстояние Махаланобиса, генетический алгоритм.
References

1. Алгоритмическое обеспечение поддержки принятия решений по отбору изделий микроэлектроники для космического приборостроения / В. И. Орлов, Л.А. Казаковцев, И.С. Масич и др. ; Сиб. гос. аэрокосмич. ун-т. Красноярск, 2017. 225 с.
2. Казаковцев Л. А., Антамошкин А. Н. Метод жадных эвристик для задач размещения // Вестник СибГАУ. 2015. Т. 16, № 2. С. 317–325.
3. MacQueen J. Some methods for classification and analysis of multivariate observations // Proc. Fifth Berkeley Symp. Math. Stat. Probab. 1967. Vol. 1. P. 281–297.
4. Hosage C. M., Goodchild M. F. Discrete Space Location-Allocation Solutions from Genetic Algorithms // Annals of Operations Research. 1986. Vol 6. P. 35–46. http://doi.org/10.1007/bf02027381
5. Bozkaya B., Zhang J., Erkut E. A Genetic Algorithm for the p-Median Problem // Drezner Z., Hamacher H. (eds,), Facality Location. Applications and Theory, Springer, Berlin, 2002.
6. Alp O., Erkut E., Drezner Z. An Efficient Genetic Algorithm for the p-Median Problem // Annals of Operations Research. 2003. Vol. 122. P. 21–42. http://doi.org/10.1023/A:1026130003508
7. Maulik U., Bandyopadhyay S. Genetic Algorithm-Based Clustering Technique // Pattern Recognition. 2000. Vol. 33, No. 9. P. 1455–1465. https://doi.org/10.1016/S0031-3203(99)00137-5
8. William M. Rand. Objective Criteria for the Evaluation of Clustering Methods // Journal of the American Statistical Association. 1971. Vol. 66, No. 336. P. 846–850.
9. De Maesschalck R., Jouan-Rimbaud D., Massart D. L. The Mahalanobis distance // Chem Intell Lab Syst. 2000. Vol 50, No. 1. P 1–18. doi: 10.1016/S0169-7439(99)00047-7
10. McLachlan G J. Mahalanobis Distance // Resonance. 1999. Vol 4, No. 20. doi: 10.1007/BF02834632.
11. Distance metric learning with application to clustering with side-information / E. P. Xing, A. Y. Ng, M. I. Jordan and et al. // Advances in Neural Information Processing Systems. 2003. Vol. 15. P. 505–512.
12. Орлов В. И., Федосов В. В. Набор данных электрорадиоизделий. 2016 [Электронный ресурс]. URL: http://levk.info/data1526.zip.
13. Применение алгоритмов кластеризации с особыми мерами расстояния для задачи автоматической группировки электрорадиоизделий / В. И. Орлов, Г. Ш. Шкаберина, И. П. Рожнов и др. // Системы управления и информационные технологии. 2019. № 3 (77). С. 42–46.
14. Hansen P., Mladenovic N. J-means: a new local search heuristic for minimum sum of squares clustering // Pattern recognition. 2001. Vol. 34, No. 2. P. 405–413.
15. Kazakovtsev L. A., Antamoshkin A. N. Genetic Algorithm with Fast Greedy Heuristic for Clustering and Location Problems // Informatica. 2014. Vol. 38, No. 3. P. 229–240.


Шкаберина Гузель Шарипжановна – доцент кафедры информационно-управляющих систем; Сибирский государственный университет науки и технологий имени академика М. Ф. Решетнева. E-mail: z_guzel@mail.ru.
Казаковцев Лев Александрович – доктор технических наук, доцент, заведующий кафедрой системного анализа и исследования операций; Сибирский государственный университет науки и технологий имени академика М. Ф. Решетнева. E-mail: levk@bk.ru.
Ли Жуя – аспирант кафедры системного анализа и исследования операций; Сибирский государственный университет науки и технологий имени академика М. Ф. Решетнева. E-mail: 646601833@qq.com.


  МОДЕЛИ И АЛГОРИТМЫ АВТОМАТИЧЕСКОЙ ГРУППИРОВКИ ОБЪЕКТОВ НА ОСНОВЕ МОДЕЛИ K-СРЕДНИХ