On features selection approach for text mining problem.pdf Разработка медицинских баз данных и предоставление свободного доступа к ним позволяет пользователям осуществлять эффективный поиск документов, содержащих высокоспециализированные медицинские знания. Быстрый рост числа каталогов научных статей и текстовых хранилищ, например таких, как MEDLINE или PubMed Central (PMC), обуславливает необходимость в развитии методов автоматической расстановки тэгов и автоматической классификации текстовых данных. Специалисты часто осуществляют поиск медицинских документов для получения информации о современных средствах диагностики, лекарственных препаратах, возможных осложнениях в результате того или иного лечения и т.п. При этом они используют в запросах специфическую терминологию, которая может быть правильно интерпретирована только с помощью специализированной медицинской онтологии (содержащей специальные для медицины значения терминов), например такой, как Medical Subject Headings (MeSH). Для того чтобы облегчить процесс поиска, все документы базы данных должны быть проиндексированы в соответствии с онтологией. Результаты поиска могут быть сгруппированы в классы документов, которые соответствуют разным разделам (например, «методы диагностики», «симптомы» и т.д.). Такие классы могут быть пересекающимися: один документ может содержать информацию, относящуюся к различным разделам, так статья, посвященная современным способам лечения какого-либо заболевания, может включать в себя как методы диагностики, так и симптомы, информацию о лекарственных препаратах, их противопоказаниях и т.д. 1. Постановка задачи Постановка задачи классификации сформулирована организаторами JRS 2012 Contest [1]. Имеется некоторое множество научных статей по медицине, которые необходимо отнести к 83 классам. Классы пересекаются, так что статья может быть отнесена сразу к нескольким классам. Ситуация, когда статья не принадлежит ни одному из заданных классов, исключена из рассмотрения. Организаторы конкурса предоставили обучающую выборку - информацию о 10 000 статьях с указанием классов, к которым они отнесены. Признаками для классификации в рассматриваемой задаче принимают так называемые «степени раскрытия» определенных научных терминов в статьях. Степень раскрытия термина определяется частотой, с которой термин встречается в статье, а также некоторыми дополнительными факторами, которые организаторами конкурса не разглашаются. Выделяют 25 640 ключевых терминов, степени раскрытия которых приведены для каждой статьи в обучающей выборке. Как правило, подавляющее большинство степеней раскрытия для конкретной статьи будет принимать нулевое значение, что соответствует отсутствию термина в статье. Сформулированную задачу классификации можно отнести к сложным и большим, так как модель принятия решения отсутствует, классические методы классификации неприменимы. Исходный набор признаков классификации значительно превышает объем обучающей выборки: доступные данные в обучающей выборке плохо обусловлены. Важнейшей задачей на пути решения сформулированной проблемы классификации становится преобразование множества признаков. Требуется перейти к новой системе признаков, значительно уменьшив их количество без потери информативности нового набора. 2. Описание алгоритма Задача классификации 83 пересекающихся классов может быть сведена к решению 83 задач бинарной классификации (принадлежности или непринадлежности статьи к каждому классу). Введем следующие обозначения: xj - степень раскрытия j-го термина в i-й статье (j = 1, n, г = 1, N), степень раскрытия термина может принимать значение от 0 до 999: 0 - термин в статье не встречается, 999 - термин раскрыт в статье полностью; yk - принадлежность г-й статьи к k-му классу (i = 1, N, k = 1, m ) k = |1, i -я статья e k -му классу, У (0, i-я статья г k-му классу; Qk = {i: yk = ij - множества порядковых номеров статей k-го класса, Tk = {j : x/ > 0, i e Qk j - множества терминов, встречающихся в статьях, принадлежащих k-му классу. В исходном пространстве n признаков классы не являются компактными. Гипотеза компактности состоит в том, что элементы одного и того же класса отражаются в признаковом пространстве в геометрически близкие точки. Если среди признаков имеется много случайных, неинформативных, то элементы класса могут оказаться далекими друг от друга и рассеянными среди элементов других классов [2, с. 29]. Таким образом, требуется выделить такое подмножество исходных признаков, в котором множество элементов класса компактно. Однако применение известных алгоритмов выделения информативных признаков, таких, как метод последовательного добавления признаков, метод последовательного сокращения [2, с. 108], метод случайного поиска с адаптацией [2, с. 110], неприменимы из-за отсутствия большинства терминов в каждой статье. Исключение одного любого признака из множества T не приведет к росту качества классификации, так же, как и добавление одно информативного признака к другому. Идея предлагаемого подхода к выделению информативных признаков состоит в синтезе набора подпространств исходного пространства признаков, таких, что в рамках каждого подпространства среди элементов выборки с ненулевыми значениями признаков возможно выделение компактных групп элементов принадлежащих и не принадлежащих к классу. Для каждого подпространства признаков из исходной формируется своя обучающая выборка, элементы которой не содержат признаков с нулевыми значениями. Объединение полученных подпространств не принесет значимого улучшения качества классификации, так как в рамках каждого подпространства признаков возможно вынесение однозначного решения о принадлежности или не принадлежности элемента с ненулевыми значениями признаков к классу, а после объединения подпространств в одно, за счет уменьшения объема выборки, количество выносимых решений сократится. Расстояние р j (xi, x5) между элементами xi и x5 в пространстве j-го признака будем определять как lxj — x] I xjxl > 0, ] I P] (xi, x5 ) = ' V 1, x]x1] = 0. Расстояние р j (xi, x5) может принимать значения от 0 до 1: р j (xi, x5) = 0 , если степени раскрытияj-го термина в статьях i и 5 равны, рj (xi, x5) = 1, если j-й термин не встречается хотя бы в одной из статей i и 5. Теперь введем меру расстояния рр (xi, x5) между элементами xi и x5 в произвольном подпространстве признаков P = (p1, p2, ..., pr), где r - размерность подпространства, r e {1, 2, ..., n},pv e {1, 2, ..., n}, v = 1,r : рР ( xi , x5 ) = xi + x\ rlЕрpv (x,x5), maxPpv (x,,x5) р^ (xi, x5,i,k,0 ) U PDlk (xi, x*,i,k,1) = PDlk (xi, x*,i,k,0 ) = 1 где x*,i,k,0 = arg min {p^ (x, xs): xs г ^, x * xs j, x*,i,k,1 = argnxin{ (x, xs): xs eQk, x * xs}. Иными словами, в каждом из искомых пространств признаков Dk ближайшим к элементу, принадлежащему k-му классу, должен быть элемент k-го класса, а к элементу, не принадлежащему этому классу, - элемент также ему не принадлежащий. Определим итеративную процедуру построения множества пространств признаков Dk ={ok, l = 1, Lk j: 1. r = 1, Lk = 0, пространство поиска r-го термина в комбинации Gk = Tk ; 2. Формирование множества подпространств признаков Dk = (dkt,,...,dkrl), где dkt e Gk, v = 1, r , l = Lk +1, Lk + Rkr , Rkr - количество множеств признаков размерности r , таких, что выполняются условия (1); 3. Сокращение пространства поиска r-го термина: Gk = Gkr \ ULl+S Dk , Lk = Lk + Rkr , r = r + 1, Grk = Gkr-1; 4. Классификация в подпространствах Dk ={ог , l = 1, Lk j: yki = max ^ : xq = arg mm pDk (xi, xs)j. 5. Вычисление ошибки классификации: Er = N-1 ±I (yk * yk ) . (2) i=1 V ' 6. Если Er < e или Er.1 - Er < 5, или Gk = 0 , множество подпространств признаков Dk ={оГ , l = 1, Lk j сформировано, иначе к шагу 2. Формирование наборов информативных признаков происходит последовательно: если Dk удовлетворяет условиям (1), то Df не может быть подпространством любого другого набора признаков. Таким образом, с одной стороны, с ростом размерности искомых пространств r возрастает количество комбинаций признаков, с другой стороны, сокращается область поиска таких комбинаций Gk. Специфика задачи классификации текстовых документов такова, что большинство статей содержат от 80 до 130 терминов (см. рис. 1), большинство терминов встречаются менее чем в 100 статьях (см. рис. 2). Анализ рис. 1 и 2 показывает, что рост количества комбинаций признаков с ростом количества признаков в подпространстве r ограничен. Это обусловлено тем, что вероятность того, что комбинация терминов встречается во многих статьях, мала. 1200 800 400 0 60 100 140 180 Количество терминов в статье 220 Рис. 1. Гистограмма распределения количества терминов в статье я ч £ 5000 4000 3000 Й 2000 1000 100 Количество статей Рис. 2. Гистограмма распределения количества статей, содержащих одинаковые термины 200 я 3 30 25 1 20 g 15 tr я ч £ 10 5 JZL "|—г 500 1000 1500 2000 Количество статей в классе 0 2500 Рис. 3. Гистограмма распределения статей в классах Конфигурации наборов информативных признаков непосредственно зависят от количества элементов, принадлежащих k-му классу. При этом элементы обучающей выборки распределены по классам неравномерно: гистограмма распределения статей в классах |Qk| приведена на рис. 3. Следует отметить, что для некоторых малочисленных классов пространства признаков Dk = {pl , l = 1, Lk j, удовлетворяющие условиям (1), могут не существовать. Применим процедуру выделения подмножеств информативных признаков для классов с различным количеством представителей. Вначале рассмотрим самый многочисленный класс (k = 40, |Qk| = 2475). На рис. 4 приведены зависимости количества подпространств признаков Dk, количества признаков, входящих хотя бы в одно подпространство множества Dk и ошибки классификации от r (E0 =|Qk|/N), гистограмма распределения количества подпространств, содержащих одинаковые термины. Rr40 -104 8 2 0 0 4000 3000 2000 1000 1000 800 600 400 200 0 200 400 600 800 1000 Количество подпространств я ч £ Er 0,2 0,1 я ч £ 0 Рис. 4. Зависимость количества подпространств признаков от размерности подпространства r (а); зависимость количества признаков, входящих в подпространства, от размерности подпространства r (б); ошибка классификации (в); гистограмма распределения количества подпространств, содержащих тот или иной термин Применим алгоритм выделения информативных признаков для класса, находящегося на 42-м месте по количеству представителей (см. рис. 5). Выбор этого класса (k = 29, |Qk| = 201) обусловлен тем, что количество представителей для него - среднее по всем классам. Rr29 -104 3 2 1 0 1 4 r 1000 2000 Количество подпространств Рис. 5. Зависимость количества подпространств признаков от размерности подпространства r (а); зависимость количества признаков, входящих в подпространства, от размерности подпространства r (б); ошибка классификации (в); гистограмма распределения количества подпространств, содержащих тот или иной термин (г) 0 0 Er 0,02 0,015 0,01 0,005 0 Приведенные графики (рис. 4, 5) иллюстрируют закономерности функционирования алгоритма классификации. Сходимость ошибки к установившемуся значению фактически наблюдается для значения r = 2. Табл. 1 содержит результаты сравнения ошибок классификации (2), вычисленных по методу скользящего экзамена, для следующих методов: 1 - предложенного алгоритма синтеза информативных признаков с последующей классификацией, 2 - метода ближайших соседей, учитывающего все n признаков, 3 - алгоритма Random Forest [3, с. 5], учитывающего все n признаков. Сравнение методов классификации по критерию качества k |Qk| Ошибка классификации 1 2 3 29 201 0,0044 0.0183 0.0188 40 2475 0,054 0.1869 0.198 Заключение В работе предложен подход к синтезу системы информативных признаков в задаче классификации текстовых документов. Он предусматривает формирование подпространств признаков в соответствии с предположением о компактности объектов классификации в каждом из подпространств. Подпространства признаков, входящие в систему, выбирались исходя из выполнения условий (1). Описанный подход позволяет значительно улучшить качество классификации по сравнению с методом ближайших соседей, учитывающим все n признаков, Random Forest. Дальнейшее улучшение качества будет требовать корректировки метрики, критерия принадлежности к классу.

Скачать электронную версию публикации