k q -квартиры

В интеллектуальном анализе данных и обучении машинном k q - Flats алгоритм — это итерационный метод, целью которого является разделение m наблюдений на k кластеров, где каждый кластер близок к q -плоскому значению , где q — заданное целое число.

Это обобщение алгоритма k -средних . В алгоритме k -means кластеры формируются таким образом, что каждый кластер близок к одной точке, которая является 0 -плоской. Алгоритм k q - Flats дает лучший результат кластеризации, чем k алгоритм - средних для некоторого набора данных.

Описание

Формулировка задачи

Учитывая набор A из m наблюдений $(a_{1},a_{2},\dots ,a_{m})$ где каждое наблюдение $a_{i}$ представляет собой n-мерный действительный вектор, алгоритм k q -квартир направлен на разделение m точек наблюдения путем создания k q -квартир, которые минимизируют сумму квадратов расстояний каждого наблюдения до ближайшей q -плоскости.

q -бемоль — это подмножество $\mathbb {R} ^{n}$ это соответствует $\mathbb {R} ^{q}$. Например, 0 – флэт – точка; бемоль 1- — линия; - квартира 2 – плоскость; а $n-1$-плоскость – это гиперплоскость . q -плоская может быть охарактеризована множеством решений линейной системы уравнений: $F=\left\{x\mid x\in \mathbb {R} ^{n},W'x=\gamma \right\}$, где $W\in \mathbb {R} ^{n\times (n-q)}$, $\gamma \in \mathbb {R} ^{1\times (n-q)}$.

Обозначим разбиение ​ $\{1,2,\dots ,n\}$ как $S=(S_{1},S_{2},\dots ,S_{k})$. Проблему можно сформулировать как

$$\min _{F_{l},l=1,\dots ,k{\text{ are q-flats}}}\min _{S}\sum _{l=1}^{k}\sum _{a_{j}\in S_{i}}\|a_{j}-P_{F_{i}}(a_{j})\|^{2},$$ ( П1 )

где $P_{F_{i}}(a_{j})$ это проекция $a_{j}$ на $F_{i}$. Обратите внимание, что $\|a_{j}-P_{F_{i}}(a_{j})\|=\operatorname {dist} (a_{j},F_{l})$ это расстояние от $a_{j}$ к $F_{l}$.

Алгоритм

Алгоритм аналогичен алгоритму k-средних (т. е. алгоритму Ллойда) тем, что он попеременно выполняет назначение кластера и обновление кластера. В частности, алгоритм начинается с начального набора q -квартир. $F_{l}^{(0)}=\left\{x\in R^{n}\mid \left(W_{l}^{(0)}\right)'x=\gamma _{l}^{(0)}\right\},l=1,\dots ,k$и продолжает, чередуя следующие два шага:

Назначение кластера

(данные q -плоские, назначьте каждую точку ближайшему q -плоскому): i -й кластер обновляется как $$S_{i}^{(t)}=\left\{a_{j}\mid \left\|(W_{i}^{(t)})'a_{j}-\gamma _{i}^{(t)}\right\|_{F}=\min _{l=1,\dots ,k}\left\|(W_{l}^{(t)})'a_{j}-\gamma _{l}^{(t)}\right\|_{F}\right\}.$$

Обновление кластера

(учитывая назначение кластера, обновите q -плоские значения): Для $l=1,\dots ,k$, позволять $A(l)\in R^{m(l)\times n}$ со строками, соответствующими всем $a_{i}$ отнесен к кластеру l . Набор $W_{l}^{(t+1)}$ быть матрицей, столбцы которой являются ортонормированными собственными векторами, соответствующими $(n-q)$ наименьшие собственные значения $A(l)'\left(I-{\tfrac {ee'}{m}}\right)A(l)$ и $\gamma _{l}^{(t+1)}={\frac {e'A(l)W_{l}^{(t+1)}}{m}}$.

Остановитесь, когда задания больше не меняются.

Шаг назначения кластера использует следующий факт: если задан q -плоский $F_{l}=\{x\mid W'x=\gamma \}$ и вектор a , где $W'W=I$, расстояние от a до q -плоской $F_{l}$ является ${\textstyle \operatorname {dist} (a,F_{l})=\min _{x:W'x=\gamma }\left\|x-a\right\|_{F}^{2}=\left\|W(W'W)^{-1}(W'x-\gamma )\right\|_{F}^{2}=\left\|W'x-\gamma \right\|_{F}^{2}.}$

Ключевой частью этого алгоритма является то, как обновить кластер, т.е. по заданным m точкам, как найти q -плоскую поверхность, которая минимизирует сумму квадратов расстояний каждой точки до q -плоской плоскости. Математически эта задача такова: учитывая $A\in R^{m\times n},$ решить задачу квадратичной оптимизации

$\min _{W\in R^{n\times (n-q)},\gamma \in R^{1\times (n-q)}}\left\|AW-e\gamma \right\|_{F}^{2},$ при условии $W'W=I,$ ( П2 )

где $A\in \mathbb {R} ^{m\times n}$ дано, и $e=(1,\dots ,1)'\in \mathbb {R} ^{m\times 1}$.

Проблему можно решить с помощью метода множителей Лагранжа, и решение указано на этапе обновления кластера.

Можно показать, что алгоритм завершится за конечное число итераций (не более общего числа возможных назначений, ограниченного $k^{m}$). Кроме того, алгоритм завершится в точке, в которой общая цель не может быть уменьшена ни путем другого назначения, ни путем определения новых плоскостей кластера для этих кластеров (такая точка в справочниках называется «локально оптимальной»).

Этот результат сходимости является следствием того, что задача (P2) может быть решена точно. Тот же результат сходимости справедлив и для алгоритма k -средних, поскольку проблема обновления кластера может быть решена точно.

Связь с другими методами машинного обучения

k -средних алгоритм

Алгоритм k q -flats является обобщением алгоритма k -means. Фактически, k алгоритм -средних является алгоритмом k 0 -квартир, поскольку точка является 0-плоской. Несмотря на их связь, их следует использовать в разных сценариях. k q -алгоритм плоских рамок для случая, когда данные лежат в нескольких низкоразмерных пространствах. Алгоритм k -средних желателен для случая, когда кластеры имеют окружающее измерение. Например, если все наблюдения лежат в двух строках, k q - Flats с алгоритм $q=1$ можно использовать; если наблюдения представляют собой два гауссовых облака , k можно использовать алгоритм -средних.

Обучение разреженному словарю

Естественные сигналы лежат в многомерном пространстве. Например, размер изображения размером 1024х1024 составляет около 10 ⁶ , что слишком велико для большинства алгоритмов обработки сигналов. Один из способов избавиться от высокой размерности — найти такой набор базисных функций, при котором многомерный сигнал может быть представлен лишь несколькими базисными функциями. Другими словами, коэффициенты представления сигнала лежат в маломерном пространстве, в котором проще применять алгоритмы обработки сигналов. В литературе вейвлет-преобразование обычно используется при обработке изображений, а преобразование Фурье обычно используется при обработке звука. Набор базисных функций обычно называют словарем .

Однако неясно, какой словарь лучше всего использовать при наличии набора данных сигнала. Один из популярных подходов — найти словарь по набору данных, используя идею разреженного словарного обучения. Его цель — найти словарь, в котором сигнал может быть скудно представлен словарем. Задачу оптимизации можно записать следующим образом.

$\min _{B,R}\|X-BR\|_{F}^{2}$ при условии $\|R_{i}\|_{0}\leq q$

где

• X представляет собой d - N. матрицу Каждый столбец X представляет сигнал, всего имеется N сигналов.
• B является матрицей d - l . Каждый столбец B представляет базисную функцию, всего l базисных функций. в словаре
• R представляет собой l размера на N. матрицу $R_{i}$ ( i -й столбец R ) представляет собой коэффициенты, когда мы используем словарь для представления i -го столбца X. B
• $\|v\|_{0}$ обозначает нулевую норму вектора v .
• $\|V\|_{F}$ обозначает норму Фробениуса матрицы V .

Идея алгоритма k q - Flats по своей природе аналогична изучению разреженного словаря. Если мы ограничим q -плоское до q -мерного подпространства, то алгоритм k q- плоских площадей просто находит замкнутое q -мерное подпространство для данного сигнала. Разреженное обучение словарю делает то же самое, за исключением дополнительных ограничений на разреженность представления. Математически можно показать, что алгоритм k q - Flats представляет собой форму обучения разреженного словаря с дополнительной блочной структурой на R .

Позволять $B_{k}$ быть $d\times q$ матрица, где столбцы $B_{k}$ являются основой k -й квартиры. Тогда проекция сигнала x на k -ю плоскость равна $B_{k}r_{k}$, где $r_{k}$ является q -мерным коэффициентом. Позволять $B=[B_{1},\cdots ,B_{K}]$ обозначают конкатенацию базиса K квартир, легко показать, что k q -плоский алгоритм аналогичен следующему.

$\min _{B,R}\|X-BR\|_{F}^{2}$ при условии $\|R_{i}\|_{0}\leq q$ и R имеет блочную структуру.

Блочная структура R связана с тем фактом, что каждый сигнал помечен только одной квартире. Сравнивая две формулировки, k q - Flat аналогичен моделированию разреженного словаря, когда $l=K\times q$ с дополнительной блочной структурой на R. и Пользователи могут обратиться к статье Шлама. для более подробного обсуждения взаимосвязи между этими двумя понятиями.

Приложения и вариации

Классификация

Классификация — это процедура, которая классифицирует входной сигнал по различным классам. Одним из примеров является классификация электронного письма на классы спама и неспама . Алгоритмы классификации обычно требуют контролируемого этапа обучения. На этапе контролируемого обучения данные обучения для каждого класса используются алгоритмом для изучения характеристик класса. На этапе классификации новое наблюдение классифицируется в класс с использованием уже обученных характеристик.

k q Для классификации можно использовать -плоский алгоритм. Предположим, что всего существует m классов. Для каждого класса k квартир априори обучаются с помощью набора обучающих данных. Когда появятся новые данные, найдите квартиру, которая ближе всего к новым данным. Затем новые данные привязываются к классу ближайшей квартиры.

Однако эффективность классификации можно еще улучшить, если мы наложим некоторую структуру на квартиры. Один из возможных вариантов — потребовать, чтобы разные квартиры разного класса находились на достаточном расстоянии друг от друга. Некоторые исследователи используйте эту идею и разработайте дискриминативный k q-плоский алгоритм.

K-метрики

В k q - Flats алгоритме $\|x-P_{F}(x)\|^{2}$ используется для измерения ошибки представления. $P_{F}(x)$ обозначает проекцию x на плоскость F . Если данные лежат в q -мерной плоскости, то одна q -плоская плоскость может очень хорошо представлять данные. Напротив, если данные лежат в пространстве очень высокой размерности, но вблизи общего центра, то алгоритм k-средних является лучшим способом k q представления данных, чем алгоритм -плоский. Это потому, что k -means. используется алгоритм $\|x-x_{c}\|^{2}$ для измерения ошибки, где $x_{c}$ обозначает центр. K-метрика — это обобщение, в котором используется как идея плоского, так и среднего значения. В k-метриках ошибка измеряется следующей метрикой Махаланобиса.

$$\left\|x-y\right\|_{A}^{2}=(x-y)^{\mathsf {T}}A(x-y)$$

где A — положительная полуопределенная матрица.

Если A — единичная матрица, то метрика Махаланобиса точно такая же, как мера ошибки, используемая в k -средних. Если A не является единичной матрицей, то $\|x-y\|_{A}^{2}$ будет отдавать предпочтение определенным направлениям в качестве меры k q -плоской ошибки.