Диссертация (1149537), страница 9
Текст из файла (страница 9)
Если значение ARI,подсчитанное для исходной коллекции не превышает выбранного порогаCRand , то невозможно предполагать, что тренировочная коллекция является надежной для текущего набора параметров.В рассматриваемой задаче, неинформативные термины появляютсяв меньшинстве отрывков с относительно невысокой частотой. Таким образом, алгоритмы разделения нечувствительны к наличию таких терминов в конкретном отрывке, так как их частота является низкой для всехрассматриваемых отрывков.
Естественно, число таких терминов можетувеличиваться с уменьшением длины фрагмента L. Оценим информативность термина на основе его средней частоте появление во всей коллекции:I(wi ) = average {f (wi , D) , D ∈ D} ,где f (wi , D) — частота появления термина wi в тексте D ∈ D. На следующем шаге только термины из множества(3.1)IW (T ) = {I(wi ) > T r} ,включены в построение векторной модели.
Здесь T r — определенное заранее пороговое значение.Ключевыми параметрами в представленной методологии являютсязадержка T и длина фрагментов L. Задача выбора подходящего наборапараметров является плохо обусловленной, так как разные комбинациипараметров могут приводить к одинаковому поведению системы. Ясно,что большие значения T и L должны приводить к более стабильным результатам. Но, с другой стороны, количество отрывков текстов можетуменьшиться до такой степени, что динамическая модель более не будетотражать динамику стиля и классификатор перестанет быть надежным.В связи с этим, необходимо сохранить баланс между значениями параметров и количеством отрывков при выборе конфигурации параметров.61По аналогии с [29], предлагается искать такие значения параметров,которые обеспечивают правильное разделение коллекций текстов, относящихся к различным стилям.
Это идея воплощена в Алгоритме 6.Рассмотрим две коллекции текстов с разными авторскими стилямиDn1 = {D11 , . . . , D1n1 } , Dn2 = {D21 , . . . , D2n2 }с двумя наборами возможных параметровT = {T1 , . . . , Tm } , L = {L1 , ..., Lk } .Эти наборы параметров могут быть получены из предыдущих экспериментов или согласно общим представлениям. Процедура повторяетсянесколько раз (параметр Iter в алгоритме).Для каждого набора T ∈ T и L ∈ L два текста D1j1 ∈ Dn1 и D2j2 ∈ Dn2выбираются случайным образом, разделяются на отрывки и кластеризуются при помощи Алг.
3, с целью определить индекс ARI между первоначальным и полученным разделением. После завершения итераций,когда среднее значение A0 (T, L) индекса ARI найдено, следующее значение достигается для каждого T ∈ TL∗ (T ) = arg min {A0 (T, L) > CRand }L∈LиT ∗ = arg min {L∗ (T )} .T ∈TЗдесь, CRand — определенный заранее порог. Пара (T ∗ , L∗ (T ∗ )) — выбранная конфигурация.Для определения подходящих значений для параметров использовался Алгоритм 6. В описанном следующие циклы книг использовались какзаведомо различные наборы текстов:• Цикл “Основание” А.Азимова,• Цикл “Рама” А.Кларка62Алгоритм 6 Подбор параметровВход:Две коллекции документов, относящиеся к двум разным стилямDn1 = {D11 , . .
. , D1n1 } и Dn2 = {D21 , . . . , D2n2 }.Процедура:1: Выбрать CRand — уровень значимости для скорректированного индекса Ранда.2:Выбрать T = {T1 , ..., Tm } — множество тестируемых значений T .3:Выбрать L = {L1 , ..., Lk } — множество тестируемых значений L.4:7:Выбрать Iter — количество итераций.for T ∈ T dofor L ∈ L dofor i = 1 : Iter do8:Случайным образом выбрать D1j1 ∈ Dn1 и D2j2 ∈ Dn2 .9:Составить Di = {D1j1 ∈ Dn1 , D2j2 ∈ Dn2 } .5:6:10:Вызвать Алгоритм 3 и получить разбиение Cl2 (Di ).11:Вычислить Ri = ARI (Cl2 (Di )).end for12:15:Вычислить A0 (t, l) = mean(Ri |i = 1, ..., Iter).end forend for16:Для каждого T ∈ T найти13:14:L∗ (T ) = arg min {A0 (T, L) > CRand } .L∈L17:НайтиT ∗ = arg min {L∗ (T )} .T ∈T18:Пара (T ∗ , L∗ (T ∗ )) — выбранная конфигурация системы.63В этих наборах семь и шесть книг соответственно.Каждая книга из первого набора сравнивалась с каждой книгой вдругом наборе (всего 42 сравнения).
Такой подход немного отличаетсяот Алгоритма 6, где сравнивались произвольно выбранные документы.Проверялись три значения для параметра задержки с 10 последовательными значениями для размера отрывка L = {500, 1000, ..., 5000}. НаРис. 3.5 представлены три графика скорректированного индекса Ранда,подсчитанного для выбранных значений T с использованием расстоянияdSpearman .Averaged value of the ARI10.8T=5T=10T=200.60.40.2500100015002000250030003500400045005000LРис. 3.5: Усредненные значения скорректированного индекса Ранда длярасстояния dSpearman .Результаты полученные с помощью расстояния dCanberra очень похожи (см.
Рис. 3.6).Полагая CRand = 0.9 в алгоритме 6, получаем L∗ (T ) = 2500, 2000,1500. Так, T ∗ = 20 и L∗ (T ∗ ) = 2000.Таким образом, в экспериментах использовались следующие параметры:• T = 20,64Averaged value of the ARI10.80.6T=5T=10T=200.40.20500100015002000250030003500400045005000LРис. 3.6: Усредненные значения скорректированного индекса Ранда длярасстояния dCanberra .• L = 2000,• T r = 0.5.Двухступенчатый анализ кластеров — это масштабируемая методология, созданная для обработки больших наборов данных [38].
Общий подход состоит из двух основных шагов (ступеней). В начале, применяетсяразделяющий алгоритм, такой как K-средних, для того, чтобы сформировать небольшие так называемые “пред-кластеры”. Количество кластеров может быть заранее определено или оценено с помощью метода валидации кластеризации. Ожидается, что полученные кластеры достаточноконсистентны, но не слишком малы, поскольку они будут использоваться на следующем шаге как отдельные наблюдения. После, процедураиерархической агломеративной кластеризации последовательно объединяет “пред-кластеры” в однородные группы. Агломеративнная иерархическая процедура начинает с одиночных кластеров и собирает их в группы, пока не будет достигнут критерий остановки.
Ни один элемент неперемещается между кластерами.Далее предложена похожая процедура. На первом шаге, книги из одной серии сравниваются между собой с помощью Алгоритма кластеризации 3 и Правила классификации 2 (см. пункт 2.2.2). Результаты представляются квадратной матрицей, где ’1’ обозначает, что для соответ65ствующей пары книг найдено различие в стилях.
Однако, на этом этапенеобходимо классифицировать похожесть между книгами посредствомобщей связи между стилями. А именно, размещением книг в группы наоснове их похожести или различия со всеми книгами в серии. Для реализации этого создаются кластеры по строкам от полученной двоичнойматрицы классификации, с использованием односвзяного агломеративного иерархического алгоритма (см. п. 1.4.1). Процесс повторяется дотех пор, пока все элементы не будут собраны в один кластер. Результатом работы иерархической процедуры кластеризации является вложенная структура стилей.Полученная дендрограмма является наглядным представлением развития авторского стиля.Цикл “Основание” А.АзимоваНа Таблицах 3.2 и 3.3 представлены результаты сравнения стилей,полученных с помощью расстояний dSpearman и dCanberra .F1F2F3F4F5F6F7F1 F2 F3 F4 F5 F6 F70011111001111111010111110011110001111111011111110Таблица 3.2: Сравнение книг из цикла “Основание” с помощью расстояния dSpearman .На Таблице 3.2 видны следующие кластеры: {F 1, F 2}, {F 3, F 4, F 5},{F 6} и {F 7}.
Первые две строки и первые два столбца (первый кластер)на Таблице 3.2 содержат только ’0’. Блок, соответствующий второму кластеру, состоит из семи ’0’ и только двух ’1’. Шестой и седьмой столбецсостоят только из ’1’, за исключением диагональных элементов. Дендрограмма, представленная на Рис. 3.7 (верхняя часть), подтверждает66F1F2F3F4F5F6F7F1 F2 F3 F4 F5 F6 F70011111001111111000111100111110101011111001111000Таблица 3.3: Сравнение книг из цикла “Основание” с помощью расстояния dCanberra .результат разделения.distance1.510.501234567567book numberdistance2101234book numberРис.
3.7: Дендрограмма иерархии книг из цикла “Основание”.Как можно увидеть из Таблицы 3.3 и Рис. 3.7 (нижняя часть), разделение по расстоянию dCanberra немного другое. Второй кластер содержит{F 3} и {F 4} и “Второе Основание” было отнесено к {F 5, F 6, F 7}. Такойрезультат может быть следствием того, что A.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
