НИКИФОРОВ
Владимир Олегович
д.т.н., профессор
doi: 10.17586/2226-1494-2017-17-4-664-669
УДК 004.023:004.852:004.832.23
ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ВЫБОРА ПРИЗНАКОВ НА ОСНОВЕ ОЧЕРЕДИ С ПРИОРИТЕТОМ
Читать статью полностью
Ссылка для цитирования: Сметанников И.Б. Параллельный алгоритм выбора признаков на основе очереди с приоритетом // Научно-технический вестник информационных технологий, механики и оптики. 2017. Т. 17. № 4. С. 664–669. doi: 10.17586/2226-1494-2017-17-4-664-669
Аннотация
Предмет исследования.Исследованы методы и алгоритмы выбора признаков в задачах классификации, применяемые в машинном обучении. Предложен метод ускоренного выбора признаков, сводящийся к задаче оптимизации линейной комбинации (ансамбля) других алгоритмов выбора признаков. Метод. Суть предлагаемого алгоритма состоит в выборе признаков на основе очереди с приоритетом. Предложенное решение является развитием алгоритма выбора признаков measure linear form (MeLiF). Предложенный вариант алгоритма реализует очередь с приоритетом для эффективного распараллеливания вычислений и, по сути, является многопоточной версией алгоритма MeLiF. Основные результаты. Оценивание качества алгоритма и сравнение его с исходным алгоритмом проведено по критериям времени, затрачиваемого на оптимизацию, и итогового качества классификации. Исследования выполнены на 36 наборах данных ДНК-микрочипов из различных открытых баз данных.Показано, что при одинаковом качестве классификации время, затрачиваемое предложенным алгоритмом, сокращается от 4,2 до 22 раз на 24-ядерном процессоре в 50 потоках. Практическая значимость. Предложенный алгоритм может быть использован для выбора значимых признаков в наборах данных с большим числом признаков. Алгоритм может быть применен для предобработки данных в задачах машинного обучения и использоваться в широком спектре задач классификации на достаточно больших наборах данных.
Благодарности. Работа выполнена при финансовой поддержке Правительства Российской Федерации, грант 074-U01 и РФФИ, грант 16-37-60115-мол_а_дк.
Список литературы
1. Fan J., Samworth R., Wu Y. Ultrahigh dimensional feature selection: beyond the linear model // Journal of Machine Learning Research. 2009. V. 10. P. 2013–2038.
2. Bolon-Canedo V., Sanchez-Marono N., Alonso-Betanzos A. et.al. A review of microarray datasets and applied feature selection methods // Information Sciences. 2014. V. 282. P. 111–135. doi: 10.1016/j.ins.2014.05.042
3. Saeys Y., Inza I., Larranaga P. A review of feature selection techniques in bioinformatics // Bioinformatics. 2007. V. 23. N 19. P. 2507–2517. doi: 10.1093/bioinformatics/btm344
4. Jiliang T., Salem A., Huan L. Feature Selection for Classification: A Review. CRC Press, 2014. 37 p.
5. Dietterich G. Ensemble methods in machine learning // Lecture Notes in Computer Science. 2000. V. 1857. P. 1–15.
6. Bolon-Canedo V., Sanchez-Marono N., Alonso-Betanzos A. An ensemble of filters and classifiers for microarray data classification // Pattern Recognition. 2012. V. 45. N 1. P. 531–539. doi: 10.1016/j.patcog.2011.06.006
7. DeConde R.P., Hawley S., Falcon S. et.al. Combining results of microarray experiments: a rank aggregation approach // Statistical Applications in Genetics and Molecular Biology. 2006. V. 5. P. i-23.
8. Dwork C. et.al. Rank aggregation methods for the web // Proc. 10th Int. Conf. on World Wide Web. 2001. P. 613–622.
9. Filchenkov A. et. al. PCA-based algorithm for constructing ensembles of feature ranking filters // Proc. ESANN. Bruges, Belgium, 2015. P. 201–206.
10. Smetannikov I., Filchenkov A. MeLiF: filter ensemble learning algorithm for gene selection // Advanced Science Letters. 2016. V. 22. N 10. P. 2982–2986. doi: 10.1166/asl.2016.7078
11. Isaev I., Smetannikov I. MeLiF+: Optimization of filter ensemble algorithm with parallel computing // IFIP Advances in Information and Communication Technology. 2016. V. 475. P. 341–347. doi: 10.1007/978-3-319-44944-9_29