Диссертация (1149537), страница 4
Текст из файла (страница 4)
, an ) – вектор коэффициентов и b – скаляр. Такойвид предсказателя p = a · x + b естественно интерпретировать как разделяющую гиперплоскость между различными классами.Метод опорных векторов был впервые предложен в [40], [140]. Основная идея алгоритма заключается нахождении оптимальной разделяющейгиперплоскости. Рассмотрим пример на Рис. 1.1. Два класса отмеченыкрестом и кружком, три разделяющие гиперплоскости A, B и C. Гиперплоскость A лучше всего разделяет классы, так как расстояние от любогообъекта до нее наибольшее.
Говорят, что гиперплоскость имеет наибольший зазор разделения. Вектор нормали к гиперплоскости указывает нанаправление в пространстве признаков, вдоль которого происходит максимальное различение.Одним из преимуществ метода опорных векторов является его устойчивость к большой размерности, поскольку обучение происходит практически независимо от размерности признакового пространства.
Отборпризнаков редко требуется, так как для классификации выбираются элементы множества данных (опорные вектора). Как отмечено в работе [79],текстовые данные идеально подходят для этой модели классификатора из-за высокой размерности и разреженности данных. Метод опорныхвекторов популярен в приложениях распознавания образов, распознавания лиц, фильтрации спама [27], [49], [114]. Более глубокий анализ методапредставлен в [78].Регрессионные модели обычно применяются в задачах выявления зависимости между вещественнозначными признаками.
Тем не менее бинарные значения меток классов можно рассматривать как частный слу21Рис. 1.1: Разделяющая плоскость.чай вещественнозначного признака и применять в задаче классификациирегрессионные модели.Одной из первых регрессионных моделей, примененной к задаче классификации текстов был метод наименьших квадратов [145]. Допустим,предсказанная метка класса pi = a · xi + b. Истинная метка yi известна и и требуется найти такие значения a, b, которые минимизируютPn2i=1 (pi − yi ) .
Пусть p — 1 × n вектор-индикатор бинарных значенийклассов, b равняется 0. Таким образом, если x — матрица n × d термдокумент, требуется найти такой вектор регрессионных коэффициентов1×d, который минимизирует ||a · xT − p||, где ||·|| — норма Фробениуса.Задачу можно обобщить на случай k классов, положив p — k×n матрицабинарных значений. В этой матрице в каждом столбце ровно одно значение 1, и соответствующий ей номер строки служит меткой класса дляобъекта. В работах [145], [146], [148] был проведен сравнительный анализметода наименьших квадратов с множеством других методов классификации, и было показано, что метод наименьших квадратов оказываетсядостаточно робастным на практике.Другим способом применения регрессионной модели к задаче классификации является логистическая регресия [111], где в качестве целевойфункции, которую нужно оптимизировать, звыступает функция правдо22подобия.
Предполагается, что вероятность наблюдать метку yi равняетсяp(C = yi |xi ) =Или иначеlogexp(a · xi + b),1 + exp(a · xi + b)p(C = yi |xi )= a · xi + b.1 − p(C = yi |xi )Таким образом логистическая регрессия — это линейный классификатор,так как граница принятия решения является линейной функцией от признаков. В случае бинарной классификации значение p(C = yi |xi ) можетбыть использовано для определения метки класса (например, используя пороговое значение 0.5, если вероятность превышает порог, отнестиобъект к классу ’1’, в противном случае — к классу ’0’).
В случае многоклассовой классификации метка класса, имеющая наибольшее значениесогласно p(C = yi |xi ), будет присвоена xi . Пусть дан набор тренировочных данных {(x1 , y1 ), . . . , (xn , yn )}, оценка параметров a происходитQпутем максимизации функции правдоподобия ni=1 p(yi |xi ).1.3.4Классификатор k ближайших соседейКлассификаторы на основе близости используют для классификациифункции расстояния.
Основная идея заключается в том, что документы,относящиеся к одному классу с большой вероятностью находятся близкодруг другу согласно значению некоторой функции близости, напримерскалярного произведения или косинусной меры сходства [125]. Для того, чтобы классифицировать тестовый объект можно воспользоватьсяодним из следующих подходов:• Определить k ближайших к тестовому объекту соседей в тренировочном наборе данных.
Наиболее распространенный среди соседейкласс возвращается как метка класса для тестового объекта. Примеры таких подходов изучены в [41], [66], [145]. Выбор k обычноварьируется от 20 до 40, в зависимости от размера словаря.23• На этапе предобработки данные в тренировочном наборе объединяются в группы документов, принадлежащих одному классу. Длякаждой группы создается мета-документ, являющийся представителем класса. Подход k ближайших соседей, описанный выше, применяется к новому множеству мета-документов (обобщенных экземпляров [93]), а не к множеству исходных документов. Реферирование на этапе предобработки улучшает эффективность классификатора, так как сокращает количество вычислений расстояний.В случае, если в множестве данных большое количество выбросов,реферирование так же может повысить качество работы классификатора.
В работах [67], [93], [120] описаны примеры таких подходов.Как отмечено в статье [145], в классификаторах k ближайших соседей значительную роль играет отбор признаков и представление документов. В объемном корпусе документов большинство термов можетне относиться к интересующей категории. Поэтому в [145] было предложен ряд методов выявления ассоциаций между словами и категориями.Далее эти ассоциации используются при построении признакового описания документа, так классификатор k ближайших соседей будет болеечувствительным к классам в коллекции документов. Похожее наблюдение было сделано в статье [66], где было показано, что добавление весовтермам (на основе их ассоциации с классом) повышает качество классификатора.1.4Кластеризация0Пусть Z = {z j }mj=1 , ρ(z, z ) – метрика.
Задача кластеризации заключается в нахождении разбиения множества Z на k кластеров таких, чтоT k (Z) = {C1 , . . . , Ck },Z=k[Ci ,Ci ∩ Cj = ∅, i 6= j.i=124Для разбиения T k (Z) функция γT k : Z → {1, . . . , k}, соотносящаяточки кластерам, определена следующим образомγT k (z) = i ⇔∈ Ci , i = 1, . . . , k.Таким образомCi = {z ∈ Z|γT k (z) = i}.Для любого k для множества Z существуют различные разбиения T k (Z).Разбиение должно обладать следующим свойством: объекты, принадлежащие одному кластеру более “похожи” между собой, чем объекты,принадлежащие разным кластерам. Определим qi – функцию “близости”к кластеру i, для любого i = 1, .
. . , k. Рассмотрим задачу минимизации(1.1)kf (T , z) =kXγT k (z)qi (T k , x) → min .Tki=1Результат минимизации функции (1.1) зависит от z. Пусть вероятностноераспределение P (·) определено на множестве Z. Тогда можно рассматривать задачу минимизации функции качества(1.2)F (T k ) = Ef (T k , z) =k ZXi=1qi (T k , z)P (dz) → minCiTkВ некоторых случаях можно ограничиться разбиением T k , котороеполностью определяется множеством k векторов c1 , .
. . , ck ∈ Rm , которыеформируют m × k матрицу C = (c1 , . . . , ck ) и для i = 1, . . . , k и z ∈ Zфункции q( ·, z) зависят только от ci , то есть qi (·, ·) : Rm ×Z → R. Правилоразбиения можно задать следующим образомCi (Z) = {z ∈ Z :qi (ci , z) < qj (cj , z), j = 1, . .
. , i − 1qi (ci , z) ≤ qj (cj , z), j = i + 1, . . . , k}, i = 1, . . . , k,которое минимизирует (1.1). Вектора ci , i = 1, . . . , k интерпретируются25как центры кластеров, когда Z — подмножество евклидова пространстваRm . В этом случае функционал качества (1.2) принимает форму(1.3)kF (T ) =k ZXi=1qi (ci , z)P (dz) → min .TkCiи может быть переписан в видеZ(1.4)F (C) = hl(C, z), q(C, z)iP (dz) → min,CZгде l(C, z) и q(C, z) — вектора длины k такие, что первый состоит иззначений характеристической функции 1Ci (C) (C, z), а второй из qi (ci , z),i = 1, .
. . , k.Такая формализация имеет простую геометрическую интерпретацию.Пусть распределение P (·) равномерно на Z и пусть функцииqi (ci , z) = ||ci − z||2 , i = 1, . . . , kпредставляют расстояние до центров кластеров c1 , c2 , . . . , ck . ИнтегралZ||ci − z||2 dzCiопределяет разброс точек x множества Ci . Функционал (1.4) принимаетвид(1.5)F (C) =l ZXi=1||ci − z||2 dz → min .CCiТаким образом, задача кластеризации свелась к задаче нахождения такого множества центров {c∗1 , . . .
, c∗k }, для которых общий разброс точекминимален.В области анализа текстов кластеризация может проходить на разных уровнях, в качестве кластеров могут выступать целые документы,абзацы, предложения или термы. Кластеризация активно применяется26в категоризации документов для улучшения поиска или просмотра. Например, в работе [42] авторы использовали алгоритмы кластеризациидля составления оглавления большой коллекции документов, в [17] припомощи кластеризации строилась контекстная система информационного поиска.Многие алгоритмы кластеризации можно применять к текстовым данным, используя, например, их векторное представление.
Однако, текстовые данные имеют ряд особенностей представления:1. Представление текста имеет высокую размерность, но сами данныеразреженные. Другими словами, размер словаря коллекции можетбыть очень большим (например, порядка 105 ), но в отдельном документе встречаться всего несколько сотен слов.2. Слова из словаря рассматриваемой коллекции документов обычно связаны между собой. Следует учитывать корреляцию междусловами при разработке алгоритма кластеризации.3. Документы в коллекции отличаются длиной (количеством встречающихся слов), важно производить нормализацию представленийтекста.Ряд алгоритмов, оптимизирующих представление текста, учитываяперечисленные выше характеристики, предложен в [124].1.4.1Иерархическая кластеризацияНазвание “иерархическая” объясняется тем, что в результате работыалгоритмов строится иерархия группы кластеров.
Построение иерархииможет происходить сверху-вниз (разделительная кластеризация) или снизувверх (агломеративная). Алгоритмы иерархической кластеризации относят к алгоритмам кластеризации, использующих функцию расстояния (похожести) ρ(X, X 0 ) для определения близости текстовых документов.
Обзор алгоритмов иерархической кластеризации представленв [109], [110], [143].27При разделительном подходе один кластер, состоящий из всех документов коллекции, рекурсивно разделяется на под-кластеры. В агломеративном подходе, изначально каждый документ представляет отдельныйкластер. Затем последовательно наиболее схожие кластеры объединяются, пока все документы не образуют единый кластер.Для кластеров, состоящих из одного элемента определена функциярасстоянияD({x}, {x0 }) = ρ(x, x0 ).На каждой итерации слияния схожих кластеров вместо кластеров Uи V образуется новый W = U ∪ V .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
