Диссертация (1149537), страница 5
Текст из файла (страница 5)
В 1967 году Лансом и Уильямсом [94]была предложена универсальная формула определения расстояния отнового кластера W до любого кластера S:D(U ∪ V, S) = αU D(U, S) + αV D(V, S) + βD(U, V ) + γ|D(U, S) − D(V, S)|,где αU , αV , β, γ ∈ R — параметры.Наиболее распространены следующие три метода объединения кластеров в агломеративном подходе:1. Метод одиночной связи (англ. single linkage)Dsl (W, S) = min ρ(w, s),w∈W,s∈S11αU = αV = , β = 0, γ = − .222. Метод полной связи (англ. complete linkage)Dcl (W, S) = max ρ(w, s),w∈W,s∈S11αU = αV = , β = 0, γ = .223. Метод средней связи (англ. group-average linkage)Dgal (W, S) = max ρ(w, s),w∈W,s∈S28αU =|U ||V |αV =, β = γ = 0.|W ||W |1.4.2Алгоритм k-среднихАлгоритм k-средних является одним из самых популярных методовкластеризации с заданным количеством кластеров.
Принцип алгоритмаосновывается на поиске представителей кластеров (называемых центроидами), по одному для каждого кластера, и выборе разбиения на основе того, как кластеры рассеиваются вокруг этих точек. Таким образомкластеризация k-средних ищет разбиение, которое минимизирует функционал (1.5).Приближенное решение этой задачи формулируется в виде следующего алгоритма:Алгоритм 1 k-среднихВход:Z — множествоk — количество кластеровTb k — начальное разбиение (необязательно)Процедура:1: Инициализация: Если начальное разбиение не задано, то сформировать начальное разбиение (обычно точки случайным образом относятся к кластерам).2: Минимизация: Вычислить среднее (центроиду) точек каждого кластера.3: Классификация: Отнести каждый элемент к текущей ближайшейцентроиде.4: Повторить 2-3 пока разбиение не стабилизируется, то есть центроидыперестанут изменяться.Доказательство сходимости алгоритма кластеризации алгоритма kсредних требует проверки следующих двух утверждений:• Переопределение точки к другому кластеру не увеличивает функцию ошибки.• Пересчет центроида кластера не увеличивает функцию ошибки.На практике элементы множества Z подаются на вход системе постепенно: z 1 , z 2 , .
. .. В этой связи итеративные алгоритмы, когда центроиды29пересчитываются одновременно с поступлением новых данных, гораздоболее предпочтительны. Рандомизированный итеративный алгоритм kсредних был предложен в [4].1.4.3Тематическое моделированиеЗадача тематического моделирования заключается в построении вероятностной порождающей модели корпуса текстовых документов.
Врамках модели документы представляются как смеси тем, где тема —это вероятностное распределение слов.Самые известные тематические модели — вероятностный латентносемантический анализ (англ. Probabilistic Latent Semantic Analysis, PLSA)[70] и латентное размещение Дирихле (англ. Latent Dirichlet Allocation,LDA) [25]. Недостатком модели PLSA является невозможность вычислить вероятность документа, которого нет в коллекции текстовых документов. В [25] эта проблема была устранена введением априорного распределения Дирихле для тем в документах.
Рассмотрим в этом разделемодель LDA.Пусть D = {d1 , . . . , d|D| } – коллекция документов и V = {w1 , . . . , w|V | }– словарь коллекции. Тема zj , 1 6 j 6 K представляет собой мультиP|V |номиальное распределение |V | слов, p(wi |zj ), i p(wi |zj ) = 1. МодельLDA генерирует слова в два этапа: слова генерируются из тем, а темыиз документов. Таким образом распределение слов в документе можновычислить как:KXp(wi |zj )p(zj |d)p(wi |d) =j=1LDA предполагает следующий генеративный процесс для коллекциидокументов D:1. Случайно выбрать для документа его распределение по темам θ ∼Dir(α).2.
Для каждого слова в документе:30• Случайно выбрать тему из распределения θd , полученного на1-м шаге.• Случайно выбрать слово из распределения в выбранной темеzi .Совместное распределение модели (скрытых и наблюдаемых переменных) равняетсяP (φ1:K , θ1:D , z1:D , w1:D ) =KYP (φj |β)j=1×|D|YP (θd |α)×d=1NY!P (zd,n |θd )P (wd,n |φ1:K , ad,n ) .n=1Далее для оценивания параметров необходимо вычислить апостериорное распределение скрытых переменных при условии наблюдаемых документов:P (φ1:K , θ1:D , z1:D |w1:D ) =P (φ1:K , θ1:D , z1:D , w1:D ).P (w1:D )Знаменатель дроби представляет собой вероятность наблюдать w привсех возможных параметрах модели и равняется сумме вероятностей совместного распределения по всем значениям скрытых переменных.
Числовсех возможных отнесений слов w к темам z растет экспоненциально сростом длины документа. Поэтому на практике используют приближенные методы вывода апостериорной вероятности, например, вариационный вывод [25] или сэмплирование по Гиббсу [63].Сэмплирование по Гиббсу вычисляет апостериорную вероятность длякаждого слова следующим образом:(d)P (zi = k|wi = w, z−i , w−i , α, β) = PKnk,−i + αk 0 =1(d)nk0 ,−i + Kα(k)× PWnw,−i + βw0 =1(k),nw,−i + W βгде zi = k — назначение слова i теме k, z−i — назначение всех остальных31(k)слов к темам, nw,−i – количество раз, когда слово w было отнесено к теме(d)k за исключением текущего отнесения.
Аналогично, nk,−i – количествораз, когда тема k была отнесена к любому слову из документа d за исключением текущего отнесения. Теоретический обзор сэмплирования поГиббсу представлен в [34], [62].LDA часто используется как элемент более сложных моделей. В [37]авторы использовали LDA совместно с иерархией понятий для моделирования документов.1.51.5.1Меры сходства и различияОпределение мер сходства и различия иих свойстваПонятия сходства и различия широко используются в сфере искусственного интеллекта.
Среди множества областей применения – интеллектуальный анализ данных, извлечение информации, распознавание образов, биоинформатика и нечеткая логика [23]. В широком смысле сходство и различие выражают результат сравнения двух объектов. Несмотря на интуитивность этих понятий, в литературе существует несколькоспособов их формализации.Рассмотрим X — множество. Функция расстояния d : X × X → Rудовлетворяет следующим свойствам [141]:1.
d(x, x) = 0 (тождественность.2. d(x, y) > 0 (неотрицательность).3. d(x, y) = d(y, x) (симметричность).4. d(x, y) = 0 =⇒ x = y. (определенность)5. d(x, y) + d(y, z) > d(x, z) (неравенство треугольника)32Если функция обладает только свойствами (1) и (2), то она называетсяфункцией расстояния или функцией различия. Если функция различияудовлетворяет свойствам (1)–(3) и (5), то она называется полуметрикой,а если всем пяти свойствам, то метрикой.
Пространство (X , d) называется пространством, снабженным полуметрикой, если d – полуметрикаили метрическим пространством, если d – метрика. Принято формировать матрицу D := (d(xi , xj )i,j−1,...,n ) из расстояний между объектамиx1 , . . . , x n ∈ X .В контексте функций сходства рассмотрим следующие свойства [23]:1.
s(x, x) > 0.2. s(x, y) = s(y, x) (симметричность).3. s(x, x) > 0 (неотрицательность).Любую функцию, удовлетворяющую свойству (1) будем называть функцией сходства. Свойство (3) может выполняться не для всех функцийсходства, например, оно не выполняется для коэффициентов корреляции или скалярного умножения.Алгоритмы машинного обучения обычно используют либо функциисходства, либо функции различия.
В общем случае выбор функции зависит от типа исследуемых данных, но может быть необходимо преобразовать функцию сходства в функцию различия и наоборот. Ниже представлено несколько способов такого преобразования.• Если функция сходства является скалярным произведением в евклидовом пространстве, соответствующую функцию расстояния можно получить следующим образом:d(x, y)2 = hx − y, x − yi = hx, xi − 2hx, yi + hy, yi.• Предположим, функция сходства нормирована, то есть 0 6 s(x, y) 61 и s(x, x) = 1 для любых x, y ∈ X .
Тогда d := 1 − s – функциярасстояния.33• Для евклидовой функции расстояния соответствующая функциясходства может быть вычислена следующим образом:1s(x, y) := (d(x, 0)2 + d(y, 0)2 − d(x, y)),2где 0 — некоторая произвольная точка в X , играющая роль началакоординат.• Если d — функция различия, то неотрицательная убывающая функция от d будет являться функцией сходства.
Например, s(x, y) =1exp(−d(x, y)2 /t) при некотором параметре t или s(x, y) = 1−d(x,y)Далее приведены примеры наиболее известных функций расстояния(различия) и сходства. Пусть xi , xj ∈ X , P > 0, |X | = N . Обозначениеxik означает k-й элемент xi .• Евклидово расстояние:vu PuXdEuclidean (xi , xj ) :=t (xik − xjk )2 .k=1• Взвешенное евклидово расстояниеvu PuXdW Euclidean (xi , xj ) :=tWk (xik − xjk )2 ,k=1где Wk обозначает вес k-го элемента вектора.• Манхэттенское расстояние, расстояние городских кварталовdM anhattan (xi , xj ) :=PXk=134|xik − xjk |.• Расстояние ЧебышёваdChebyshev := max(|xi1 − xj1 |, .
. . , |xiP − xjP |).• Расстояние МинковскогоPXdM inkowski (xi , xj ) :=! 1l|xik − xjk |l,k=1где l > 1.• Расстояние Махаланобисаvu PuXdM ahalanobis :=t (xi − xj )T Σ−1 (xi − xj ),k=1где Σ – матрица ковариации размера P × P , ij-й элемент которойравенP1 X(xik − x̄i )(xjk − x¯j ),Σ(i, j) :=N −1k=1N1 Xx̄ =xik .Nk=1• Корреляция СпирменаПусть X = (x1 , . .
. , xN ), Y = (y1 , . . . , yN )dSpearman := 1 −6PN2i=1 (R(xi ) − R(yi )),N (N 2 − 1)где R(xi ), R(yi ) – ранги элементов xi , yi в последовательностях X, Yсоответственно.• Расстояние КанберраdCanberraPX|xik − xjk |:=.|x|+|x|ikjki=135• Гауссовская ядерная функция сходства (радиальная базисная функция)||xi − xj ||2sGaussian (xi , xj ) := a exp(−),2σ 2где σ — “масштабирующий” параметр.• Гармоническое среднееsHarmonicPXxik xjk:= 2.xik + xjkk=1• Косинусная мера сходстваPPsCosine :=k=1 xik xjk||xi ||||xj ||=hxi , xj i.||xi ||||xj ||• Корреляция ПирсонаPP− x̄i )(xjk − x¯j )||xi − x̄i ||||xj − x¯j ||hxi − x̄i , xj − x¯j i=||xi − x̄i ||||xj − x¯j ||sP earson :=k=1 (xik=SCosine (xi − x̄i , xj − x¯j ).1.5.2Ядерные функции и их свойстваВ последнее время подход, основанный на ядерных функциях, сталраспространенным и популярным методом в машинном обучении. Основной причиной такой популярности стал так называемый “Kernel trick”,впервые предложенный в [2].
Идея заключается в переходе в пространство большей размерности, в котором нелинейная задача легко решаетсялинейными методами. Исходное пространство объектов X вкладываетсяв пространство признаков Fφ : X → F, x → φ(x),36в котором затем вычисляется скалярное произведениеK(x, x0 ) = hφ(x), φ(x0 )i.(1.6)Обычно, ядро K(·, ·) выбирается без какой-либо дополнительной информации об отображении φ, чтобы избежать расчетов в пространствевысокой размерности. Теорема Мерсера [127] утверждает, что любая непрерывная, симметричная, положительно определенная ядерная функцияможет быть представлена скалярным произведением в пространстве высокой размерности.
Успех применения ядерных функций в методе опорных векторов [43] расширил применение этих функций на другие задачимашинного обучения: кластеризации (см. обзор в [55], [128]) и пониженияразмерности [106].Далее приведем определения, свойства и известные результаты о вещественных положительно и отрицательно определенных ядрах.Определение 1.• Симметричная функция K : X × X → R называется положительно определенным ядром, если ∀n ≥ 1 и для любых x, . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
