Графическиеалгоритмыкластеризации Этот класс алгоритмов основан на представлении объектов выборки в виде графа, где рёбрам соответствуют расстояния между объектами. Их достоинствами являются наглядность и простота реализации.
Алгоритмвыделениясвязныхкомпонент Суть алгоритмавыделениясвязныхкомпонент (connected- component labeling) состоит в подборе такого значение параметра 𝑅, что при удалении всех рёбер (i, j) таких, что 𝜌{ij} > 𝑅, граф распадается на несколько связных компонент. Вершины каждой компоненты связаны хотя бы одним путем, проходящим по ребрам. Эти компоненты и будут иско- мыми кластерами.
Алгоритмкратчайшегонезамкнутогопути В случае алгоритмакратчайшегонезамкнутогопути (minimumspanning tree, MST algorithm) должен быть задан параметр 𝐾 — количест- во кластеров. На объектах из X𝑙 строится кратчайший путь, проходящий по всем вершинам, затем удаляются 𝐾 − 1 рёбер, так что в графе остается
𝐾 связных компонент.
Статистические алгоритмы предполагают, что данный класс содержит тот или иной объект с определенной вероятностью, то есть класс рассмат- ривается как случайная величина, которая имеет некоторое распределение на множестве объектов. Задача кластеризации тогда эквивалентна стати- стической задаче разделения смеси распределений.
Для разделения смеси чаще всего используется EM-алгоритм (Expectation-maximization algorithm) — он работает быстрее стандартных методов кластеризации на данных большого объема. EM-алгоритм берет случайные параметры соответствующих распределений и улучшает их, приближая к более правдоподобным. Необходимо повторить этот алго- ритм несколько раз — на каждом шаге параметры будут приближаться к более правдоподобным. После некоторого количества повторений функ- ция правдоподобия максимизируется.
На первом этапе (expectation) рассчитываются апостериорные рас- пределения при фиксированных параметрах, а на втором этапе (maximization) параметры пересчитываются так, чтобы им отвечала мак- симальная функция правдоподобия. Затем, после обновления параметров, опять пересчитываются апостериорные распределения; этот цикл шагов E и M производится до тех пор, пока корректировка распределения не ста- нет незначительной.
