Научный журнал

Фундаментальные исследования

ISSN 1812-7339

"Перечень" ВАК

ИФ РИНЦ = 1,674

• Авторы
• Резюме
• Файлы
• Ключевые слова
• Литература

Гусева А.И. 1 Киреев В.С. 1 Кузнецов И.А. 1 Бочкарёв П.В. 1

---

1 Национальный исследовательский ядерный университет «МИФИ» (Московский инженерно-физический институт), Москва

Настоящая статья посвящена решению задачи классификации научных направлений. Источником данных является большой объем библиографической информации, содержащийся в международных научных системах и базах данных. Рассматривается задача многомерной классификации в пространстве большого количества признаков. Проводится сравнительный анализ таких алгоритмов классификации, как построение наивного байесовского классификатора, дерево решений и лес деревьев решений. Рассматривается подход усиления алгоритмов, связанный с введением комитетов голосующих алгоритмов. Предлагается алгоритм, представляющий собой модификацию голосования по большинству. Серия вычислительных экспериментов показала, что применение предлагаемого алгоритма повышает точность полученных решений до 90 %. Для дальнейшего усовершенствования алгоритма, по нашему мнению, могут использоваться два направления: обучение комитета алгоритмов и введение весов атрибутов в пространстве признаков, описывающие классифицируемые объекты.

Статья в формате PDF

783 KB

научное направление

жизненный цикл научного направления

научный результат

многомерная классификация

комитет голосующих алгоритмов

1. Лычагин М.В., Мкртчян Г.М., Лычагин А.М., По пов И.Ю. Новое исследование инноваций в 2006–2013 годах: библиометрический анализ на основе EconLit // Вестник Новосибирского государственного университета. Серия: Социально-экономические науки. – 2014. – Т. 14, Вып. 3. – С. 150–162.

2. Мазуров В.Д. Метод комитетов в задачах оптимизации и классификации. – М.: Наука, 1990.

3. Несветайлов Г.А. Научные кадры: возраст и творчество // Социологические исследования. – 1998. – № 9.– С. 115–119.

4. Нессонова М.Н. Метод рейтингового голосования комитета алгоритмов в задачах классификации с учителем // Запорожский медицинский журнал. – 2013. – № 1 (76). – С. 101–102

5. Никулин В.Н., Палешева С.А., Зубарева Д.С. Об однородных ансамблях при использовании метода бустинга в приложении к классификации несбалансированных данных // Вестник пермского университета. Серия: Экономика. – 2012. – № 4. – С. 8–14

6. Попов А.К., Трофимов А.Г. Применение комитетов классификаторов в задаче классификации многомерных динамических данных // Новый университет. – 2012. – № 4(10). – С. 34–37.

7. Boosting the margin: a new explanation for the effectiveness of voting methods / R.E. Schapire, Y. Freund, W.S. Lee, P. Bartlett // Annals of Statistics. – 1998. – Vol. 26, № 5. – P. 1651–1686.

8. Breiman, L. 2000. Some infinity theory for predictor ensembles. Technical Report 579, Statistics Dept. UCB.

9. Grove A., Schuurmans D. (1998). Boosting in the limit: Maximizing the margin of learned ensembles // In Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI-98).

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

Научное (научно-техническое) направление характеризуется совокупностью научных работ, объединенных общностью объекта и методов исследования, общностью тем и их взаимосвязанностью. К научным работам или, более точно, научным результатам (НР) мы относим тезисы докладов, статьи, монографии и учебники, препринты, защищенные диссертации и результаты интеллектуальной деятельности (патенты на изобретения, промышленные образцы, полезные модели и селекционные достижения, свидетельства государственной регистрации на программы для ЭВМ и базы данных).

Стандартная модель жизненного цикла научного направления предполагает четыре этапа своего развития: зарождение, рост, зрелость и насыщение с последующим распадом [3]. Этапы зарождения и роста составляют интенсивную фазу, а этапы зрелости и насыщения – экстенсивную. Во время первой, интенсивной фазы, число ежегодно получаемых принципиально новых научных результатов быстро увеличивается, на экстенсивной – падает. По длительности интенсивная стадия познания заметно короче, чем экстенсивная. На разных этапах жизненного цикла преобладают разные виды научных результатов. Так, на первом этапе развития научного направления преобладают фундаментальные исследования, на второй – прикладные исследования и разработки. В соответствии с этим изменяется основной вид результатов научной деятельности в сторону увеличения патентов и свидетельств.

Объем накопленной в мире научной информации (тезисы, статьи, монографии, патенты и т.д.) оценивается в петабайтах (большие данные, Big Data) и требует специальных методов обработки. Современные мировые базы данных имеют свои собственные классификаторы научных направлений. Использование имеющихся классификаторов также сопряжено с рядом трудностей. Во-первых, эти классификаторы отличаются друг от друга, во-вторых, динамика изменения направления прикладных исследований чрезвычайно высока, и классификаторы не успевают изменяться так быстро, как нужно. В-третьих, появление нового научного направления не всегда бывает замечено и отражено в классификаторах. Например, в [1] приведены результаты исследования списка предметных кодов JEL в электронной библиографии экономической литературы EconLit. По данным 2006–2013 годов выявлены 62 новых направления экономических исследований на пересечении микрообластей классификатора JEL.

Таким образом, решение задачи многомерной классификации на больших объемах научных данных является весьма актуальным.

Состояние вопроса

Постановка задачи классификации выглядит следующим образом.

Пусть есть множество объектов X, заданных в многомерном пространстве признаков, и конечный набор классов {Ci ... Cn}. Известно, что каждый объект x ? X относится к некоторому классу Cj ? {C1, C2, ... Cn}. Таким образом, необходимо построить правило (алгоритм) отображения каждого объекта из Х к своему классу T:X ? {C1, C2, ... Cn} с наибольшей точностью.

Учитывая, что реальное пространство признаков очень велико и разрежено, а самих объектов чрезвычайно много, то подгонка параметров алгоритма (его обучение) проводится по некоторому конечному подмножеству XL ? X, называемому обучающей выборкой.

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

Наивный байесовский классификатор (NA?VE BAYES, NB). Наивный байесовский классификатор объединяет модель с правилом решения. Одно общее правило должно выбрать наиболее вероятную гипотезу; оно известно как апостериорное правило принятия решения (MAP). Соответствующий классификатор – это функция {classify}, определённая следующим образом [2]:

где f1, f2, …, fn – переменные (характеристики объекта); С – класс.

То есть вероятность принадлежности объекта к конкретному классу рассчитывается как произведение вероятностей независимых событий о равенстве переменных конкретным значениям для класса.

К достоинствам алгоритма относятся такие свойства, как устойчивость к изолированным точкам шума; обработка как количественных, так и дискретных данных, быстрое вычисление и эффективное использование памяти, нечувствительность к нерелевантным переменным. При работе алгоритма возникают проблемы, если условная вероятность равна нулю. Ограничением использования алгоритма является предположение, что переменные независимы.

Дерево решений (DT). Дерево принятия является одним из самых простых, но в то же время прозрачных и эффективных алгоритмов для выполнения классификации. Дерево решений представляет правила в иерархическом и последовательном виде, где каждому атрибуту соответствует свой узел, на основе которого дается решение [2].

К достоинствам данного алгоритма относится то, что он не требует предобработки данных, обладает высокой скоростью работы, высокой точностью и прозрачностью. Недостатком является то, что слишком сложные конструкции могут не отображать реальной картины, ввиду чего точность может оказаться ниже, чем у более простой конструкции

Лес деревьев решений (Random Forest, RF). Само по себе дерево решений не обеспечивает достаточной точности для этой задачи, но отличается быстротой построения. Алгоритм RF обучает k решающих деревьев на параметрах, случайно выбранных для каждого дерева, после чего на каждом из тестов проводится голосование среди обученного ансамбля. В основе построения этого алгоритма лежит идея о том, что если суммировать данные от большого количества различных слабых алгоритмов, сведя их в единый ответ, то результат, скорее всего, будет лучше, чем у одного мощного алгоритма [2].

Подобные алгоритмы обладают способностью эффективно обрабатывать данные с большим числом признаков и классов, мало чувствительны к масштабированию (и вообще к любым монотонным преобразованиям) значений признаков, одинаково хорошо обрабатываются как непрерывные, так и дискретные признаки, обладают внутренней оценкой способности модели к обобщению (тест out-of-bag), возможностью параллельной реализации и масштабируемостью. Существуют методы построения деревьев по данным с пропущенными значениями признаков и оценивания значимости отдельных признаков в модели. В качестве недостатков следует отметить, что алгоритм склонен к переобучению на некоторых задачах, особенно на зашумленных задачах, и требует большого объема памяти для представления полученных результатов. В этом случае требуется O(Nk) памяти для хранения модели, где k – число деревьев.

Совершенствование алгоритма классификации (Adaptive Boosting, AdaBoost).

Увеличение точности простых классификаторов может быть проведено путём комбинирования примитивных слабых классификаторов в один сильный алгоритм AdaBoost (от английских слов адаптивность и усиление) [7]. Под силой классификатора в данном случае подразумевается эффективность (качество) решения задачи классификации. Улучшение (Boosting) – это набор методов для порождения последовательности классификаторов, в которой каждый последующий классификатор пытается исправить ошибки предыдущих. Улучшение применяется к некоторому алгоритму классификации, называемому базовым классификатором (BaseLearner). Этот классификатор часто называют слабым классификатором. На каждом шаге алгоритм изменяет веса записей обучающей выборки, увеличивая веса неверно расклассифицированных записей.

Усиление происходит путем объединения их в комитет. Суть алгоритма заключается в комбинировании слабых классификаторов в один финальный, более мощный [7, 9]. Известно, что в качестве слабых классификаторов могут выступать практически любые, а использование комитетов почти всегда приводит к усилению результата [5]. В процессе обучения финального классификатора акцент делится на эталоны, которые распознаются хуже, т.е. выбирается классификатор, который лучше идентифицирует объекты, неверно распознанные предыдущим классификатором, в этом и заключается адаптивность алгоритма, в процессе обучения он подстраивается под наиболее сложные объекты.

Часто используются следующие способы построения комитетов алгоритмов [2, 4, 8].

1. Голосование по большинству (простое голосование), при котором комитет классификаторов относит объект к тому классу, к которому его отнесли большинство входящих в него алгоритмов.

2. Голосование по старшинству (машина покрывающих множеств). Этот метод предполагает последовательную одноклассовую классификацию. То есть первый алгоритм комитета отвечает за отнесение объекта к классу 1. Если он отказывается от классификации, то объект передается второму алгоритму, который может его отнести к классу 2. Если этого не произошло, объект передается к третьему классификатору и т.д., пока один из алгоритмов не при мет решения.

3. Взвешенное голосование из смеси экспертов. В этом случае голос каждого из классификаторов Ti, входящих в комитет Т, имеет свой вес ?i, зависящий от ошибки данного алгоритма на обучающем множестве:

В работе [6] приводятся данные, что усложнение правил построения комитетов, от взвешенного голосования до нейронных сетей, не дает значимого эффекта. Наилучший результат, повышение точности на 7–10 %, дает обучение комитета.

К достоинствам алгоритма AdaBoost следует отнести простоту реализации, возможность идентифицировать объекты, являющиеся шумовыми выбросами, хорошую обобщающую способность. В реальных задачах (не всегда, но часто) удаётся строить композиции, превосходящие по качеству базовые алгоритмы. Обобщающая способность может улучшаться (в некоторых задачах) по мере увеличения числа базовых алгоритмов. Время построения композиции практически полностью определяется временем обучения базовых алгоритмов.