Перевод названия: Detection of patterns in data for recognition of objects as a conditional pseudo-boolean OPTIMIZATION problem
Тип публикации: статья из журнала
Год издания: 2015
Ключевые слова: classification, logical patterns, Pseudo-boolean optimization, классификация, логические закономерности, псевдобулевая оптимизация
Аннотация: Создание и использование логических алгоритмов классификации основывается на выявлении в исходных данных закономерностей, из набора которых формируется решающая функция. Поиск закономерностей можно рассматривать как задачу комбинаторной оптимизации. Для получения более эффективного решения выбор алгоритма оптимизации следует произвПоказать полностьюодить исходя из характерных свойств, присущих рассматриваемой оптимизационной задаче. Рассматриваются некоторые свойства задач оптимизации, решаемых в ходе поиска логических закономерностей в данных. Рассматривается задача распознавания объектов, описываемых бинарными признаками и разделенных на два класса. Закономерности являются элементарными блоками для построения логических алгоритмов распознавания. Задачу нахождения максимальной закономерности можно записать в виде задачи условной псевдобулевой оптимизации. Проводится исследование свойств оптимизационной модели, описывающей поиск логических закономерностей в данных. Результаты исследований показывают, что в пространстве поиска имеется множество постоянства целевой функции, которое затрудняет работу алгоритмов оптимизации, начинающих поиск из допустимой точки и ведущих его по соседним точкам, так как вычисление целевой функции в системе окрестностей, состоящей из соседних точек, не дает информации о наилучшем направлении поиска. При решении практических задач больших размерностей это множество постоянства может быть таким, что ему принадлежит большая часть точек допустимой области. Рассматриваются возможности улучшения алгоритмов поиска закономерностей. Проводится экспериментальное исследование на практических задачах распознавания. Результаты экспериментов показывают, что использование информации о близости объектов выборки к закономерности позволяет преодолеть трудности, связанные с характерными особенностями решаемой задачи оптимизации и проявляющиеся в наличии множеств постоянства, и находить лучшие закономерности в данных для их использования в решении задач распознавания. Creating and using logical classification algorithms are based on revealing patterns in the input data, and a decision function is formed from a set of these patterns. Search for patterns can be viewed as a combinatorial optimization problem. To produce the most effective solutions, the choice of the optimization algorithm should be made on the basis of the characteristic properties inherent in the considered optimization problem. In this paper we consider some properties of optimization problems that are solved in the course of finding logical patterns in the data. We consider the recognition problem for objects described by binary attributes and divided into two classes. Regularities are the elementary blocks for construction logical recognition algorithms. The problem of finding the maximum patterns can be written in the form of a constrained pseudo-Boolean optimization problem. We study the properties of the optimization model, which describes the search for logical patterns in the data. Research results show that in the search space there is a set of constancy of the objective function. This hampers performance of the optimization algorithms, which begin the search from a feasible point and leading it to neighboring points, since the calculation of the objective function in the system of neighborhoods consisting of neighboring points, gives no information on best search direction. While solving practical problems of large dimension, this set of constancy may own most of the points of the feasible region. We consider the possibilities of improving algorithms of search for patterns. Experimental investigations were conducted on the real-world recognition problems. Experimental results show that the use of information about the proximity of the sample objects to patterns can overcome the difficulties associated with the characteristic features of optimization problem solved and manifested in the presence of constancy sets. And this allows finding the best patterns in the data to use them in solving the recognition problems.
Журнал: Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева
Выпуск журнала: Т. 16, № 1
Номера страниц: 16-21
ISSN журнала: 18169724
Место издания: Красноярск
Издатель: Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева