Автореферат (1149535), страница 2
Текст из файла (страница 2)
, k.Такая формализация имеет простую геометрическую интерпретацию. Пусть распределение P (·) равномерно на Z и пусть функции qi (ci , z) = ||zi − z||2 , i =Z1, . . . , k||ci −представляют расстояние до центров кластеров c1 , c2 , . . . , ck . ИнтегралCiz||2 dz определяет разброс точек z множества Ci . Функционал (4) принимает видF (C) =l ZXi=1||ci − z||2 dz → min .CCi(5)Таким образом, задача кластеризации свелась к задаче нахождения такого множества центров {c∗1 , . .
. , c∗k }, для которых общий разброс точек минимален.В п. 1.5 даны определения мер сходства и различия, приведены примеры широкоиспользуемых функций расстояния и схожести. Пусть xi , xj ∈ X , P > 0, |X | = N .Обозначение xik означает k-й элемент xi .В численных экспериментах в работе были использованы следующие функциирасстояния:P26 Ni=1 (R(xi ) − R(yi )), где R(xi ), R(yi )• Корреляция Спирмена: dSpearman := 1−N (N 2 − 1)– ранги элементов xi , yi в последовательностях X = {x1 , . . . , xN } и Y ={y1 , . . . , yN } соответственно.• Расстояние Канберра: dCanberraPX|xik − xjk |:=.|xik | + |xjk |i=1Во второй главе “Динамическая модель процесса эволюции текстовых документов” предложен один из возможных методов построения динамической модели текста.
На основе предложенной динамической модели были разработаны и обоснованы два метода классификации документов и их фрагментов. Первый метод основан на кластеризации периодограмм, второй использует кластеризацию с помощьюрасстояния, основанного на некоторых ядрах. Сформулированы теоремы об однозначности и корректности построенных процедур классификации.В п. 2.1 описывается метод построения динамической модели текстовых документов, исследованы свойства модели.Пусть {Xi }ni=1 — множество текстовых документов. Под текстовым документомбудет понимать упорядоченное множество символов.8∀i = 1, .
. . , n разделим документ Xi на mi последовательных фрагментов:iXi = x1i + . . . + xmi ,(6)где “+” — операция конкатенации строк. Рассмотрим множество всех фрагментовX = {xji }i∈1..n,j∈1..mi .Введем отображение V , которое сопоставляет фрагменту xji ∈ X некоторое вероятностное распределение P ∈ PM из множества вероятностных распределенийна {1, .
. . , M }:V : X → PM ,P ∈ PM :P ={pi }Mi=1 ,pi ≥ 0,MXpi = 1.i=1Таким образомxji = V (xji ) ∈ RM .(7)Обозначим X = {xji }i∈1..n,j∈1..mi — множество всех фрагментов в векторном представлении.Значение параметра M определяется выбранной векторной моделью. Примеры распространенных векторных моделей приведены в п. 1.2.2 диссертации. ПустьV = {v1 , . . . , vA } — множество всех термов в коллекции документов, называемоесловарем.
В случае модели “мешка слов” M = |V|, текст представляется в виде распределения частот появления в нем всех термов из словаря. Модель ключевых словявляется частным случаем предыдущей, текст представляется распределением частот появления слов из некоторого подмножества V 0 ⊂ V, таким образом M = |V 0 |.В модели N -грамм, строится словарь всех N -грамм VN , встречающихся в документах из множества документов, в этом случае M = |VN |.Будем считать, что на множестве RM × RM определена некоторая функция похожести двух фрагментов:r : RM × RM → R.(8)Пусть T > 0. Для i ∈ 1..n, j > T , xji ∈ X обозначим через ∆xj множествоij−1предшествующих ему векторов-фрагментов: ∆xj = {xj−T,...,x}.iiiКаждая последовательность векторов-фрагментов ∆x с помощью описанной вы-9ше функции (8) порождает функцию sx (·) : RM → R:sx (y) =1 Xr(x0 , y),T x0 ∈∆(9)xкоторую будем называть динамической моделью.Значения функции sx (y) соответствуют средней похожести вектора-фрагментаy с каждым из векторов-фрагментов из ∆x .Таким образом, введено отображениеψ : xji → sx (·).(10)В п.
2.2.1 сформулирован алгоритм кластеризации с помощью спектральногопредставления и правило классификации на его основе. Сформулирована теоремао корректности описанной ниже процедуры.Каждый документ из множества {Xi }ni=1 разделим на одинаковое количествопоследовательных фрагментов m̄. Для каждого фрагмента получим его векторноепредставление согласно (7). Сопоставим документу последовательность векторовфрагментов:Xi 7→ {xji }j∈1..m̄ .(11)Пусть T > 0. Для j > T , для каждого xji ∈ {xji }j∈T +1..m̄ построим динамическуюмодель sxj (·). Рассмотрим последовательность выходов динамической модели:i{xji }j∈T +1..m̄ 7→ {sxj (xji )}j∈T +1..m̄ .i(12)Последовательность (12) представляет собой временной ряд, соответствующий i-мудокументу.Введем следующие обозначения:• sji = sxj (xji ), j ∈ T + 1..m̄, i ∈ 1..n — средняя мера похожести фрагмента xji иiпредшествующих ему фрагментов.• Si = {sji }i∈1..n,j∈T +1..m̄ — последовательность средних мер похожести, временной ряд.• S = {Si }i∈1..n — множество последовательностей – временных рядов, соответствующих разным документам коллекции.10Периодограммой называется оценка спектральной плотности мощности сигнала, ее вычисление основано на подсчете коэффициентов преобразования Фурье споследующим усреднением.Для каждого временного ряда Si вычислим его периодограмму.Si 7→ PG(Si ).(13)Обозначим F = {PG(Si )}i∈1..n — множество всех периодограмм документов.
Заметим, элементы множества F являются векторами из Rm̄ , будем называть F —пространством коэффициентов Фурье.Будем кластеризовать элементы множества помощью алгоритма кластеризацииCl, минимизирующего функционал (5).Количество кластеров определяется значением индекса алгоритма валидациикластеризации.Описанную процедуру можно сформулировать в виде следующего алгоритма.Алгоритм 1• X — множество текстов• T — параметр задержки• k ? — максимальное количество кластеров• Cl — алгоритм кластеризации• CLV — индекс алгоритма валидации кластеризации1.
Преобразовать документ Xi ∈ X во временной ряд Si последовательно применив (11) и (12).2. Для каждого временного ряда вычислить периодограмму PG(Si ).3. for k = 2 to k ∗ do4. T = Cl({PG(Si )}i∈1..n , k);5. indk = CLV (T );6. end for117. Количество кластеров соответствует оптимальному числу кластеров, согласнозначению индекса indk {k = 2, .., k ∗ }.Пусть в результате работы Алгоритма 1 периодограммы документов разделились на k кластеров L1 , . .
. , Lk . Тогда в пространстве временных рядов можно определить следующее правило классификации, относящее документ к одному из классов l1 , . . . , lk :Правило классификации 1Два документа Xi и Xj относятся к одному классу lk , если соответствующие империодограммы PG(Si ) и PG(Sj ) попали в один кластер k.Теорема 1. Кластеризация в пространстве F обеспечивает однозначность и корректность Правила классификации 1.В п. 2.2.2 сформулирован алгоритм кластеризации по расстояниям, основаннымна ядрах, и правило классификации на его основе. Сформулирована теорема окорректности описанной ниже процедуры.Каждый документ из множества {Xi }ni=1 разделим на последовательные фрагменты одинаковой длины.
Далее для каждого фрагмента получим его векторноепредставление согласно (7). Сопоставим документу последовательность векторовфрагментов:Xi 7→ {xji }j∈1..mi .Пусть T > 0, X = {xji }i∈1..n,j∈T +1..m̄ — множество векторов-фрагментов, длякоторых j > T , m̄ = m1 + . . . + mn .По формуле (9) ∀xji построим динамическую модель:xji 7→ sxj (·).iДля строгого теоретического обоснования дальнейших выкладок предположимвыполнение следующего условия для sx (·):Предположение 1sx (x) ≤ sx (y) ∀y ∈ X.То есть каждый вектор-фрагмент наиболее тесно связан только со своими T предшественниками.12Введем функцию D : RM × RM → RD(x, y) = sx (x) + sy (y) − sx (y) − sy (x).(14)Произведем вложение пространства (X, D(x, y)) в пространство Rm , где m =m1 + .
. . + mn − nT = |X|:F : (X, D(x, y)) → (Rm , k · k)по следующему правилу: каждому вектору-фрагменту xji сопоставим вектор F ∈Rm по следующему правилу:D(xji , xT1 +1 ) D(xji , xT1 +2 ) ...jF (xi ) = 0....jmn−1 D(xi , xn )nD(xji , xmn )(15)Таким образом, ∀j > T, i ∈ 1..n координаты вектора F (xji ) соответствуют расстояниям от вектора-фрагмента xji до всех векторов-фрагментов из множества X.Рассмотрим пример вложения. Пусть X = {xt11 , xt21 , xt31 } и• D(xt11 , xt21 ) = 0.5,• D(xt11 , xt31 ) = 1,• D(xt21 , xt31 ) = 0.2.Тогда соответствующие вектора F равны 00.51 t1t1t1F (x1 ) = 0.5, F (x2 ) = 0 , F (x3 ) = 0.2.10.20Обозначим F = {F (xji }xj ∈X .
Будем кластеризовать элементы множества F сiпомощью алгоритма кластеризации Cl, минимизирующего функционал (5).Описанную процедуру можно сформулировать в виде следующего алгоритма.13Алгоритм 2• X — коллекция текстов• T — параметр задержки• k — число групп1. Построить X = {xji }mj=T +1 .2. Для каждого x построить динамическую модель sx по (9).3. Вычислить F (x) для каждого x по (15).4. Разделить множество F на k кластеров с помощью алгоритма кластеризацииCl.Пусть в результате работы Алгоритма 2 вектора F (x) разделились на k кластеров L1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
