Анализ основных компонентов ядра

В области многомерного статистического анализа , ядра анализа главных компонент (РСА ядра) ^[1] является продолжением основного компонентного анализа (РСА) с использованием методики методов ядра . Используя ядро, первоначально линейные операции PCA выполняются в воспроизводящем гильбертовом пространстве ядра .

Предыстория: Linear PCA [ править ]

Напомним, что обычный PCA работает с данными с нулевым центром; это,

${\ displaystyle {\ frac {1} {N}} \ sum _ {i = 1} ^ {N} \ mathbf {x} _ {i} = \ mathbf {0}}$,

где - одно из многомерных наблюдений. Он работает путем диагонализации ковариационной матрицы ,${\ Displaystyle \ mathbf {х} _ {я}}$${\ displaystyle N}$

${\ displaystyle C = {\ frac {1} {N}} \ sum _ {i = 1} ^ {N} \ mathbf {x} _ {i} \ mathbf {x} _ {i} ^ {\ top} }$

другими словами, он дает собственное разложение ковариационной матрицы:

${\ Displaystyle \ лямбда \ mathbf {v} = C \ mathbf {v}}$

который можно переписать как

${\ displaystyle \ lambda \ mathbf {x} _ {i} ^ {\ top} \ mathbf {v} = \ mathbf {x} _ {i} ^ {\ top} C \ mathbf {v} \ quad {\ textrm {for}} ~ i = 1, \ ldots, N}$. ^[2]

(См. Также: Матрица ковариации как линейный оператор )

Введение ядра в PCA [ править ]

Чтобы понять полезность ядра PCA, особенно для кластеризации, обратите внимание, что, хотя N точек, как правило, нельзя разделить линейно по размерам, их почти всегда можно разделить линейно по размерам. То есть, если дано N точек, если мы отобразим их в N -мерное пространство с${\displaystyle d<N}$${\displaystyle d\geq N}$${\displaystyle \mathbf {x} _{i}}$

${\displaystyle \Phi (\mathbf {x} _{i})}$где ,${\displaystyle \Phi :\mathbb {R} ^{d}\to \mathbb {R} ^{N}}$

легко построить гиперплоскость , разделяющую точки на произвольные кластеры. Конечно, это создает линейно независимые векторы, поэтому нет ковариации, на которой можно было бы выполнять собственное разложение явно, как это было бы в линейном PCA.${\displaystyle \Phi }$

Вместо этого в ядре PCA «выбирается» нетривиальная, произвольная функция, которая никогда не вычисляется явно, что дает возможность использовать функции очень высокой размерности , если нам никогда не придется фактически оценивать данные в этом пространстве. Поскольку мы обычно стараемся избегать работы в -пространстве, которое мы будем называть «пространством функций», мы можем создать ядро ​​N-by-N${\displaystyle \Phi }$${\displaystyle \Phi }$${\displaystyle \Phi }$

${\displaystyle K=k(\mathbf {x} ,\mathbf {y} )=(\Phi (\mathbf {x} ),\Phi (\mathbf {y} ))=\Phi (\mathbf {x} )^{T}\Phi (\mathbf {y} )}$

который представляет внутреннее пространство продукта (см. матрицу Грамиана ) трудноразрешимого в противном случае пространства признаков. Двойственная форма, возникающая при создании ядра, позволяет нам математически сформулировать версию PCA, в которой мы никогда не решаем собственные векторы и собственные значения ковариационной матрицы в -пространстве (см. Уловку с ядром ). N-элементы в каждом столбце K представляют собой скалярное произведение одной точки преобразованных данных по отношению ко всем преобразованным точкам (N точек). Некоторые известные ядра показаны в примере ниже.${\displaystyle \Phi (\mathbf {x} )}$

Поскольку мы никогда не работаем непосредственно в пространстве функций, формулировка ядра PCA ограничена тем, что вычисляет не сами основные компоненты, а проекции наших данных на эти компоненты. Чтобы оценить проекцию из точки в пространстве признаков на k-й главный компонент (где верхний индекс k означает компонент k, а не степени k)${\displaystyle \Phi (\mathbf {x} )}$${\displaystyle V^{k}}$

${\displaystyle {\mathbf {V} ^{k}}^{T}\Phi (\mathbf {x} )=\left(\sum _{i=1}^{N}\mathbf {a_{i}} ^{k}\Phi (\mathbf {x_{i}} )\right)^{T}\Phi (\mathbf {x} )}$

Отметим, что это означает скалярное произведение, которое является просто элементами ядра . Кажется, все, что осталось, это вычислить и нормализовать , что можно сделать, решив уравнение для собственных векторов${\displaystyle \Phi (\mathbf {x_{i}} )^{T}\Phi (\mathbf {x} )}$${\displaystyle K}$${\displaystyle \mathbf {a_{i}} ^{k}}$

${\displaystyle N\lambda \mathbf {a} =K\mathbf {a} }$

где N - количество точек данных в наборе, а и - собственные значения и собственные векторы K. Затем, чтобы нормализовать собственные векторы , мы требуем, чтобы${\displaystyle \lambda }$${\displaystyle \mathbf {a} }$${\displaystyle \mathbf {a} ^{k}}$

${\displaystyle 1=(\mathbf {V} ^{k})^{T}\mathbf {V} ^{k}}$

Следует проявлять осторожность в отношении того факта, что независимо от того, имеет ли оно нулевое среднее значение в исходном пространстве, не гарантируется его центрирование в пространстве функций (которое мы никогда не вычисляем явно). Поскольку для проведения эффективного анализа главных компонент требуются центрированные данные, мы « централизуем » K, чтобы он стал${\displaystyle x}$${\displaystyle K'}$

${\displaystyle K'=K-\mathbf {1_{N}} K-K\mathbf {1_{N}} +\mathbf {1_{N}} K\mathbf {1_{N}} }$

где обозначает матрицу размером N на N, для которой каждый элемент принимает значение . Мы используем для выполнения описанный выше алгоритм ядра PCA.${\displaystyle \mathbf {1_{N}} }$${\displaystyle 1/N}$${\displaystyle K'}$

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

Большие наборы данных [ править ]

На практике большой набор данных приводит к большому K, и сохранение K может стать проблемой. Один из способов справиться с этим - выполнить кластеризацию набора данных и заполнить ядро ​​средствами этих кластеров. Поскольку даже этот метод может дать относительно большое значение K, обычно вычисляются только верхние собственные значения P, а собственные векторы собственных значений вычисляются таким образом.

Пример [ править ]

Точки ввода до ядра PCA

Рассмотрим три концентрических облака точек (показаны); мы хотим использовать ядро ​​PCA для идентификации этих групп. Цвет точек не представляет информацию, задействованную в алгоритме, а только показывает, как преобразование перемещает точки данных.

Сначала рассмотрим ядро

${\displaystyle k({\boldsymbol {x}},{\boldsymbol {y}})=({\boldsymbol {x}}^{\mathrm {T} }{\boldsymbol {y}}+1)^{2}}$

Применение этого к ядру PCA дает следующее изображение.

Вывод после ядра PCA с расширением . Эти три группы можно различить только по первому компоненту.${\displaystyle k({\boldsymbol {x}},{\boldsymbol {y}})=({\boldsymbol {x}}^{\mathrm {T} }{\boldsymbol {y}}+1)^{2}}$

Теперь рассмотрим гауссовское ядро:

${\displaystyle k({\boldsymbol {x}},{\boldsymbol {y}})=e^{\frac {-||{\boldsymbol {x}}-{\boldsymbol {y}}||^{2}}{2\sigma ^{2}}},}$

То есть это ядро ​​является мерой близости, равной 1, когда точки совпадают, и равной 0 на бесконечности.

Вывод после ядра PCA с гауссовым ядром.

Обратите внимание, в частности, что первого главного компонента достаточно, чтобы различать три разные группы, что невозможно с использованием только линейного PCA, потому что линейный PCA работает только в данном (в данном случае двумерном) пространстве, в котором эти концентрические облака точек находятся линейно не разделимы.

Приложения [ править ]

Было продемонстрировано, что ядро ​​PCA полезно для обнаружения новизны ^[3] и устранения шумов в изображениях. ^[4]

См. Также [ править ]

• Кластерный анализ
• Многолинейный PCA
• Мультилинейное подпространственное обучение
• Нелинейное уменьшение размерности
• Спектральная кластеризация

Ссылки [ править ]