K q-flats - Википедия - k q-flats

В сбор данных и машинное обучение, ${ displaystyle k}$ ${ displaystyle q}$-flats алгоритм ^[1][2] это итерационный метод, направленный на разбиение ${ displaystyle m}$ наблюдения в ${ displaystyle k}$ кластеры, где каждый кластер близок к ${ displaystyle q}$-плоский, куда ${ displaystyle q}$ заданное целое число.

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

Описание

Эта статья может быть слишком техническим для большинства читателей, чтобы понять. Пожалуйста помогите улучшить это к сделать понятным для неспециалистов, не снимая технических деталей. (Декабрь 2011 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

Постановка проблемы

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

А ${ displaystyle q}$-flat - это подмножество ${ displaystyle R ^ {n}}$ это соответствует ${ displaystyle R ^ {q}}$. Например, ${ displaystyle 0}$-плоскость - это точка; а ${ displaystyle 1}$-плоскость - линия; а ${ displaystyle 2}$-плоскость - это самолет; а ${ displaystyle n-1}$-квартира гиперплоскость.${ displaystyle q}$-плоскость может быть охарактеризована системой решений линейной системы уравнений: ${ Displaystyle F = {x | x in R ^ {n}, W'x = gamma }}$, куда ${ Displaystyle W in R ^ {п раз (п-д)}}$, ${ Displaystyle гамма в R ^ {1 раз (п-д)}}$.

Обозначим a раздел из ${ Displaystyle {1,2, точки, п }}$ в качестве ${ Displaystyle S = (S_ {1}, S_ {2}, точки, S_ {k})}$Задачу можно сформулировать как

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

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

Алгоритм

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

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

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

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

На этапе присвоения кластера используется следующий факт: с учетом q-квартиры ${ Displaystyle F_ {l} = {х | W'x = гамма }}$ и вектор ${ displaystyle a}$, куда ${ Displaystyle W ^ { prime} W = I}$, расстояние от ${ displaystyle a}$ в q-квартиру ${ displaystyle F_ {l}}$является ${ displaystyle dist (a, F_ {l}) = min_ {x: W ^ { prime} x = gamma} | xa | _ {F} ^ {2} = | W (W'W) ^ {- 1} (W ^ { prime} x- gamma) | _ {F} ^ {2} = | W ^ { prime} x- gamma | _ {F} ^ {2} .}$

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

${ Displaystyle (P2) min _ {W in R ^ {n times (nq)}, gamma in R ^ {1 times (nq)}} | AW-e gamma | _ { F} ^ {2},}$ при условии ${ displaystyle W ^ { prime} W = I,}$

куда ${ displaystyle A in R ^ {m times n}}$ дано, и ${ Displaystyle е = (1, точки, 1) ' в R ^ {м раз 1}}$.

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

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

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

Отношение к другим методам машинного обучения

${ displaystyle k}$-средний алгоритм

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

Изучение разреженного словаря

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

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

${ Displaystyle мин _ {B, R} | X-BR | _ {F} ^ {2}}$ при условии ${ Displaystyle | R_ {я} | _ {0} leq q}$

куда

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

Идея ${ displaystyle k}$ ${ displaystyle q-}$Алгоритм flats по своей природе схож с редким изучением словаря. Если сузить q-плоское до q-мерного подпространства, то ${ displaystyle k}$ ${ displaystyle q-}$Алгоритм flats просто находит замкнутое q-мерное подпространство для данного сигнала. Изучение разреженного словаря тоже делает то же самое, за исключением дополнительных ограничений на разреженность представления. Математически можно показать, что ${ displaystyle k}$ ${ displaystyle q-}$Алгоритм flats представляет собой изучение разреженного словаря с дополнительной блочной структурой на р.

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

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

Блочная структура р ссылается на то, что каждый сигнал помечен только на одну квартиру. Сравнивая две формулировки, k q-flat совпадает с моделированием разреженного словаря, когда ${ Displaystyle л = К раз д}$ и с дополнительной блочной структурой на р. Пользователи могут обратиться к статье Шлама ^[3] для более подробного обсуждения взаимосвязи между двумя концепциями.

Приложения и варианты

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

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

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

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

K-метрики ^[3]

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

${ Displaystyle | х-у | _ {А} ^ {2} = (х-у) ^ {Т} А (х-у)}$

куда А - положительная полуопределенная матрица.

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

Рекомендации