Building a style sheet using text classification algorithms based on decision trees.pdf В 2006 г. на факультете информатики Томского государственного университета был разработан программный комплекс «СтилеАнализатор» [1], предоставляющий пользователю необходимый инструментарий для автоматического анализа текстов статистическими методами, в том числе методами классификации текстов на основе деревьев решений. В последующие годы функциональные возможности системы «СтилеАнализатор» наращивались совместными усилиями факультета информатики ТГУ и лаборатории общей и компьютерной лексикологии и лексикографии филологического факультета Московского государственного университета им. М.В. Ломоносова. В частности, возникла необходимость построения и включения в «СтилеАнализатор» алгоритмов классификации с функциональностью экспертизы текстов, использующей «стилевые профили» текстов по авторам, жанрам и т.п. Настоящая работа посвящена построению таблиц стилей текстовых произведений с использованием алгоритмов классификации на основе деревьев решений. 1. Постановка задачи Пусть имеется множество текстов определённого жанра (например, произведений художественной прозы ряда писателей). В предположении, что каждый писатель обладает своим индивидуальным авторским стилем, его тексты образуют определённый авторский стилевой класс. В качестве признаков стиля можно использовать различные характеристики текста. Часто используют числовые характеристики - частоты встречаемости в текстах тех или иных слов (например, служебных или наиболее употребительных), словосочетаний, буквосочетаний (би-грамм, триграмм и др.) и т.п. Набор таких числовых характеристик для каждого текста образует n-мерный вектор признаков стиля этого текста. Задача состоит в том, чтобы по множеству «обучающих» текстов, принадлежность которых к авторским стилевым классам известна, и по набору n-мерных векторов признаков этих текстов построить алгоритм оптимального (по некоторому критерию, например, информационному) последовательного бинарного разбиения n-мерного признакового пространства стилей текстовых произведений на 2n непересекающихся n-мерных интервалов, образующих таблицу стилей текстов. Такая таблица определит «стилевой портрет» (профили стилей) соответствующего корпуса текстов. 2. Классификация при помощи дерева решений Для решения поставленной задачи необходимо использовать «признаковый» классификатор - алгоритм, позволяющий по n-мерному вектору признаков отнести текст, класс которого неизвестен, к тому или иному классу. Одним из наиболее эффективных классификаторов является классификатор, построенный на основе использования деревьев решений [2]. Как известно [2-4], деревом решений называется представленный в виде ациклического графа план, по которому производится классификация объектов, описанных набором признаков, по некоторому (обычно, информационному) критерию. В задаче классификации текстов объектами являются тексты, а признаки характеризуют классы текстов (в данной работе - это признаки авторского стиля, но это могут быть признаки, характеризующие жанровый или какой-либо другой стиль). Ограничимся количественными признаками стиля, такими, например, как частоты появления в тексте тех или иных служебных слов. Дерево решений - это классификатор, полученный из обучающего множества, содержащего объекты (в данном случае тексты) и их характеристики (признаки класса), на основе обучения. Для обучения такого классификатора на его вход подаются тексты известных классов, например определённых авторов, являющиеся представителями классов авторских стилей. Каждый узел дерева содержит условие ветвления по одному из признаков. В первый (корневой) узел дерева входят все тексты, представленные всеми имеющимися признаками. Для текущего узла дерева выбирается признак, наиболее подходящий с точки зрения выбранного критерия, и находится его оптимальное пороговое значение. На основе этого значения производится разделение обучающей выборки на две части. В одну часть попадают тексты, у которых значение признака ниже оптимального порога, в другую - у которых оно выше или равно порогу. Каждая из образовавшихся частей становится узлом дерева следующего уровня или концевым узлом, то есть листом, если она содержит тексты только одного класса. В дальнейшем ветвлении дерева этот признак больше не участвует. Для каждого неконцевого узла выбирается один из оставшихся признаков, наиболее подходящий с точки зрения того же критерия, и определяется оптимальное пороговое значение этого признака. На основе полученного порогового значения признака все тексты, оказавшиеся в этом узле, разделяются, в свою очередь, на две части по значениям этого признака у каждого текста. Тексты со значениями признака разделения ниже порога попадают в одну часть, а тексты со значениями признака разделения выше или на уровне порога - в другую. Процесс ветвления идёт до тех пор, пока не будет исчерпано всё множество признаков или пока все узлы дерева не станут листьями. На этом обучение дерева решений завершается. Взяв в качестве испытуемого любой произвольный текст и следуя по обученному таким образом дереву, сравнивая значение признака разделения этого текста в каждом узле дерева с соответствующим этому узлу пороговым значением признака разделения, мы окажемся в одном из листьев дерева, приписав тем самым текст классу этого листа. 3. Таблицы стилей текстов и профилей стилей текстов Дерево решений в скрытом виде хранит в себе информацию о свойствах классов, характеризуемых выбранным набором признаков (частот), и позволяет классифицировать неизвестный текст. Но использовать эту информацию для сравнения классов практически невозможно, так как она не представлена в явном, интерпретируемом с этой точки зрения виде. Эту информацию надо извлечь из дерева решений и представить в таком виде, который позволит сравнивать классы между собой и оценивать степень схожести стиля неизвестного текста со стилем текстов какого-либо известного класса. Для этой цели в данной работе предлагается строить специальные таблицы стилей текстов и профилей стилей текстов. По исходной таблице значений признаков, полученных для обучающих текстов известных классов, предлагается сначала построить множество одноуровневых бинарных деревьев решений по каждому признаку. Множество обучающих текстов по каждому признаку разбивается оптимальным образом на два подмножества: подмножество текстов, для которых значения признака меньше некоторого порога, и подмножество текстов, для которого значение признака больше либо равно порогу. Пример фрагмента таблицы входных данных для 9 служебных слов приведён на рис. 1. В обучающем множестве представлены 3 произведения Н.В. Гоголя («Вечера на хуторе близ Диканьки», ч. 1 и ч. 2, «Вий»), 3 - И. А. Гончарова («Обломов», «Обрыв», «Обыкновенная история»), 3 - Ф.И. Достоевского («Бедные люди», «Белые ночи», «Бесы»), 2 - А.И. Куприна («Колесо времени», «Яма»), 3 -М.Ю. Лермонтова («Ашик Кериб», «Вадим», «Герой нашего времени»), 3 -Н. С. Лескова («Загадочный человек», «На ножах», «Некуда»). В левом столбце таблицы приведены метки классов - авторы текстов, используемых для обучения классификатора. Каждая строка соответствует тексту художественного произведения какого-либо автора и представляет объект соответствующего авторского класса. В ячейках таблицы указаны абсолютные значения частот появления в соответствующем тексте того или иного служебного слова. В «СтилеАнализаторе» для обучения дерева решений (построения порогового правила разбиения множества текстов на два подмножества по каждому признаку) используются относительные частоты (доли абсолютных частот употребления того или иного служебного слова в общем числе употребления в тексте служебных слов). Это позволяет избежать искажений результатов классификации из-за различий в объёмах текстов, непосредственно влияющих на значения абсолютных частот. В результате каждому тексту ставится в соответствие вектор-строка, содержащая в качестве признаков значения относительных частот. Геометрически каждый текст может быть представлен тогда точкой в многомерном координатном пространстве относительных частот. Тексты каждого класса (например, каждого определённого автора) образуют в таком пространстве некоторое многомерное облако (диаграмму рассеяния элементов класса). Блоки в на с о через из-за хотя когда чтобы Гоголь Н В 611 502 272 30 12 2 3 G3 53 Гоголь Н В S17 675 437 GG 13 11 17 103 70 Гоголь Н В 2Э2 212 135 32 3 5 3 40 15 ГончаровИА 3524 2401 2030 301 77 19 54 3G4 10 ГончаровИА 5033 3500 29Э1 550 166 41 76 57G 126 ГоичэроеИА 1794 1200 1174 364 53 14 17 132 27 ДостоеаскийФМ 761 4S1 333 101 13 G 15 105 62 ДостоеаскийФМ 332 202 130 60 14 2 0 72 2 ДостоеаскийФМ 5001 2460 2525 0G4 101 53 200 393 335 КуприкАИ 4G5 24G 100 116 0 1 11 74 26 КуприиАИ 2032 1376 1125 247 9G 22 41 204 121 ЛермонтовМЮ G2 32 25 3 1 2 1 G 1 ЛермонтовМЮ 699 543 232 115 27 4 14 95 20 ЛермонтовМЮ 059 701 421 105 3S 13 39 97 9 ЛесковН С 1014 370 427 127 2G 7 20 52 92 ЛесковН С 5171 311В 2729 702 1G9 54 104 466 350 ЛесковН С 4251 2472 2300 669 195 67 44 254 209 Рис. 1. Таблица входных данных алгоритма классификации по авторскому стилю (абсолютные частоты) Рис. 2. Бинарное дерево решений для классификации текстов по частоте появления служебного слова «через» На рис. 2 в качестве примера приведено бинарное дерево решений для разбиения текстов по одному из индивидуальных признаков стиля текста - частоте появления служебного слова «через». Одноуровневая бинарная классификация разделила в этом примере множество 17 текстов 6 указанных в корне дерева русских писателей 19-го века на два подмножества, образующие листы дерева в соответствии с определённым критерием классификации, то есть критерием отнесения каждого текста к одному из двух (в бинарной классификации) стилевых классов. Аналогичная классификация проведена и по другим признакам (другим служебным словам). Порог для каждого признака находится однозначно по информационному критерию, лежащему в основе правила принятия решений по дереву решений [2-5]. Рассмотрим вопрос о выборе оптимальных порогов подробнее [2]. Пусть для обучения дерева решений (для отыскания оптимальных порогов бинарного разбиения текстов по каждому признаку) используется N текстов, образующих множество A текстов, принадлежащих K классам (авторам) и характеризующихся n признаками (относительными частотами V появления в каждом тексте, например, одного из n служебных слов). Пусть Nk - число текстов k-го класса, k = 1, K, так что ^K Nk = N . Тогда вероятность того, что наугад взятый текст будет текстом k-го класса (эмпирическая априорная вероятность k-го класса) равна Pk = Nk / N. Статистическая неопределённость (энтропия) [6] множества классов выражается формулой H(A) = -tPk log2 Pk . (1) k=1 Пусть по каждому j-му признаку, j = 1, n, выбирается порог hj разделения текстов на два подмножества по значению Vj j-го признака каждого /-го текста, так что если Vj < hj, то i-й текст относится к подмножеству Ay, а если Vj > hj, то i-й текст относится к подмножеству A2j. Объединение этих подмножеств по n признакам даёт множества A1 и A2, а объединение A1 и A2 - множество всех текстов A: A = U a j, A2 = UA2 j, A = A! и Л. j =1 j =1 Пусть N1jk - число текстов k-го класса, попавших во множество Ay. Тогда общее число текстов, попавших во множество Ay, есть ^ K Nj jk = Nj j . Вероятность того, что наугад взятый текст из множества Ay будет текстом k-го класса (эмпирическая апостериорная вероятность k-го класса при условии, что в результате разделения текстов этот текст попал во множество Ay, то есть его j-й признак оказался меньше порога hj), равна P1jk = N1jk / Ny. Аналогично имеем N2jk, A2j, ^^ N2jk = N2j . Вероятность того, что наугад взятый текст из множества A 2j будет текстом k-го класса (эмпирическая апостериорная вероятность k-го класса при условии, что в результате разделения текстов этот текст попал во множество A2j, то есть его j-й признак оказался не меньше порога hj), равна P2jk = N2jk / N2j. Очевидно, Ny + N2j = N. Вероятность попадания наугад взятого текста во множество A1 (то есть эмпирическая вероятность того, что j-й признак текста окажется меньше порога hj), равна Py = N1j / N. Аналогично вероятность попадания текста во множество A2j (то есть эмпирическая вероятность того, что J-й признак наугад взятого текста окажется не меньше порога hj), равна P2j = N2j / N = 1 - Py . Следовательно, средняя энтропия множества классов при условии, что порог разделения текстов деревом решений по j-му признаку равен hj, называемая «пороговой» энтропией [5] множества классов относительно j-го признака, выражается формулой Н (A I hj) = -р j fp k log2 P jk - P2 j XP, jk log2 P2 jk . (2) k=1 k=1 Информативность разделения текстов по j-му признаку определяется как мера снятой по этому признаку неопределённости множества классов при фиксированном пороге hf. Ij (( I hj) = H(A)-H(A | hj). (3) Очевидно, эта величина зависит от порога hj. Естественно выбрать порог разделения так, чтобы информативность (3) разделения текстов по j-му признаку была максимальной. hj opt = arg max Ij (A 1 hj). (4) hj Оптимальное значение hj opt порога hj разделения текстов по j-му признаку достаточно искать в конечном множестве середин интервалов между соседними значениями V(,y и V(I+1j в упорядоченном в порядке возрастания ряду значений Vj j-го признака всех текстов. hj + v(+1)j V2,' = ( где V(fj - i-я порядковая статистика набора значений { Vj} j-го признака по всем N текстам обучающего множества. Именно такое разделение текстов по относительной частоте употребления служебного слова «через» (соответствует j = 5 в таблице на рис. 1) в текстах нашего примера приведено на рис. 2 (оптимальный порог по этому признаку равен = 0,000539). Из рис. 2 видно, что N15 = 10 текстов из N = 17 попали во множество A15 (3 текста 1-го класса «Гоголь», 3 - 2-го «Гончаров», 2 - 3-го «Достоевский», 1 - 4-го «Куприн», 1 - 5-го «Лермонтов»), а остальные N25 = 7 текстов - во множество A25 (1 текст 3-го класса «Достоевский», 1 - 4-го «Куприн», 2 - 5-го «Лермонтов», 3 - 6-го «Лесков»). Разделение по остальным признакам аналогично. Тем самым пространство признаков разбивается на 2n непересекающихся n-мерных интервалов, порождающих пространственную таблицу стилей текстов. По ячейкам (n-мерным интервалам) этой таблицы распределяются все тексты обучающего множества. В каждый интервал попадает определённое число текстов каждого класса (в какие-то интервалы может не попасть ни одного текста, тогда эти интервалы остаются пустыми). Можно найти долю текстов каждого класса, попавших в область ниже порога и выше порога по каждому признаку. Тогда эту таблицу можно представить двумерной таблицей, строками которой будут классы, а столбцами - признаки. В каждой j-й ячейке этой таблицы можно указать долю текстов i-го класса, попавших в область ниже порога по j-му признаку и в область выше либо на уровень порога по тому же признаку. Если доля текстов i-го класса, попавших по j-му признаку, скажем, выше оптимального порога, составляет величину, большую, например, 60% (доля текстов выше порога существенно больше доли текстов ниже порога), соответствующую ячейку таблицы можно выделить некоторым цветом (например, красным) или пометить некоторым символом (например, 1). Если эта доля составляет величину, меньшую, например, 40% (доля текстов выше порога существенно меньше доли текстов ниже порога), ячейку можно выделить другим цветом (например, зелёным) или пометить другим символом (например, 0). В противном случае (доля текстов выше порога существенно не отличается от доли текстов ниже порога) ячейку можно выделить, например, жёлтым цветом или пометить, например, символом «-» (знак неопределённости классификации). Одновременно в ячейке таблицы можно указать число и долю текстов, попавших ниже порога или выше либо на уровень порога. Такая таблица и образует таблицу профилей стилей текстов. На рис. 3 приведён пример таблицы профилей авторских стилей для таблицы данных рис. 1. Сравнивая между собой строки таблицы рис. 3, можно оценить степень схожести классов. Предъявляя классификатору текст неизвестного класса, получим строку подобной таблицы, сравнивая которую со строками таблицы профилей стилей можно сказать, к какому классу ближе всего исследуемый текст по используемому критерию сравнения. Рис. 3. Таблица профилей стилей текстов В качестве признаков, по которым можно оценивать схожесть классов, могут выступать величины, измеряемые в шкале отношений, например проценты (доли) текстов каждого класса, попавших по каждому исходному признаку (относительной частоте) в область ниже порога. Но можно использовать в качестве признаков схожести, наоборот, доли попадания относительных частот в область не ниже (выше или на уровень) порога. А можно использовать в качестве признаков схожести также величины, измеряемые в номинальной шкале: троичную «цветовую» переменную, принимающую значения «красный», «зелёный», «жёлтый», о чём говорилось выше при описании раскраски таблицы профилей стилей. Или троичную «яркостную» переменную, принимающую значения «тёмно-серый», «серый», «светло-серый». Им может соответствовать переменная троичной логики со значениями «1», «0», «-» («истина», «ложь», «неопределённость»). Геометрический смысл каждой строки (класса), описывающей признаки схожести классов в шкале отношений, заключается в том, что каждому облаку точек-текстов класса в исходном частотном признаковом пространстве ставится в соответствие одна точка в пространстве признаков схожести классов, характеризующая непосредственно стиль класса. Такое представление существенно упрощает задачу сравнения стилей авторов (классов). Так, взяв за координаты точек-стилей (за признаки сравнения) проценты текстов, оказавшихся ниже порога по каждому признаку, и расставив эти точки в пространстве признаков сравнения, можно легко интерпретировать схожесть стилей. две точки достаточно близки друг к другу - стили классов схожи, две точки достаточно удалены друг от друга - стили отличаются. В этом случае в качестве меры близости точек (метрики в пространстве признаков сравнения) можно взять евклидово расстояние между точками. В случае использования в качестве признаков сравнения логических переменных «расстояние» между классами можно определять числом несовпадений значений признаков сравниваемых классов. 4. Дерево кластеризации профилей стилей текстов С использованием шкалы отношений и выбранной меры расстояния между классами можно построить иерархическое дерево кластеризации [7] (здесь уместно использовать кластеризацию «по дальнему соседу») и визуализировать картину близости классов. Так, при евклидовой метрике сравнения классов по процентам попадания текстов в области ниже порога для рассматриваемого примера данных, представленного на рис. 1, получаем горизонтальную древовидную диаграмму кластеризации, показанную на рис. 4. Диаграмма получена из таблицы профилей авторских стилей текстов рис. 3 в программном продукте «СтилеАнализатор». Рис. 4. Горизонтальная древовидная диаграмма кластеризации Сначала каждый класс авторских стилей образует свой кластер (левая часть диаграммы). Горизонтальная ось представляет расстояние объединения кластеров в новые кластеры. Для каждого узла дерева кластеризации (там, где формируется новый кластер) в верхней строке рис. 4 против вертикальных точечных линий можно видеть величину расстояния, на котором соответствующие элементы (предыдущие кластеры) объединяются в новый кластер. Числа, помечающие узлы, нумеруют последовательность образования кластеров. Обратим внимание, что в использованном здесь методе кластеризации (методе полной связи, методе «дальнего соседа») расстояние между кластерами определяется наибольшим расстоянием между двумя объектами из разных кластеров. 5. Логическое сравнение профилей стилей текстов С использованием номинальной шкалы «расстоянием» между классами может служить число несовпадений сравниваемых строк по всем ячейкам значений введённых выше троичных переменных, характеризующих признаки схожести стилей текстов. Так, при сравнении авторских классов по «цветовой» или «яркост-ной» гамме из таблицы рис. 4 получается следующая таблица чисел несовпадения троичных признаков: Таблица 1 Гоголь Гончаров Достоевский Куприн Лермонтов Лесков Гоголь 0 4 6 6 5 5 Гончаров 4 0 4 7 5 7 Достоевский 6 4 0 5 5 5 Куприн 6 7 5 0 7 5 Лермонтов 5 5 5 7 0 6 Лесков 5 7 5 5 6 0 Пусть теперь имеем текст, автор которого исследователю неизвестен и который характеризуется признаками, приведёнными в первых трёх строках следующей таблицы: Таблица 2 Признак в на с о через из-за хотя когда чтобы Абс. част. 1868 992 841 197 38 27 48 147 229 Отн. част. 0.0195 0.0142 0.0090 0.0021 0.0002 0.0003 0.0002 0.0027 0.0010 Профиль 1 1 1 0 0 1 0 1 1 Сравнивая относительные частоты признаков с порогами таблицы рис. 3, получим стилевой профиль этого текста. Запишем его в четвёртую строку табл. 2. Сравнивая эту строку со строками профилей стилей авторских классов таблицы рис. 3, видим, что этот профиль наиболее близок профилю авторского стиля Н.В. Гоголя (просто совпадает с ним: число несовпадений равно нулю). Действительно, предъявленный текст был произведением Н.В. Гоголя «Мёртвые души», том 2. Отбор минимальных наборов признаков (безызбыточных, или тупиковых тестов), достаточных для распознавания классов, может быть проведён на основе методов логического распознавания (например, [8, 9]) по таблице профилей стилей текстов рис. 3. Заключение На основе использования алгоритмов деревьев решений предложен алгоритм построения таблицы профилей стилей текстов, принадлежащих заданным классам (авторским, жанровым и др.). Получаемые при обучении алгоритма профили стилей текстов могут быть использованы для идентификации стиля предъявляемого текста неизвестного автора, что позволяет, в частности, определять наиболее вероятное авторство текста.

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