Неконтролируемая кластеризация: определение в процессе обучения смешанных гауссовых распределений
Неконтролируемой кластеризацией называется задача выделения многочисленных категорий в коллекции объектов. Эта проблема — неконтролируемая, поскольку категориям не назначены метки. Например, предположим, что регистрируются спектры сотен тысяч звезд; звезды подразделяются на типы, которые можно определить по спектру, а если так оно и есть, то сколько таких типов и каковы их характеристики? Мы все знакомы с терминами наподобие "красный гигант" и "белый карлик", но звезды не носят эти надписи на своих шляпах, поэтому астрономы должны выполнять неконтролируемую кластеризацию для выявления их категорий. К другим примерам относится выявление видов, родов, отрядов и других категорий в таксономии живых организмов, установленной Линнеем, а также создание естественных разновидностей для распределения по категориям обычных объектов (см. главу 10).
Неконтролируемая кластеризация начинается с данных. На рис. 20.8, а показано 500 точек данных, каждая из которых задает значения двух непрерывных атрибутов. Точки данных могут соответствовать звездам, а атрибуты — интенсивностям спектра на двух определенных частотах. Затем необходимо понять, какого рода распределение вероятностей могло быть сформировано этими данными. Сама возможность кластеризации равносильна предположению, что данные сформированы с помощью смешанного распределения Р. Такое распределение имеет к компонентов, каждый из которых представляет собой отдельное распределение. Точка данных формируется путем первоначального выбора компонента, а затем формирования выборки из этого компонента. Допустим, что этот компонент определяет случайная переменная С со значениями 1,..., к; в таком случае смешанное распределение задается следующим выражением:
Р(х) = Tp(C=i) P(x\C=i) i = l
где х относится к значениям атрибутов для точки данных. В случае непрерывных данных естественным вариантом выбора для распределений компонентов является многомерное гауссово распределение, что приводит к созданию семейства распределений, представляющего собой так называемое смешанное гауссово распределение. Параметрами смешанного гауссова распределения являются Wi-P(C=i) (вес каждого компонента), jii (математическое ожидание каждого компонента) и Si (ковариация каждого компонента). На рис. 20.8, б показано смешанное гауссово распределение, состоящее из трех распределений; фактически это смешанное распределение было источником данных, приведенных на рис. 20.8, а.
Таким образом, задача неконтролируемой кластеризации состоит в восстановлении модели смешанного распределения, подобной приведенной на рис. 20.8, б, из исходных данных, таких как показано на рис. 20.8, а. Очевидно, что если бы мы знали, с помощью какого компонента сформирована каждая точка данных, то было бы легко восстановить гауссово распределение для этого компонента, поскольку можно было просто выбрать все точки данных, соответствующие такому компоненту, а затем применить уравнение 20.4 (вернее, его многомерную версию) для согласования параметров гауссова распределения с множеством данных. С другой стороны, если бы были известны параметры каждого компонента, то можно было бы, по меньшей мере в вероятностном смысле, присвоить каждую точку данных компоненту. Но проблема состоит в том, что не известны ни присваивания, ни параметры.
Основная идея алгоритма ЕМ, рассматриваемого в данном контексте, состоит в том, что необходимо принять допущение, будто нам известны параметры этой модели, а затем вычислить вероятность того, что каждая точка данных принадлежит к тому или иному компоненту. После этого нужно снова согласовать компоненты сданными таким образом, чтобы каждый компонент согласовывался со всем набором данных, каждой точке которого назначен вес, соответствующий вероятности того, что она принадлежит к данному компоненту. Такой процесс продолжается итерационно до достижения сходимости. По сути при этом происходит "дополнение" данных путем вычисления распределений вероятностей по скрытым переменным (определяющим, какому компоненту принадлежит каждая точка данных) на основании текущей модели. При использовании смешанного гауссова распределения модель смешанного распределения инициализируется произвольными значениями параметров, а затем осуществляются итерации по описанным ниже двум шагам.
1. Е-шаг. Вычислить вероятности рц = Р{ C=i | Xj) того, что данные Xj были сформированы компонентом i. Согласно правилу Байеса, справедливо соотношение Pij=aP(Xj | C=i) P{C=i). Терм P(XJ | C=i) представляет собой вероятность значений данных Xj в i-м гауссовом распределении, а терм Р (Oi) — это параметр определения веса i-ro гауссова распределения; по определению Pi=Јj Pij.
2. М-шаг. Вычислить новые значения математического ожидания, ковариации и весов компонента следующим образом:
Е-шаг, или шаг ожидания (expectation), может рассматриваться как вычисление ожидаемых значений p±j скрытых индикаторных переменных Zij? где значение Zi6 равно 1, если данные Xj были сформированы i-м компонентом, и 0 — в противном случае. В М-шаге, или шаге максимизации (maximization), осуществляется поиск новых значений параметров, которые максимизируют логарифмическое правдоподобие данных с учетом ожидаемых значений скрытых индикаторных переменных.
Окончательная модель, параметры которой определены в процессе обучения с помощью алгоритма ЕМ, применяемого к данным, приведенным на рис. 20.8, я, показана на рис. 20.8, в; она практически не отличается от первоначальной модели, на основе которой были сформированы данные. На рис. 20.9, а показан график изменения логарифмического правдоподобия данных, соответствующих текущей модели, которое изменяется в процессе выполнения алгоритма ЕМ. На этом графике заслуживают внимания две особенности. Во-первых, логарифмическое правдоподобие модели, окончательно полученной в процессе обучения, немного превышает соответствующее значение для первоначальной модели, на основании которой были сформированы исходные данные. Это явление может на первый взгляд показаться удивительным, но оно просто отражает тот факт, что данные были сформированы случайным образом, поэтому существует вероятность того, что они не являются точным отражением самой базовой модели. Во-вторых, любопытно то, что Ж9 в алгоритме ЕМ логарифмическое правдоподобие данных повышается после каждой итерации. Можно доказать, что такова общая особенность данного алгоритма. Кроме того, можно доказать, что при определенных условиях алгоритм ЕМ достигает локального максимума правдоподобия (а в редких случаях он может достичь точки перегиба или даже локального минимума). В этом смысле алгоритм ЕМ напоминает алгоритм восхождения к вершине с учетом градиента, но заслуживает внимания то, что в нем уже не применяется параметр со "ступенчатым изменением величины"!
Но события не всегда развиваются так удачно, как можно было бы судить на основании рис. 20.9, а. Например, может случиться так, что один компонент гауссова распределения сузится настолько, что будет охватывать лишь единственную точку данных. В таком случае его дисперсия достигнет нуля, а правдоподобие увеличится до бесконечности! Еще одна проблема состоит в том, что может произойти "слияние" двух компонентов, в результате чего они примут одинаковые значения средних и дисперсий, а точки данных станут для них общими. Вырожденные локальные максимумы такого рода представляют собой серьезную проблему, особенно в случае большого количества измерений. Одно из решений состоит в наложении распределений априорных вероятностей на параметры модели и применении версии MAP алгоритма ЕМ. Еще одно решение состоит в перезапуске вычислений для некоторого компонента с новыми случайно выбранными параметрами, если он становится слишком малым или слишком близким к другому компоненту. Иногда имеет также смысл выбирать для инициализации параметров более обоснованные значения.