Тип публикации: статья из журнала
Год издания: 2020
Идентификатор DOI: 10.31772/2587-6066-2020-21-3-347-354
Ключевые слова: automatic grouping, k-means, Mahalanobis distance, genetic algorithm, автоматическая группировка, k-средних, расстояние Махаланобиса, генетический алгоритм
Аннотация: The paper is devoted to the study and development of new algorithms for automatic grouping of objects. The algorithms can improve the accuracy and stability of the result of solving practical problems, such as the problems of identifying homogeneous batches of industrial products. The paper examines the application of the k-means aПоказать полностьюlgorithm with the Euclidean, Manhattan, Mahalanobis distance measures for the problem of automatic grouping of objects with a large number of parameters. A new model is presented for solving problems of automatic grouping of industrial products based on the k-means model with the Mahalanobis distance measure. The model uses a training procedure by calculating the averaged estimate of the covariance matrix for the training sample (sample with pre-labeled data). A new algorithm for automatic grouping of objects based on an optimization model of k-means with the Mahalanobis distance measure and a weighted average covariance matrix calculated from a training sample is proposed. The algorithm allows reducing the proportion of errors (increasing the Rand index) when identifying homogeneous production batches of products based on the results of tests. A new approach to the development of genetic algorithms for the k-means problem with the use of a single greedy agglomerative heuristic procedure as the crossover operator and the mutation operator is presented. The computational experiment has shown that the new mutation procedure is fast and efficient in comparison with the original mutation of the genetic algorithm. The high rate of convergence of the objective function is shown. The use of this algorithm allows a statistically significant increase both in the accuracy of the result (improving the achieved value of the objective function within the framework of the chosen mathematical model for solving the problem of automatic grouping), and in its stability, in a fixed time, in comparison with the known algorithms of automatic grouping. The results show that the idea of including a new mutation operator in the genetic algorithm significantly improves the results of the simplest genetic algorithm for the k-means problem. Работа посвящена исследованию и разработке новых алгоритмов автоматической группировки объектов, которые позволяют повысить точность и стабильность результата решения практических задач, например, таких как задача выделения однородных партий промышленной продукции. В статье исследуется применение алгоритма k-средних с Евклидовым, Манхэттенским, Махаланобиса мерами расстояния для задачи автоматической группировки объектов с большим количеством параметров. Представлена новая модель для решения задач автоматической группировки промышленной продукции на основе модели k-средних с мерой расстояния Махаланобиса. Данная модель использует процедуру обучения путем вычисления усредненной оценки ковариационной матрицы для обучающей выборки (выборка с предварительно размеченными данными). Предложен новый алгоритм автоматической группировки объектов, основанный на оптимизационной модели k-средних с мерой расстояния Махаланобиса и средневзвешенной ковариационной матрицей, рассчитанной по обучающей выборке. Алгоритм позволяет снизить долю ошибок (повысить индекс Рэнда) при выявлении однородных производственных партий продукции по результатам тестовых испытаний. Представлен новый подход к разработке генетических алгоритмов для задачи k-средних с применением единой жадной агломеративной эвристической процедуры в качестве оператора скрещивания и оператора мутации. Вычислительный эксперимент показал, что новая процедура мутации является быстрой и эффективной по сравнению с исходной мутацией генетического алгоритма, показана высокая скорость сходимости целевой функции. Применение данного алгоритма позволяет статистически значимо повысить точность результата (улучшить достигаемое значение целевой функции в рамках выбранной математической модели решения задачи автоматической группировки), а также его стабильность за фиксированное время по сравнению с известными алгоритмами автоматической группировки. Результаты показывают, что идея включения нового оператора мутации в генетическом алгоритме значительно улучшает результаты простейшего генетического алгоритма для задачи k-средних.
Журнал: Сибирский журнал науки и технологий
Выпуск журнала: Т. 21, № 3
Номера страниц: 347-354
ISSN журнала: 25876066
Место издания: Красноярск
Издатель: Сибирский государственный университет науки и технологий им. акад. М.Ф. Решетнева