Исследование методов классификации

Размещено на http://www.allbest.ru/

1. Введение

1.1 Характеристика исследовательской проблемы

сэмплинг генерация синтетический

Для успешного решения задач автоматической обработки естественного языка (англ. natural language processing) - направления в вычислительной лингвистике (англ. computational linguistics), в рамках которого изучаются проблемы синтеза естественных языков и их компьютерного анализа - очень важно иметь возможность правильно классифицировать текстовые данные в соответствии с проблемой, стоящей перед человеком. Примерами подобных задач являются фильтрация спама в электронных почтовых ящиках (определение, принадлежит ли поступившее владельцу письмо к классу «спам» или нет) и анализ тональности текста (определение тональности информации, содержащейся в сообщении в целом или относительно какой-либо сущности, упомянутой в нём).

В качестве методов, используемых для установления принадлежности объекта к тому или иному классу, чаще всего используют машинное обучение с учителем (англ. supervised learning). Основной идеей этого подхода является индуктивный вывод функции на основе размеченных данных для обучения [20]. Это означает, что успешность применения алгоритма машинного обучения с учителем во многом зависит от той выборки объектов, на основе которых «обучается» программа. Большинство подобных алгоритмов требуют от исследователя включения сопоставимого количества примеров для каждого из классов, однако зачастую сделать сбалансированные наборы данных не представляется возможным в связи с рядом факторов. Ключевыми из них являются специфика целевой области (балансировка данных может понизить показатель их репрезентативности - «меры возможности восстановить, воспроизвести представление о целом по его части или мера возможности распространить представление о части на включающее эту часть целое» [42, с. 104]) и разная цена ошибок первого и второго рода при классификации.

Вследствие этого возникает проблема обучения модели на несбалансированных данных (англ. skewed data; таковыми являются данные, в распределении которых наблюдается асимметрия, а показатели моды и среднего значения не равны): в соответствии с базовыми предположениями, заключенными в большинство алгоритмов, целью обучения является максимизация доли правильных решений по отношению ко всем принятым решениям, а данные для обучения и генеральная совокупность подчиняются одному и тому же распределению [7]. Однако учёт данных предположений и несбалансированности выборки приводит к тому, что модель оказывается неспособна классифицировать данные согласно алгоритму лучше, чем тривиальная модель, полностью игнорирующая менее представленный класс и маркирующая все объекты для классификации как принадлежащие к доминирующему классу.

Другой вариант развития событий - это создание слишком сложной модели, включающей большое множество правил, которое при этом будет охватывать малое количество объектов. Очевидно, что это приведёт к переобучению модели (англ. overfitting; явление, при котором модель правильно принимает решения относительно данных из обучающей выборки, но плохо - относительно экземпляров, не участвовавших в обучении). Таким образом, чтобы избежать подобного явления и достичь хорошего результата, необходимо исследовать методы работы с несбалансированными данными.

1.2 Актуальность темы исследований

В последние годы, в связи с развитием науки и технологий, значительно выросло количество необработанных и доступных данных. Это в свою очередь привело к росту роли таких сфер, как инженерия данных (англ. data engineering) в частности и информационных технологий в целом, в жизни человека, начиная от приложений по автоматизации рутинных занятий работников до сложных систем для принятия решений на государственном уровне. Следовательно, особое значение приобрело и исследование способов для обработки этих данных и связанных с этой задачей проблем.

Согласно данным, которые приводят Хаибо Хе и Эдуардо А. Гарсия за первую декаду двадцать первого века [15], число публикаций, посвящённых попытке решить проблему обучения модели на несбалансированных данных, постоянно растёт в значительном темпе. К примеру, с 2002 по 2007 год количество ежегодно публикуемых исследований выросло почти в 10 раз (с 10 до около 100). Учитывая, что данным вопросом начали заниматься сравнительно недавно (тот же источник указывает, что первая работа появилась в 1997 году), а интерес к этой теме не спадает до сих пор, можно сделать вывод, что поиск решения этой проблемы имеет долгосрочные перспективы и будет оставаться актуальным и в будущем.

1.3 Объект, предмет и материал исследования

Объект исследования - текст.

Предмет исследования - методы классификации несбалансированных текстовых данных.

Материал - сообщения из социальных сетей.

1.4 Обзор литературы

Foster Provost. Machine Learning from Imbalanced Data Sets

В данной статье автор объясняет, почему несбалансированные наборы данных представляют проблемы для алгоритмов машинного обучения, показывает, что именно вызывает трудности при создании модели, и обсуждает существующие способы избежать возникновения негативных эффектов. В частности, упоминаются такие методы, как уменьшение большего/увеличение меньшего класса (англ. under-/oversampling) и изменение порога решения.

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

He H., Garcia A. Learning from Imbalanced Data

Авторы этой статьи ставили своими целями показать то, как понимается проблема машинного обучения на несбалансированных данных, и проанализировать эффективность современных решений этой проблемы. Особенное внимание уделено таким методам, как изменение выборки путём удаления/прибавления копий данных (англ. sampling) и применение разнообразных алгоритмов: с присвоением весов (англ. cost-sensitive), основанных на принципе ядра (англ. kernel-based) или на активном обучении. Также рассматриваются критерии оценки работы метода и самые актуальные и современные задачи, стоящие перед исследователями в данной области.

Помимо того, что эта статья предоставляет подробный анализ многих методов для работы с несбалансированными данными (это будет полезным материалом для определения наиболее подходящего способа для работы с текстовыми выборками), она также обозревает наиболее актуальные задачи в этой сфере. Это поможет не только выполнить данное исследование, но и наметить перспективы для его дальнейшего развития.

Nitesh V. Chawla. Data mining for imbalanced datasets: an overview

Автор в этой статье представляет свободный обзор проблемы интеллектуального анализа несбалансированных данных, особенно фокусируясь на методах оценки качества работы и методологии сэмплинга. Во время разбора упомянутой методики автор презентует собственный алгоритм овэрсэмплинга под названием SMOTE (англ. Synthetic Minority Over-sampling Technique), которая отличается от методики простого копирования миноритарного класса тем, что создаёт объекты, принадлежащие этому классу, на основе тех, что уже имеются, а не копируя их, таким образом повышая разнообразие данных и не искажая их распределения [23].

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

1.5 Формулировка цели исследования

Определения наиболее эффективного метода классификации текстов для несбалансированных данных и его реализация для русскоязычных материалов.

1.6 Формулировка задач, которые необходимо решить для достижения цели

1. Анализ методов классификации для несбалансированных данных.

2. Определение наиболее эффективного метода классификации для несбалансированных данных с учётом текстовой специфики.

3. Реализация наиболее эффективного метода классификации для русскоязычных текстов.

1.7 Методы исследования

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

Реализация выбранного метода, в частности, алгоритма машинного обучения и способа оценки его работы, будет выполнена при помощи программных средств языка программирования Python. Он представляет собой высокоуровневый язык программирования общего назначения. Его выбор обуславливается наличием большого объёма полезных функций и подключаемых библиотек, как лингвистической, так и общей направленности, и сравнительной простотой синтаксиса.

2. Анализ методов классификации для несбалансированных данных

Перед тем, как непосредственно приступить к рассмотрению проблемы несбалансированности данных, нужно определить, какие данные следует считать несбалансированными и какие виды этого явления существуют.

Прежде всего, следует описать соотношение данных разных классов в обучающей выборке: говоря строго, несбалансированными можно назвать любые данные, соотношение классов в которых не равно (даже такое незначительное неравенство, как 51:49, можно подвести под данную категорию). Однако зачастую при исследовании несбалансированных данных соотношение между классами в них определяется как 10:1 и более, так как именно при подобных пропорциях наиболее ярко проявляются искажения, характерные для процесса обучения на таких данных.

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

Также несбалансированность данных может быть относительной и абсолютной [12]. Относительная несбалансированность данных вызвана спецификой проблемы: ярким примером в данном случае может служить задача диагностики редких заболеваний, для решения которой набор данных состоит из подавляющего большинства объектов, представляющих показатели здоровых людей, и из экземпляров, представляющих, показатели больных, причём количество данных экземпляров значительно меньше в отношении к мощности мажоритарного класса. Абсолютная же несбалансированнность относится непосредственно к проблеме самих данных: она возникает при недостатке имеющихся данных для корректного описания целевой области.

Последние виды несбалансированности данных, которые будут рассмотрены в данном исследовании, это межклассовая и внутриклассовая несбалансированность. Под межклассовой скошенностью (англ. skewed) данных зачастую понимают само явление несбалансированности в целом - то есть сильное различие между количеством примеров для каждого класса в обучающей выборке. Внутриклассовую скошенность понимают как несбалансированность кластеров, которые составляют класс [15].

2.1 Сэмплинг

Чаще всего этот метод подразумевает под собой добавление в обучающую выборку экземпляров менее представленного класса или удаление из неё экземпляров доминирующего класса с целью достичь сбалансированного распределения в наборе данных. У этого способа есть различные вариации.

2.1.1 Случайный сэмплинг

Как видно из названия, случайный сэмплинг добавляет (англ. oversampling) путём копирования в обучающую выборку или удаляет (англ. undersampling) из неё случайно выбранные объекты из соответствующих классов. Таким образом, общее количество объектов в миноритарном/мажоритарном классе увеличивается/уменьшается на величину, равную количеству скопированных/удалённых объектов, так же меняется и распределение объектов между классами [15].

Достоинствами такого подхода являются его простота, лёгкость реализации и визуализации и предоставляемая им возможность изменить баланс в любую нужную сторону. Про недостатки нужно говорить отдельно в соответствии с тем, какая стратегия сэмплинга используется: несмотря на то, что обе из них изменяют общий размер данных с целью поиска баланса, их применение имеет различные последствия. В случае с андэрсэмплингом удаление данных может привести к потере классом важной информации и, как следствие, понижения показателя его репрезентативности. В свою очередь применение овэрсэмплинга ведёт к тому, что правила, генерируемые моделью, становятся слишком специфичными, а это приводит к переобучению [6].

2.1.2 Динамический андэрсэмплинг

Динамический андэрсэмплинг(англ. informed sampling) - это «обучение классификаторов на динамически формируемых на итерациях обучения классификатора сбалансированных подмножествах исходной выборки» [40]. Из тех алгоритмов, которые показали хорошие результаты при применении этого метода, следует выделить Easy Ensemble, Balance Cascade и k ближайших соседей (англ. k-nearest neighborhood).

Первые два алгоритма ставят перед собой задачу минимизировать потерю информации, к которой ведёт применение метода случайного андэрсэмплинга. Идея Easy Ensemble достаточно проста: она заключается в создании множества классификаторов, каждый из которых будет случайным образом брать подмножества (Ni) из множества объектов в мажоритарном классе (N) независимо от остальных и комбинировать отобранное подмножество с множеством объектов миноритарного класса (P) в качестве обучающего набора данных [35], то есть Ni + P, где |Ni| = |P| и |Ni| < |N|. Затем все сгенерированные классификаторы объединяются в один для выдачи финального решения. Исходя из вышеперечисленного, можно сказать, что данный алгоритм использует метод машинного обучения без учителя.

Что касается Balance Cascade, то его подход, напротив, можно классифицировать как более близкий к машинному обучению с учителем: он так же, как и Easy Ensemble, создаёт множество классификаторов, однако выбор подмножества объектов мажоритарного класса для обучения происходит иначе. Лучше всего рассмотреть этот алгоритм поэтапно: после того, как первый классификатор был построен, и с его помощью были классифицированы данные, которые не участвовали в процессе обучения (то есть множество объектов мажоритарного класса без использованного для построения классификатора подмножества), алгоритм объявляет все правильные решения избыточной информацией и удаляет их из выборки [35]. Данная процедура повторяется несколько раз до тех пор, пока окончательный размер выборки мажоритарного класса не становится примерно равным набору данных миноритарного класса. Обычно для этого необходимо T-1итераций, где T - число раз, в которое количество объектов миноритарного класса меньше количества объектов мажоритарного класса.

Метод k ближайших соседей использует одноименный алгоритм машинного обучения для андэрсэмплинга на основе данных о распределении объектов. Основные реализации этого подхода - это NearMiss-1, NearMiss-2, Near-Miss-3 и «поиск наиболее удалённых» (англ. the most distant) [17]. NearMiss-1 отбирает те объекты мажоритарного класса, чья средняя дистанция до трёх ближайших объектов миноритарного класса минимальна. NearMiss-2 отбирает те экземпляры, чья средняя дистанция до трёх наиболее удалённых объектов миноритарного класса минимальна. Near-Miss-3 отбирает заданное число ближайших к объекту миноритарного класса объектов мажоритарного класса, чтобы гарантировать, что каждый объект миноритарного класса после их удаления будет окружён хотя бы несколькими экземплярами из мажоритарного класса. Метод «поиска наиболее удалённых» отбирает те объекты мажоритарного класса, чья средняя дистанция до трёх ближайших объектов миноритарного класса максимальна.

Эксперименты показали, что применение алгоритмов на основе метода k ближайших соседей не даёт ощутимого преимущества по сравнению с методом случайного сэмплинга. Этот факт ставит их практическую ценность под сомнение: NearMiss-1 метод выдал низкие показатели точности и полноты, результаты NearMiss-2 сопоставимы с полученными от метода случайного сэмплинга, NearMiss-3 имеет хорошие показатели точности, а метод «поиска наиболее удалённых» - высокую полноту [17].

В то же время такие реализации алгоритма динамического андэрсэмпилнга, как Easy Ensemble и Balance Cascade, могут помочь добиться лучшего по сравнению со случайным андэрсэмплингом результата за счёт меньших потерь информации при удалении объектов мажоритарного класса из выборки.

2.1.3 Синтетический сэмплинг с генерацией данных

Одним из самых популярных алгоритмов для метода синтетического сэмплинга с генерацией данных является SMOTE. Он создаёт искусственные объекты миноритарного класса на основе сходств в пространстве параметров между уже существующими экземплярами на основе идеи алгоритма k ближайших соседей [24]. Если обозначить S как совокупность всех элементов обучающей выборки, а Smin - как совокупность элементов миноритарного класса, являющейся подмножеством S, то K ближайших соседей - это K объектов из Smin, евклидово расстояние которых между каждым из них и каждым экземпляром xi, принадлежащим Smin, является минимальным в n-размерном пространстве параметров X, где K - это целое число, означающее количество этих соседей.

Чтобы создать подобный синтетический набор, случайно выбирается один из K соседей, затем все его компоненты из вектора параметров умножаются на случайное число из интервала от 0 до 1. Далее полученный вектор складывается с аналогичным у xi по формуле xnew = xi + (`x'i - xi) * L, где xi, рассматриваемый в данный момент, принадлежит Smin, `x'i - это один из k соседей для xi, а L - случайное число из интервала от 0 до 1 [15]. Согласно приведённой выше формуле, сгенерированный объект, если представить его как точку и перенести всю обучающую выборку на плоскость, будет принадлежать отрезку, точками которого служат рассматриваемое xi и один из её k соседей, выбранных случайно.

SMOTE решает многие проблемы, которые возникли у метода случайного оверсэмплинга, и действительно увеличивает изначальный набор данных таким образом, что модель обучается гораздо эффективнее [15]. Тем не менее, данный алгоритм имеет и свои недостатки, главным из которых является игнорирование мажоритарного класса. Это может привести к тому, что при сильно разреженном распределении (англ. sparsed distribution) объектов миноритарного класса относительно мажоритарного наборы данных «смешаются», то есть расположатся в таком виде, что отделить объекты одного класса от другого будет очень трудно. Примером данного явления может служить случай, при котором между объектом и его соседом, на основе которых генерируется новый экземпляр, находится объект другого класса. В результате синтетически созданный объект будет находиться ближе к противоположному классу, чем к классу своих родителей. Кроме того, количество сгенерированных с помощью SMOTE экземпляров задаётся заранее, следовательно, уменьшается возможность изменения баланса и гибкость метода [4].

2.1.4 Адаптивный синтетический сэмплинг

В основе данного метода лежит синтетический сэмплинг. Целью алгоритмов, созданных для данного метода, является избавиться от недостатков, которые возникли при применении синтетического сэмплинга. Основными из них являются Borderline-SMOTE и Adaptive Synthetic Sampling (ADASYN) [15].

Borderline-SMOTE накладывает ограничения на выбор объектов миноритарного класса, на основе которых генерируются новые экземпляры. Происходит это следующим образом: для каждого объекта миноритарного класса определяется набор k ближайших соседей, затем производится подсчёт, сколько экземпляров из этого набора принадлежит к мажоритарному классу (это число принимается за m). После этого отбираются те объекты миноритарного класса, для которых верно неравенство k/2 <= m < k [14]. Полученный набор представляет собой экземпляры миноритарного класса, находящиеся на границе распределения, и именно у них вероятность оказаться некорректно классифицированными выше, чем у прочих.

Следует отметить, почему неравенство, определяющее отбор объектов, исключает случаи, при которых все k соседей принадлежат мажоритарному классу: это связано с тем, что подобные экземпляры расположены в зоне «смешивания» двух классов, и на их основе могут быть сгенерированы лишь искажающие процесс обучения модели объекты. В связи с этим они объявляются шумом (англ. noise) и игнорируются алгоритмом.

ADAZYN же, в свою очередь, основывается на систематическом методе, позволяющем адаптивно генерировать разные количества данных в соответствии с их распределениями [16]. Вначале рассчитывается количество объектов, которые необходимо сгенерировать для всего миноритарного класса, по формуле G = (|Smaj| - |Smin|) * B, где Smaj - выборка экземпляров миноритарного класса, а B - параметр, используемый для определения желаемого уровня баланса [15].

Затем для каждого объекта миноритарного класса определяется k ближайших соседей в соответствии с Евклидовым расстоянием и высчитывается пропорция Г по формуле Гi = ?i/Z, где i принимает значение от 1 до количества экземпляров миноритарного класса, ?i является числом k ближайших соседей объекта, которые принадлежат мажоритарному классу, а Z -константа нормализации, уравновешивающая формулу (Гi - такая функция плотности распределения, что ?Гi = 1) [15]. Далее определяется количество экземпляров, которые необходимо сгенерировать для каждого объекта миноритарного класса:

gi = Гi * G [16].

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

2.1.5 Сэмплинг с использованием очистки данных

Техники очистки данных (англ. data cleaning) применяются для того, чтобы удалить пересечения данных разных классов (англ. overlapping), появляющиеся при применении сэмплинга. Примером подобного метода могут служить цепи Томека (англ. Tomek links) [22]. Они представляют собой пару наиболее близких объектов разных классов. Определим её как (xi, xj) и расстояние между ними как d(xi, xj). Если не существует такого xk, для которого будет верно одно из неравенств d(xi, xj) > d(xi, xk), d(xi, xj) > d(xj, xk), то пара (xi, xj) является цепью Томека [15]. Таким образом, если пара объектов формирует цепь Томека, то либо один из объектов является шумом, либо оба из них находятся на границе классов. Следовательно, можно использовать алгоритм для нахождения подобных пар, чтобы очистить данные от нежелательных пересечений между классами после применения синтетического сэмплинга. Алгоритм будет работать до тех пор, пока все пары наиболее близких друг к другу объектов не будут принадлежать одному и тому же классу.

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

2.1.6 Сэмплинг, основанный на кластеризации

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

CBO (англ. Cluster-Based Algorithm) использует метод k средних для решения. Данный алгоритм берёт случайное множество k экземпляров из каждого кластера (для обоих классов) и вычисляет центр масс векторов параметров для них, который принимается за центр кластера [30]. На втором шаге каждый объект из оставшихся в обучающей выборке также представляется в виде вектора параметров, и метод вычисляет евклидово расстояние между ним и каждым вектором, представляющим центр кластера. Далее каждый экземпляр причисляется по вышеупомянутой метрике к наиболее близкому кластеру (наиболее близким считается тот кластер, евклидово расстояние до центра которого минимально). После этой процедуры центр масс векторов параметров для увеличившегося кластера вычисляется заново с учётом появившегося объекта, и процесс повторяется со второго шага до тех пор, пока через метод не пройдут все экземпляры.

После того, как все объекты будут обработаны, CBO увеличивает все кластеры мажоритарного класса до размера наибольшего из них методом овэрсэмплинга. Затем той же процедуре подвергаются и кластеры миноритарного класса, однако размер каждого из них будет равен количеству всех объектов мажоритарного класса после овэрсэмплинга, делённому на количество кластеров миноритарного класса [30].

После завершения работы алгоритма миноритарный класс становится гораздо лучше представлен в наборе данных [15]. Кроме того, данный метод хорошо помогает как при межклассовой несбалансированности, так и при внутриклассовой.

Недостаток данного метода в том, что число кластеров необходимо задавать заранее, и вычислить их оптимальное число можно лишь эмпирически.

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

2.1.7 Интеграция сэмплинга и бустинга

Наиболее интересным примером данного подхода является алгоритм SMOTEBoost, соединяющий в себе SMOTE и Adaboost M2 [22]. Говоря более детально, он производит синтетический сэмплинг на каждой итерации бустинга (данная процедура представляет собой последовательное формирование ансамбля алгоритмов машинного обучения с целью компенсации их недостатков). Таким образом, каждое следующее множество классификаторов больше фокусируется на миноритарном классе. Так как каждый набор классификаторов обучается на разных сэмплах данных, предполагается, что окончательное решение классификатора будет основываться на более общих для миноритарного класса правилах [15].

Другой пример подобного метода - DataBoost-IM алгоритм, который комбинирует Adaboost.M1 и техники сэмплинга данных для того, чтобы достичь увеличения доли правильных решений без ухудшения способности классифицировать объекты мажоритарного класса [15]. Основная идея DataBoost-IM заключается в генерировании объектов при помощи синтетического сэмплинга в соответствии с пропорцией трудных для обработки примеров среди классов [13]. Алгоритм ранжирует каждый из объектов обучающего набора данных в порядке убывания согласно его взвешенному распределению для классификатора t, которое представляет собой относительную сложность обучения на экземпляре выборки. Затем выбирается топ |S| * error(t) экземпляров для формирования множества E, где error(t) - величина ошибки (англ. error rate) текущего обучаемого классификатора. Таким образом, E определяется как набор тяжёлых для классификации объектов из обоих классов (подмножества Emin и Emaj соответственно). Кроме того, в связи с тем, что экземпляры миноритарного класса в целом более сложны как материал для обучения, ожидается, что Emin > Emaj [15].

Как только множество E определено, DataBoost-IM переходит к генерированию объектов методом двухуровневого синтетического сэмплинга: сначала определяются «семена» (англ. seeds) из E, на основе которых будут созданы новые экземпляры, а затем происходит непосредственно процесс генерации на основе отобранных объектов. Отбор «семян» происходит в соответствии с долей классов в E и S. Число «семян» для мажоритарного класса (Ml) определяется по формуле min(|Smaj|/|Smin|, |Emaj|), для миноритарного (Ms) - min((|Smaj|*Ml)/|Smin|, |Emin|). Затем генерируется множество Esyn (с подмножествами для каждого класса Esmin и Esmaj) в соответствии с формулами |Esmin| = Ms * |Smin| и |Esmaj| = Ml *|Smaj| [13]. Далее набор данных для обучения пополняется элементами множества Esyn для формирования более сбалансированного распределения между классами. В конце взвешенное распределение D обновляется согласно добавленным синтетическим объектам.

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

Для того, чтобы избежать подобного роста сложности и падения качества работы модели, существует подход, предложенный Мизом: вместо того, чтобы генерировать новые данные на основе вычислительных методов, используются копии данных, полученные методом случайного овэрсэмплинга. Чтобы решить проблему переобучения (в связи с «привязанностью» сгенерированных примеров к оригинальным), вводятся синтетические отклонения для этих данных. Это помогает разрушить связи между копиями и оригиналами объектов [6]. Алгоритм JOUS-Boost, основанный на данном подходе, создаёт независимо и равномерно распределённый шум на каждой итерации бустинга для объектов миноритарного класса.

2.1.8 Достоинства и недостатки сэмплинга

На практике применение сэмплинга помогло улучшить работу классификатора для некоторых алгоритмов по сравнению с обучением на несбалансированных данных [1]. Впрочем, то, насколько серьёзный прирост качества работы даст этот метод, зависит во многом от данных и задачи, которая стоит перед исследователем. К примеру, если допустить, что классификаторы могут обучаться и на несбалансированных данных, что, в принципе, не противоречит логике, есть вероятность получить результат, сопоставимый с применением того же алгоритма на данных, сбалансированных данным методом [11]. Тем не менее, для большинства несбалансированных данных применение сэмплинга действительно может помочь увеличить долю правильных решений классификатора.

2.2 Методы с распределением весов

Методы с распределением весов (англ. Cost-sensitive methods), в отличие от сэмплинга, применяются не для того, чтобы сбалансировать распределения для тренировочных данных различных классов, а для создания матрицы весов для каждого из неправильно классифицированных объектов [5].

2.2.1 Основы методов с распределением весов

Основа данных методов - матрица весов. Под ней понимается числовое представление штрафа за неверную классификацию. Если обозначить C(Min, Maj) как неверную классификацию объекта мажоритарного класса в качестве миноритарного, а C(Maj, Min) - обратный первому случай, то вполне очевидно, что C(Maj, Min) > C(Min, Maj), так как каждый из экземпляров миноритарного класса представляет собой большую долю своего класса, чем аналогичный из мажоритарного. Таким образом, цель данного метода - построить гипотезу, которая минимизирует общий набор весов для данных для обучения. Обычно для этого используется Байесовский условный риск (англ. Bayes conditional risk) [15]. В этом случае риск определяется как

R(i|x) = ?P(j|x) * C(i,j),

где P(j|x) - вероятность того, что объект x принадлежит к классу j, C(i, j) - вес ошибки, если предсказанный класс i, а верный класс - j [20].

Все алгоритмы для данного метода можно разделить на три категории [15]. Первая рассматривает цену ошибки как технику для взвешивания пространства данных на основе теоремы перенесения. Главная идея заключается в применении статистического бутстрэпа, в котором цена ошибки используется для выбора наилучшего распределения данных для обучения.

Вторая категория применяет техники минимизации веса к комбинационным схемам ансамблевых методов с целью получить чувствительные к весам классификаторы. Для достижения этого стандартные алгоритмы машинного обучения объединяются с ансамблевыми. Зачастую для данной категории алгоритмов используется фреймворк Metacost. Он использует одноименный подход, который базируется на формировании многочисленных репликаций набора данных для обучений путём бустрэпа и дальнейшем построении одного классификатора для каждого из них с целью установить вероятность каждого класса для каждого экземпляра с помощью общего решения множества классификаторов. Маркер класса для каждого объекта вычисляется заново с учётом новых полученных данных после каждого нового построенного классификатора [25].

На самом деле многие существующие исследования объединяют обе вышеназванные категории методов для того, чтобы достичь лучших результатов [15]. В связи с этим, было бы логично рассмотреть их в совокупности в данной работе.

Последняя категория алгоритмов включает функции или параметры с распределением весов напрямую в парадигмы классификации, чтобы полностью соответствовать фреймворку для них. Вследствие того, что многие из этих алгоритмов имеют свою специфику и часто могут быть применимы к сильно ограниченному числу парадигм, не существует объединяющего фрэймворка для данной категории [15]. Тем не менее, в большинстве случаев хорошо работающие решения для одной парадигмы могут быть выведены на абстрактный уровень и применены и к другим.

2.2.2 Техника для взвешивания пространства данных с адаптивным бустингом

Многие алгоритмы данного метода основывались на алгоритме AdaBoost, добавляя цену ошибки к его стратегии обновления весов. Примеры такого подхода - алгоритмы AdaC1, AdaC2 и AdaC3 [36]. Основная идея AdaBoost - итеративное обновление функции распределения на основе данных для обучения. Таким образом, на каждой итерации, число которых равно t, установленному заранее, функция распределения Dt обновляется последовательно и используется для задания новой гипотезы: Dt+1(i) = Dt(i) * exp(-at * ht(xi) * yi) / Zt, где at - параметр обновления весов, равный Ѕ ln((1-et)/t), ht(xi) - результат применения гипотезы ht на экземпляре xi, et - показатель ошибки гипотезы ht на тренировочных данных, а Zt - нормализационный фактор, вводимый для того, чтобы было корректно равенство

?Dt+1(i) = 1 [36].

Учитывая вышеописанный алгоритм для AdaBoost, фактор цены ошибки может быть применён внутри экспоненциального выражения, вне его и в обоих местах. Таким образом изменённые формулы (с добавлением данного фактора в соответствующий компонент уравнения) соотносятся с методами AdaC1, AdaC2 и AdaC3.

Фактор цены ошибки соответствует цене ошибки для каждого xi. В итоге вышеупомянутые алгоритмы увеличивают вероятность сэмплинга для объекта с более высокой ценой ошибки на каждой итерации, давая классификатору построить более специфичные правила. Было показано, что включение фактора цены ошибки в схему взвешивания AdaBoost создаёт искажения в пользу миноритарных классов и увеличивает использование более релевантных сэмплов данных для каждой гипотезы, обеспечивая формы классификации, устойчивые к нарушениям исходных предпосылок [15].

Другой чувствительный к весу алгоритм бустинга для данного метода называется AdaCost [32] Как и AdaC1, он помещает фактор цены ошибки внутрь экспонентного выражения. Однако вместо того, чтобы применять фактор цены напрямую, AdaCost использует функции добавления цены, которая повышает веса для неправильно классифицированных примеров и понижает её для правильно разобранных примеров. Формула для этой функции такова: Bi = B(sign(yi, h1(xi)), Ci), где sign(yi, h1(xi) принимает положительные значения при корректной классификации и негативные - при некорректном решении. Следует отметить, что величину данного компонента можно менять в зависимости от тех задач, которые стоят перед исследователем.

Сопоставление алгоритмов AdaC1, AdaC2, AdaC3 и AdaCost показало, что во всех случаях полученный с помощью бустинга ансамбль классификаторов показывает лучший результат согласно показателю F-меры, чем каждый из классификаторов по отдельности [36]. Кроме того, было доказано, что почти во всех случаях включение чувствительности к весу помогает улучшить результат.

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

2.2.3 Взвешенное дерево принятия решений

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

Отмечается, что точное задание порога принятия решения может быть разным в зависимости от стоящей задачи. Таким образом, предлагается использовать метод ROC-оценки (англ. receiver operating characteristic) вместо использования распределения данных для обучения, чтобы изобразить диапазон, в котором находятся метрики для оценки качества [19]. Начало графика - точка, в которой общая цена ошибки для мажоритарного класса максимальна, конец - аналогичная точка для миноритарного класса. Порог принятия решения, что дает наиболее доминирующую точку на кривой ROC, затем используется в качестве порогового значения окончательного решения [15].

Что касается взвешивания как разделяющего критерия, то одной из главных задач является настройка функции инородности (англ. impurity function), которая была бы нечувствительна к неравным весам. К примеру, такой показатель, как доля правильных решений, традиционно используется как функция инородности для деревьев принятия решений, которые выбирают разделитель с минимальной ошибкой на каждой вершине [15]. Однако данная метрика чувствительна к изменению распределения объектов, и, следовательно, наследует чувствительность к неравным весам.

Последний способ работы с взвешенным деревом принятия решений относится к его усечению. Усечение выгодно, так как оно избавляет дерево от чрезмерной сложности и улучшает его способность к обобщению, удаляя листья с вероятностью класса ниже заданного порога [15]. Однако, учитывая несбалансированность данных, усечение зачастую удаляет те листья, которые отвечают за правила для распознавания объектов миноритарного класса. Тем не менее, несмотря на то, что использование усечённых деревьев, обученных на несбалансированных данных, может понизить качество модели, использование неусечённых деревьев также не повышает качество [21]. В результате особое внимание должно быть уделено улучшению оценки вероятности класса для каждой вершины. Это позволит разработать более репрезентативное дерево принятия решений, для которого усечение будет иметь положительный эффект.

2.2.4 Достоинства и недостатки методов с распределением весов

Исследования показали, что машинное обучение с помощью методов с распределением весов и обучение на несбалансированных данных достаточно сильно связаны: теоретические основы и алгоритмы первых могут быть использованы для решения проблемы, возникающей при попытке произвести второе [19]. Кроме того, было доказано, что методы с распределением весов имеют преимущество перед методом сэмплинга при обучении на несбалансированных данных [34].

2.3 Методы на базе ядра и активном обучении

2.3.1 Основы методов обучения на базе ядра

Принципы обучения на базе ядра построены на теориях статистического обучения и размерности Вапника-Червоненкиса. Метод опорных векторов (англ. support vector machines, далее - SVM), являющийся репрезентацией парадигмы обучения на базе ядра, может обеспечить достаточно устойчивую к нарушениям исходных предпосылок классификацию при обучении на несбалансированных данных [21]. Идея SVM заключается в обучении на объектах (опорных векторах), расположенных на краю классовой области, чтобы максимизировать разделяющую классы границу между выведенной согласно гипотезе границей и опорными векторами и при этом минимизировать общую ошибку классификации [31]. Однако, учитывая то, что SVM старается минимизировать величину общей ошибки, можно сделать вывод о том, что при этом метод искажает классификацию в пользу мажоритарного класса, чтобы увеличить долю правильных решений классификатора. В идеале при наличии двух классов, сильно отличающихся по количеству объектов, разделителем будет линия или гиперплоскость, располагающаяся ближе к пограничным элементам мажоритарного класса, однако в реальности данный разделитель зачастую располагается гораздо дальше своего корректного местонахождения. Корректным в данном случае называется то местонахождение разделителя, которое позволит классификатору избежать искажений в пользу мажоритарного класса.

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

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

Что касается неразделяемых линейно пространств, то при попытке увеличить n-мерность пространства для нахождения разделительной плоскости классификатор так же будет искажён в пользу мажоритарного класса.

2.3.2 Интеграция метода на базе ядра и сэмплинга

Данный подход был достаточно широко представлен в научном сообществе разнообразными работами. Одна из них - применение метода сэмплинга SMOTE с разными весами (далее SDC). Он использует разные величины ошибки для разных классов, чтобы изменить решение модели SVM с целью передвинуть границу разделения классов дальше от миноритарных экземпляров и расположить их более плотно, чтобы обеспечить более чёткую границу [27].

Другой алгоритм для данного метода разрабатывает ансамблевую систему для изменения распределения данных без попытки изменить SVM классификатор [26].

Ещё один пример данного подхода - модифицировать SVM с помощью ассиметричных цен ошибок для того, чтобы улучшить качество работы классификатора [3]. Данный подход очень похож на идею, которая лежит в основе алгоритма AdaBoost, описанного ранее.

Гранулярный SVM с повторяющимся андэрсэмплингом (англ. Granular SVM - Repetitive Undersampling, далее GVSM-RU) - ещё один алгоритм для данного метода, который заслуживает отдельного внимания. Он основан на гранулярной SVM (далее GVSM), главные особенности которой таковы: во-первых, GVSM способен анализировать распределение данных с помощью поиска компромисса между локальной значимостью подмножества данных и его общей корреляции [38]. Во-вторых, GSVM способен улучшить вычислительный КПД для SVM метода с помощью использования параллельных вычислений. Главное отличие GSVM-RU от GSVM заключается в том, что первый использует итеративное применение SVM для андэрсэмплинг: так как все объекты миноритарного класса считаются информативными, набор экземпляров мажоритарного отбирается в соответствии с ними [37]. Затем создаётся линейный SVM с помощью гранул миноритарного класса и оставшихся его объектов в общем наборе данных. Экземпляры мажоритарного класса, определённые данной моделью как опорные вектора, формируются в мажоритарную гранулу и удаляются из первоначального набора данных. Затем строится новый линейный SVM, основанный на уменьшенной полученной выборке данных, и процесс с формированием мажоритарной гранулы и удалением её из набора данных повторяется. Данный шаг выполняется несколько раз для того, чтобы получить множество мажоритарных гранул. В самом конце итерационно производится операция группировки, которая учитывает глобальную корреляцию, с целью выбора набора объектов мажоритарного класса для построения финальной модели SVM на основе гранулярных вычислений в каждой из гранул [37].

2.3.3 Модификации методов на базе ядра для обучения на несбалансированных данных

Данная секция посвящена описанию и анализу алгоритмов, которые модернизируют сам SVM метод. Один из них основывается на ортогональной поступательной селекции (англ. orthogonal forward selection, далее OFS) и оценке регуляризованных ортогональных взвешенных наименьших квадратов (англ. regularized orthogonal weighted least squares, далее ROWLS) [33]. Данный алгоритм оптимизирует процесс обобщения в методах на базе ядра с помощью двух компонентов. Первый из них интегрирует компоненты контроля по отдельным объектам (англ. leave one out, далее LOO) и площадь под кривой (англ. area under curve, далее AUC), чтобы создать функцию LOO-AUC для выбора наиболее оптимального метода на базе ядра. Второй компонент использует функцию оценки весов из ROWLS алгоритма, чтобы присвоить больший вес ошибкам классификации миноритарного класса по сравнению с ошибками классификации мажоритарного.

Другой пример модификации метода на базе ядра - регулировка проведения границы между классами с помощью SVM метода. Данное изменение направлено на выравнивание границ с целью улучшения классификации. Есть три его разновидности: движение границ (англ. Boundary movement, далее BM), предвзятые штрафы (англ. biased penalties, далее BP) и выравнивание границ классов (англ. class-boundary alignment, далее CBA) [9].

Также был предложен алгоритм выравнивания границ ядра (англ. kernel-boundary alignment, далее KBA), главной идеей которого является модификация матрицы ядра, которую рассчитывает функция ядра на основе несбалансированного распределения данных [10]. Данный алгоритм учитывает дистанцию на основе пространства параметров и степень несбалансированности классов. Теоретический анализ и опыты показали, что этот метод имеет достаточно высокий показатель доли правильных решений и может быть применён как к векторным данным, так и к последовательностям [15].

Следующий алгоритм для обучения, TAF-SVM (англ. total margin-based adaptive fuzzy SVM, адаптивный нечёткий SVM для абсолютного разделения) был создан для уменьшения искажения результатов работы классификатора. Он обладает рядом достоинств: во-первых, он помогает избежать переобучения благодаря разбиению данных в соответствии с их относительной важностью [39]. Во-вторых, алгоритм включает различные взвешенные методы, которые позволяют ему самостоятельно адаптироваться к различным искажениям в распределении данных. В-третьих, он вводит общую парадигму разделения, которая принимает во внимание как правильно, так и неправильно классифицированные экземпляры данных при построении оптимальной разделяющей линии или гиперплоскости.

Последняя модификация, которую необходимо рассмотреть в данном исследовании, - это алгоритм k ближайших категорий (k-category proximal support, далее PSVM) с уплотнением Ньютона (англ. Newton refinement) [8]. Данный метод трансформирует парадигму максимизации с мягким зазором в простую систему k линейных уравнений как для линейных, так и нелинейных классификаторов, где k -количество классов [15]. Главное преимущество данного алгоритма - его быстрое время работы, так как всё, что ему нужно посчитать, это решение системы линейных уравнений.

2.3.4 Методы активного обучения для несбалансированных данных

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

Активное обучение, основанное на SVM методе, ставит своей целью выбрать наиболее информативные объекты из неисследованных тренировочных данных, чтобы заново обучить модель на базе ядра [28], то есть такие экземпляры, которые находятся ближе всего к текущей разделяющей линии или гиперплоскости. Далее данный метод отправляет запросы отобранным объектам на каждом шаге итерации активного обучения. Во время данной процедуры SVM модель обучается. Затем наиболее информативные экземпляры извлекаются и формируют новую выборку для обучения в соответствии с построенной гиперплоскостью. На последнем этапе новые данные для обучения и все неисследованные тренировочные данные используются заново для обучения SVM модели.

Отмечается, что процесс поиска наиболее информативных объектов может быть очень ресурсоёмок при вычислениях, так как для каждого экземпляра неисследованных данных алгоритму необходимо пересчитать заново расстояние между каждым объектом и текущей гиперплоскостью [28]. Для того чтобы решить данную проблему, был предложен метод эффективного отбора таких информативных объектов из случайного множества обучающей выборки, чтобы сократить цену вычислений для больших объёмов несбалансированных данных.

2.3.5 Достоинства и недостатки методов на базе ядра и активном обучении

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

2.4 Определение наиболее эффективного метода классификации для несбалансированных данных с учётом текстовой специфики

Чтобы проверить эмпирически методы для работы с несбалансированными данными, была выбрана задача бинарной классификации высказываний на русском языке в зависимости от того, корректны ли они или содержат какую-либо оскорбительную информацию (под ней понимается выраженное в текстовой форме оскорбление, то есть «унижение чести и достоинства человека в неприличной форме» [43, с. 143]). Выбор задачи обусловлен её актуальностью (существующие решения данной проблемы в основной массе базируются на фильтрах определённых слов, а это не даёт возможности оценить контекст, в котором было использовано слово; кроме того, обычно списки стоп-слов для подобных фильтров включают очень ограниченное количество лексики) и принадлежностью к задаче несбалансированной классификации (очевидно, что оскорбительных высказываний значительно меньше, чем нейтральных текстов).

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

После анализа методов сэмплинга, методов с распределением весов и методов на базе ядра и активном обучении, был сделан вывод о том, что наиболее логично будет использовать метод с распределением весов или метод на базе ядра. Метод сэмплинга был признан неподходящим для данной задачи, так как при его использовании слишком велик риск переобучения или потери информации (в зависимости от того, какой стратегии придерживаться при балансировке выборки: овэр- или андэрсэмплинге). Данный подход во многом нацелен на то, чтобы изменить данные, а не сам классификатор непосредственно. Было доказано, что эффективнее работать с изменением порога решений и весами ошибок разного рода, чем пытаться изменить распределение обучающего набора данных случайным образом или синтетически [34].