New Method for Optimal Feature Set Reduction

Аннотация

Рассматривается задача нахождения минимального по размеру множества атрибутов, используемых для распределения многомерных объектов по классам, например на основе деревьев решений. Задача имеет важное значение при разработке высокопроизводительных и точных классифицирующих систем. Приведен краткий сравнительный обзор известных методов. Задача сформулирована как отыскание минимального (взвешенного) покрытия на различающей 0,1-матрице, которая служит для описания возможности атрибутов разделять пары объектов из разных классов. Приведено описание способа построения различающей матрицы. Сформулированы и решены на основе общего разрешающего принципа групповых резолюций следующие варианты задачи: отыскание минимального по размеру множества атрибутов на заданном входном наборе данных; отыскание минимального по размеру множества атрибутов с минимальным суммарным весом атрибутов (в качестве весов атрибутов можно использовать величины, определяемые на основе известных алгоритмов, например на основе метода RELIEF); нахождение оптимального взвешенного нечеткого покрытия для случая, когда элементы различающей матрицы принимают значения в диапазоне [0,1]; определение статистически оптимального покрытия различающей матрицы (например, для входных наборов данных больших размеров). Статистически оптимальный алгоритм позволяет ограничить время решения полиномом от размеров задачи и плотности единичных элементов в различающей матрице и при этом обеспечить близкую к единице вероятность отыскания точного решения.

Таким образом, предлагается общий подход к определению минимального по размеру множества атрибутов, учитывающий различные особенности в постановке задачи, что отличает данный подход от известных. Изложение содержит многочисленные иллюстрации с целью придать ему максимальную ясность. Ряд теоретических положений, приводимых в статье, основывается на ранее опубликованных результатах. В заключительной части представлены результаты экспериментов, а также сведения о сокращении размерности задачи о покрытии для больших массивов данных. Отмечаются некоторые перспективные направления изложенного подхода, включая работу с неполными и качественными данными, интегрировании управляющей модели в систему классификации данных.

Abstract

A problem of searching a minimum-size feature set to use in distribution of multidimensional objects in classes, for instance with the help of classifying trees, is considered. It has an important value in developing high speed and accuracy classifying systems. A short comparative review of existing approaches is given. Formally, the problem is formulated as finding a minimum-size (minimum weighted sum) covering set of discriminating 0,1-matrix, which is used to represent capabilities of the features to distinguish between each pair of objects belonging to different classes. There is given a way to build a discriminating 0,1-matrix. On the basis of the common solving principle, called the group resolution principle, the following problems are formulated and solved: finding an exact minimum-size feature set; finding a feature set with minimum total weight among all the minimum-size feature sets (the feature weights may be defined by the known methods, e.g. the RELIEF method and its modifications); finding an optimal feature set with respect to fuzzy data and discriminating matrix elements belonging to diapason [0,1]; finding statistically optimal solution especially in the case of big data. Statistically optimal algorithm makes it possible to restrict computational time by a polynomial of the problem sizes and density of units in discriminating matrix and provides a probability of finding an exact solution close to 1.

Thus, the paper suggests a common approach to finding a minimum-size feature set with peculiarities in problem formulation, which differs it from the known approaches. The paper contains a lot of illustrations for clarification aims. Some theoretical statements given in the paper are based on the previously published works.

In the concluding part, the results of the experiments are presented, as well as the information on dimensionality reduction for the coverage problem for big datasets. Some promising directions of the outlined approach are noted, including working with incomplete and categorical data, integrating the control model into the data classification system.