Новый метод оптимального сокращения множества признаков
Ключевые слова:
многомерные данные, классификация, минимизация размера множества атрибутов, задача о минимальном покрытии, принцип групповых резолюцийАннотация
Рассматривается задача нахождения минимального по размеру множества атрибутов, используемых для распределения многомерных объектов по классам, например на основе деревьев решений. Задача имеет важное значение при разработке высокопроизводительных и точных классифицирующих систем. Приведен краткий сравнительный обзор известных методов. Задача сформулирована как отыскание минимального (взвешенного) покрытия на различающей 0,1-матрице, которая служит для описания возможности атрибутов разделять пары объектов из разных классов. Приведено описание способа построения различающей матрицы. Сформулированы и решены на основе общего разрешающего принципа групповых резолюций следующие варианты задачи: отыскание минимального по размеру множества атрибутов на заданном входном наборе данных; отыскание минимального по размеру множества атрибутов с минимальным суммарным весом атрибутов (в качестве весов атрибутов можно использовать величины, определяемые на основе известных алгоритмов, например на основе метода RELIEF); нахождение оптимального взвешенного нечеткого покрытия для случая, когда элементы различающей матрицы принимают значения в диапазоне [0,1]; определение статистически оптимального покрытия различающей матрицы (например, для входных наборов данных больших размеров). Статистически оптимальный алгоритм позволяет ограничить время решения полиномом от размеров задачи и плотности единичных элементов в различающей матрице и при этом обеспечить близкую к единице вероятность отыскания точного решения.
Таким образом, предлагается общий подход к определению минимального по размеру множества атрибутов, учитывающий различные особенности в постановке задачи, что отличает данный подход от известных. Изложение содержит многочисленные иллюстрации с целью придать ему максимальную ясность. Ряд теоретических положений, приводимых в статье, основывается на ранее опубликованных результатах. В заключительной части представлены результаты экспериментов, а также сведения о сокращении размерности задачи о покрытии для больших массивов данных. Отмечаются некоторые перспективные направления изложенного подхода, включая работу с неполными и качественными данными, интегрировании управляющей модели в систему классификации данных.
Литература
2. Khun K, Johnson K. Feature engineering and selection. A practical approach for predictive models. CRC Press. 2019. 310 p.
3. Bachu V., Anuradha J. A review of feature selection and its methods. Cybernetics and information technologies (Bulgary). 2019. vol. 19. no. 1. pp. 322.
4. Hameed S., Petinrin O., Hashi A., Saeed F. Filter-wrapper combination and embedded feature selection for gene expression data. International journal of advances in soft computing and its applications. 2018. vol. 10. no. 1. pp. 91–105.
5. Sanchez-Pinto L.N., Venable L.R., Fahrenbach J., Churpek M. Comparison of variable selection methods for clinical predictive modeling. International journal of medical informatics. 2018. vol. 116. pp. 1017.
6. Li J. et al. Feature selection: A data perspective. ACM Computer surveys. 2017. vol. 50. no. 6. pp. 94:294:46.
7. Guyon I. et al. Feature Extraction. Foundations and Applicationsbg. Springer. 2006. 762 p.
8. Urbanowicz R.J. et al. Relief-based feature selection: Introduction and review. Journal of biomedical informatics. 2018. vol. 8. no. 5. pp. 189203.
9. Liu Y., Singleton A., Arribas-Bel D. A principal component analysis (PCA)-based framework for automated variable selection in geodemographic classification. GEO-Spatial Information Science. 2019. vol. 22. no. 4. pp. 251264.
10. Khanna R., Awad M. Efficient learning machines: Theories, Concepts, and Applications for engineers and system designers. Apress. 2015. 247p.
11. Mao Y., Yang Y. A wrapper feature subset selection based on randomized search and multilayer structure. BioMed Research International. 2019. vol. 2019. pp. 19.
12. Hui K.H. et al. An improved wrapper-based feature selection method for machinery fault diagnosis. PloS ONE. 2017. vol. 12. no. 12. pp. 110.
13. Lal T.N., Chapelle O., Weston J., Eliseeff A. Embedded methods. Series in Fuzzy and soft computing. 2006. vol. 207. pp. 137165.
14. Sudrajat R., Irianingsih I., Krisnawan D. Analysis of data mining classification by comparison of C4.5 and ID algorithms. IOP Conference Series: Materials and Engineering. 2017. vol. 166. pp.012031.
15. Krishna M. et al. Predicting student performance using classification and regression trees. International Journal of Innovative Technology and Exploring Engineering. 2020. vol. 9. no. 3. pp. 33493356.
16. Suneetha N., Hari Ch., Sunilkumar V. Modified Gini index classification: a case statudy on hart disease dataset. International journal on computer science and engineering. 2010. vol. 2. no. 6. pp. 19591965.
17. German O.V., Naidenko V.G. [Statistically optimal algorithm for the minimum-size covering problem] Jekonomika i matematicheskie metody Economics and mathematical methods. Moscow. 1993. Issue 29. vol. 4. pp. 662667. (In Russ.).
18. German O.V. [The generalized statistically optimal method to find minimum weighted covering set for 0,1-matrix] Jekonomika i matematicheskie metody Economics and mathematical methods. oscow. 1994. Issue 30. vol. 4. pp. 139150. (In Russ.).
19. German O.V. Jekspertnye sistemy [Expert systems]. Minsk. Belorusskij gos. universitet informatiki i radioelektroniki. 2008. 91 p. (In Russ.).
20. Kamenev G.K., Kamenev I.G. Primenenie metodov mnogomernogo analiza dlja izuchenija sociologicheskih sovokupnostej [Applications of the methods of multidimension analysis for learning social aggregates]. Proc. of the department of mathematical modeling of economic systems. Computer Center «Informatics and Control» of the Russian Academy of Sciences. 2017. 91p. (In Russ.).
21. Bhatia N. et al. Survey of Nearest Neighbor Techniques. International Journal of Computer Science and Information Security. 2010. vol. 8. no. 2. pp. 302304.
22. Sun L., Chen G., Xiong H., Guo C. Cluster analysis in data-driven management and decisions. Journal of Management Science and Engineering. 2017. vol. 2. no. 4. pp. 227251.
Опубликован
Как цитировать
Раздел
Copyright (c) aleh_herman
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).