Диссертация (1149537), страница 6
Текст из файла (страница 6)
, xn ∈X , c1 , . . . , cn ∈ R выполненоnXci cj K(xi , xj ) > 0.i,j=1• Симметричная функция N : X ×X → R называется отрицательно определенным ядром, если ∀n ≥ 1 и для любых x, . . . , xn ∈ XвыполненоnXci cj N (xi , xj ) 6 0i,j=1для c1 , . . . , cn ∈ R таких, чтоPni=1 ci= 0.Связь между положительно определенным и отрицательно определенным ядром выражается в следующих свойствах:37• Пусть N (x, y) — отрицательно определенное ядро такое, что N (z, z) =0 для некоторого z ∈ X . ТогдаK(x, y) = N (x, z) + N (z, y) − N (x, y).• Если K(x, y) — положительно определенное ядро, то функцияN (x, y) = K(x, x) + K(y, y) − 2K(x, y)является отрицательно определенным ядром, N (x, x) = 0 для любого x ∈ X .Следующие утверждения эквивалентны• K(x, y) = exp(−tN (x, y)) — положительно определенное ядро длялюбого t > 0.• N (x, y) — отрицательно определенное ядро.Один из способов построить признаковое отображение, удовлетворяющее свойству (1.6), основано на следующей теореме.Теорема.
Пусть K(x, y) — положительно определенное ядро. Тогдасуществует единственное гильбертово пространство H вещественнозначных функций на X такое, что• ky (·) = K(·, y) ∈ H для любого y ∈ X ,• для любого y ∈ X и f ∈ H выполненоhf, ky (·)i = f (y).На основе этой теоремы признаковое отображение можно построитьследующим образомφ : X → H,38x → kx (·).В частности, по определению скалярного произведенияhkx (·), ky (·)i = K(x, y)для любых x, y ∈ X .
Таким образом положительно определенные ядраоказываются нелинейным обобщением функции схожести, порожденнойскалярным произведением. Пространство H известно как воспроизводящее ядерное гильбертово пространство (англ. Reproducing Kernel HilbertSpace).Теорема ( [19]). Пусть N (x, y) отрицательно определенное ядро, такое, что N (x, x) = 0 для любого x ∈ X . Тогда существует гильбертово пространство вещественнозначных функций на X и отображениеφ : X → H такое, что||φ(x) − φ(y)||2 = N (x, y).Теорема ( [127]).
Сепарабельное метрическое пространство (X , ρ) может быть изометрически вложено в гильбертово пространство Hтогда и только тогда, когда ρ2 — отрицательно определенное ядро.39Глава 2Динамическая модельтекстовых документовВ этой главе предложен один из возможных методов построения динамической модели текста. На основе предложенной динамической модели были разработаны и обоснованы два метода классификации документов и их фрагментов. Первый метод основан на кластеризации периодограмм, второй использует кластеризацию с помощью расстояния,основанного на некоторых ядрах. Сформулированы теоремы об однозначности и корректности построенных процедур классификации.2.1Динамическая модель текстовыхдокументовПусть {Xi }ni=1 — множество текстовых документов.
Под текстовымдокументом будет понимать упорядоченное множество символов.∀i = 1, . . . , n разделим документ Xi на mi последовательных фрагментов:(2.1)iXi = x1i + . . . + xmi ,где “+” — операция конкатенации строк. Рассмотрим множество всехфрагментов X = {xji }i∈1..n,j∈1..mi .40Введем отображение V , которое сопоставляет фрагменту xji ∈ Xнекоторое вероятностное распределение P ∈ PM из множества вероятностных распределений на {1, . .
. , M }:V : X → PM ,P ∈ PM :P={pi }Mi=1 ,pi ≥ 0,MXpi = 1.i=1Таким образом(2.2)xji = V (xji ) ∈ RM .Обозначим 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 определена некотораяфункция похожести двух фрагментов (см. п. 1.5.1)(2.3)r : RM × RM → R.Пусть T > 0. Для i ∈ 1..n, j > T , xji ∈ X обозначим через ∆xj множеij−Tство предшествующих ему векторов-фрагментов: ∆xj = {xi , . . . , xj−1i }.iКаждая последовательность векторов-фрагментов ∆x с помощью опи-41санной выше функции (2.3) порождает функцию sx (·) : RM → R:(2.4)1 Xr(x0 , y),sx (y) =T 0x ∈∆xкоторую будем называть динамической моделью.Значения функции sx (y) соответствуют средней похожести векторафрагмента y с каждым из векторов-фрагментов из ∆x .Таким образом, введено отображение(2.5)2.22.2.1ψ : xji → sx (·).Паттерны динамической моделиКластеризация спектральных представленийКаждый документ из множества {Xi }ni=1 разделим на одинаковое количество последовательных фрагментов m̄.
Для каждого фрагмента получим его векторное представление согласно (2.2). Сопоставим документу последовательность векторов-фрагментов:(2.6)Xi 7→ {xji }j∈1..m̄ .Пусть T > 0. Для j > T , для каждого xji ∈ {xji }j∈T +1..m̄ построимдинамическую модель sxj (·). Рассмотрим последовательность выходовiдинамической модели:(2.7){xji }j∈T +1..m̄ 7→ {sxj (xji )}j∈T +1..m̄ .iПоследовательность (2.7) представляет собой временной ряд, соответствующий i-му документу.Введем следующие обозначения:• sji = sxj (xji ), j ∈ T + 1..m̄, i ∈ 1..n — средняя мера похожестиiфрагмента xji и предшествующих ему фрагментов.42• Si = {sji }i∈1..n,j∈T +1..m̄ — последовательность средних мер похожести, временной ряд.• S = {Si }i∈1..n — множество последовательностей – временных рядов, соответствующих разным документам коллекции.Периодограммой называется оценка спектральной плотности мощности сигнала, ее вычисление основано на подсчете коэффициентов преобразования Фурье с последующим усреднением [14].Предположим сигнал v(t) измерен в N точках:v = {vn , n = 0, 1, ..., N − 1}с интервалом ∆.
Для простоты положим N — четкое число. Дискретноепреобразование Фурье v выражается какN−1X2πinkVk (x) =vn wn expNn=0(2.8)где i =частотах√, k = 0, ..., N − 1,−1, и wn — функция окна. Периодограмма задана вN2+1kkN= 2fc , k = 0, ..., ,N∆N2где fc — частота Найквиста, следующим образом:fk =|V0 (v)|2 .221• Pv (k) = Pv (fk ) = W 2 |Vk (v)| + |VN −k (v)| , k = 1, ...,• Pv (0) = Pv (f0 ) =•Pv ( N2 )1W2= Px (f N ) =21W22V N2 (x) .дляW =NN−1Xn=043wn2 .N2−1 .Для каждого временного ряда Si вычислим его периодограмму.(2.9)Si 7→ PG(Si ).Обозначим F = {PG(Si )}i∈1..n — множество всех периодограмм документов.
Заметим, ∀f ∈ F f ∈ Rm̄ , будем называть F — пространствомкоэффициентов Фурье.Будем кластеризовать элементы множества помощью алгоритма кластеризации Cl, минимизирующего функционал (1.5) из п.1.4.Количество кластеров определяется значением индекса алгоритма валидации кластеризации (см., например, [30], [51], [53], [59], [69], [74], [91],[107], [137]).Алгоритм 2Вход:X — множество текстовT — параметр задержкиk ? — максимальное количество кластеровCl — алгоритм кластеризацииCLV — индекс алгоритма валидации кластеризацииПроцедура:1: Преобразовать документ Xi ∈ X во временной ряд Si последовательно применив (2.6) и (2.7).2: Для каждого временного ряда вычислить периодограмму PG(Si ).∗3: for k = 2 to k do4:T = Cl({PG(Si )}i∈1..n , k);5:indk = CLV (T );6: end for7: Количество кластеров соответствует оптимальному числу кластеров,согласно значению индекса indk {k = 2, .., k ∗ }.Пусть в результате работы Алгоритма 2 периодограммы документовразделились на k кластеров L1 , .
. . , Lk . Тогда в пространстве временныхрядов можно определить следующее правило классификации, относящеедокумент к одному из классов l1 , . . . , lk :44Правило классификации 1Два документа Xi и Xj относятся к одному классу lk , если соответствующие им периодограммы PG(Si ) и PG(Sj ) попали в один кластер k.Теорема 1. Кластеризация в пространстве F обеспечивает однозначность и корректность правила классификации.Доказательство.
По равенству Парсеваля [9] расстояния в S — пространстве последовательностей (временных рядов) и в пространстве коэффициентов преобразования Фурье F сохраняются. Следовательно, имеем взаимно-однозначное соответствие между кластерами в S, пространстве последовательностей (временных рядов), и в пространстве периодограмм F.
Это обуславливает корректность построенной процедуры классификации.2.2.2Кластеризация по расстояниям, основанным наядрахКаждый документ из множества {Xi }ni=1 разделим на последовательные фрагменты одинаковой длины. Аналогично п.2.2.1 для каждого фрагмента получим его векторное представление согласно (2.2). Сопоставимдокументу последовательность векторов-фрагментов:Xi 7→ {xji }j∈1..mi .Пусть T > 0, X = {xji }i∈1..n,j∈T +1..m̄ — множество векторов-фрагментов,для которых j > T , m̄ = m1 + .
. . + mn .По формуле (2.4) ∀xji построим динамическую модель:xji 7→ sxj (·).i45Для строгого теоретического обоснования дальнейших выкладок предположим выполнение следующего условия для sx (·):Предположение 1sx (y) ≤ sx (x) ∀y ∈ X.То есть каждый вектор-фрагмент наиболее тесно связан только со своими T предшественниками.Введем функцию D : RM × RM → R(2.10)D(x, y) = sx (x) + sy (y) − sx (y) − sy (x).Произведем вложение пространства (X, D(x, y)) в пространство Rm ,где m = m1 + . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
