Метод головних компонент

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Ме́тод головни́х компоне́нт (МГК, англ. principal component analysis, PCA) — метод факторного аналізу в статистиці, який використовує ортогональне перетворення множини спостережень з можливо пов'язаними змінними (сутностями, кожна з яких набуває різних числових значень) у множину змінних без лінійної кореляції, які називаються головними компонентами.

Метод головних компонент — один з основних способів зменшити розмірність даних, втративши найменшу кількість інформації. Винайдений Карлом Пірсоном у 1901 році та доповнений і розширений Гарольдом Готелінґом в 1933. Застосовується в багатьох галузях, зокрема, в економетриці, біоінформатиці, обробці зображень, для стиснення даних, у суспільних науках.

Обчислення головних компонент може бути зведене до обчислення сингулярного розкладу матриці даних або до обчислення власних векторів і власних чисел коваріаційної матриці початкових даних. Іноді метод головних компонент називають перетворенням Кархунена — Лоева[1] або перетворенням Хотеллінга (англ. Hotelling transform).

Зміст

Загальна характеристика[ред. | ред. код]

Схема математичних перетворень. На малюнку позначення: X — матриця вихідних даних розмірністю n×m (n — число об'єктів спостереження, m — число елементарних аналітичних ознак); Z — матриця центрованих і нормованих значень ознак; R — матриця парних кореляцій. Λ — діагональна матриця власних (характеристичних) чисел. A — матриця факторного відображення, її елементи arj — вагові коефіцієнти. Спочатку A має розмірність m*m — за кількістю елементарних ознак Xj, потім в аналізі залишається r найвагоміших компонент, r ≤ m. Обчислюють матрицю A за відомими даними матриці власних чисел Λ і нормованими власними векторами V за формулою A = VΛ1/2. F — матриця значень головних компонент розмірністю r×n.

Метод головних компонент — один з найпоширеніших методів факторного аналізу.[2]

Серед інших подібних методів, що дозволяють узагальнювати значення елементарних ознак, МГК виділяється простою логічною конструкцією, і, разом з тим, на його прикладі стають зрозумілими загальна ідея й цілі чисельних методів факторного аналізу.

Метод головних компонент дає можливість за m — числом початкових ознак виділити r головних компонент, або узагальнених ознак. Простір головних компонент ортогональний. Математична модель методу головних компонент базується на логічному припущенні, що значення множини взаємозалежних ознак породжують деякий загальний результат.

Розв'язування задачі методом головних компонент зводиться до поетапного перетворення матриці початкових даних X.

Формальна постановка задачі[ред. | ред. код]

Задача аналізу головних компонент має щонайменше чотири базових версії:

  • апроксимувати дані лінійними многовидами[ru] меншої розмірності;
  • знайти підпростори меншої розмірності, в ортогональній проекції на які розкид даних (тобто середньоквадратичне відхилення від середнього значення) максимальний;
  • знайти підпростори меншої розмірності, в ортогональній проекції на які середньоквадратична відстань між точками максимальна;
  • для даної багатовимірної випадкової величини побудувати таке ортогональне перетворення координат, внаслідок якого кореляції між окремими координатами перетворяться в нуль.

Перші три версії оперують скінченними множинами даних. Вони еквівалентні і не використовують жодної гіпотези про статистичне породження даних. Четверта версія оперує випадковими величинами. Скінченні множини з'являються тут як вибірки з даного розподілу, а розв'язання трьох перших завдань — як наближення до розкладу за теоремою Кархунена — Лоева[ru] («істинного перетворення Кархунена — Лоева»). При цьому виникає додаткове і не цілком тривіальне питання про точність цього наближення.

Апроксимація даних лінійними многовидами[ред. | ред. код]

Ілюстрація до знаменитої роботи Пірсона (1901): дані точки на площині,  — відстань від до прямої . Шукається пряма , що мінімізує суму

Метод головних компонент починався з задачі найкращої апроксимації скінченної множини точок прямими і площинами (Пірсон, 1901). Дано скінченну множину векторів для кожного серед всіх -вимірних лінійних многовидів[ru] у знайти таке , що сума квадратів відхилень від мінімальна:

,

де  — евклідова відстань від точки до лінійного многовиду. Кожен -вимірний лінійний многовид в може бути заданий як множина лінійних комбінацій , де параметри пробігають дійсну пряму , а  — ортонормований набір векторів

,

де евклідова норма,  — евклідів скалярний добуток, або в координатній формі:

.

Розв'язок задачі апроксимації для дається набором вкладених лінійних многовидів , . Ці лінійні многовиди визначаються ортонормованим набором векторів (векторами головних компонент) та вектором . Вектор шукається як розв'язок задачі мінімізації для :

,

тобто

.

Це — вибіркове середнє: .

Фреше в 1948 році звернув увагу, що варіаційне визначення середнього (як точки, що мінімізує суму квадратів відстаней до точок даних) дуже зручно для побудови статистики в довільному метричному просторі, і побудував узагальнення класичної статистики для загальних просторів (узагальнений метод найменших квадратів).

Вектори головних компонент можуть бути знайдені як розв'язки однотипних задач оптимізації:

  1. Централізуються дані (відніманням середнього): . Тепер ;
  2. Відшукується перша головна компонента як розв'язок задачі:
    .
    якщо розв'язок не єдиний, то вибирається один з них.
  3. З даних віднімається проекція на першу головну компоненту:
    ;
  4. Відшукується друга головна компонента як розв'язок задачі:
    .
    Якщо розв'язок не єдиний, то вибирається один з них.

Далі процес триває, тобто на кроці віднімається проекція на -у головну компоненту (до цього моменту проекції на попередні головні компоненти вже відняті):

;

і на кроці визначається -а головна компонента як розв'язок задачі:

(якщо розв'язок не єдиний, то вибирається один з них).

На кожному підготовчому кроці віднімається проекція на попередню головну компоненту. Знайдені вектори ортонормовані просто внаслідок розв'язування описаної задачі оптимізації, однак, щоб не дати помилкам обчислення порушити взаємну ортогональність векторів головних компонент, можна включати в умови задачі оптимізації.

Неєдиність у визначенні крім тривіальної довільності у виборі знака ( і розв'язують ту саму задачу) може бути більш істотною і походити, наприклад, з умов симетрії даних. Остання головна компонента  — одиничний вектор, ортогональний всім попереднім .

Пошук ортогональних проекцій з найбільшим розсіянням[ред. | ред. код]

< Нехай нам дано центрований набір векторів даних (середнє арифметичне значення дорівнює нулю). Завдання — знайти таке ортогональне перетворення в нову систему координат, для якого б виконувались такі умови:

  • Вибіркова дисперсія даних уздовж першої координати максимальна (цю координату називають першою головною компонентою);
  • Вибіркова дисперсія даних уздовж другої координати максимальна за умови ортогональності першій координаті (друга головна компонента);
  • Вибіркова дисперсія даних уздовж значень -ої координати максимальна за умови ортогональності першим координатами;

Вибіркова дисперсія даних уздовж напрямку, заданого нормованим вектором , це

(оскільки дані центровані, вибіркова дисперсія тут збігається із середнім квадратом ухилення від нуля).

Розв'язок задачі про найкращу апроксимацію дає ту ж множину головних компонент , що й пошук ортогональних проекцій з найбільшим розсіянням, з дуже простої причини: і перший доданок не залежить від .

Пошук ортогональних проекцій з найбільшою середньоквадратичною відстанню між точками[ред. | ред. код]

Ще одне еквівалентне формулювання випливає з очевидної тотожності, правильної для будь-яких векторів :

У лівій частині цієї тотожності стоїть середньоквадратична відстань між точками, а в квадратних дужках праворуч — вибіркова дисперсія. Таким чином, у методі головних компонент шукаються підпростори, в проекції на які середньоквадратична відстань між точками максимальна (або, що те ж саме, її спотворення внаслідок проекції мінімальне)[3]. Таке переформулювання дозволяє будувати узагальнення зі зважуванням різних парних відстаней (а не тільки точок).

Анулювання кореляцій між координатами[ред. | ред. код]

Для заданої -вимірної випадкової величини знайти такий ортонормований базис, , в якому коефіцієнт коваріації між різними координатами дорівнює нулю. Після перетворення до цього базису

для .

Тут  — коефіцієнт коваріації, де  — математичне сподівання.

Діагоналізація коваріаційної матриці[ред. | ред. код]

Всі задачі про головні компоненти приводять до задачі діагоналізації коваріаційної матриці або вибіркової коваріаційної матриці. Емпірична або вибіркова коваріаційна матриця, це

Коваріаційна матриця багатовимірної випадкової величини , це

Вектори головних компонент для задач про найкращу апроксимацію і про пошук ортогональних проекцій з найбільшим розсіянням — це ортонормований набір власних векторів емпіричної коваріаційної матриці , розташованих у порядку спадання власних значень Ці вектори слугують оцінкою для власних векторів коваріаційної матриці . У базисі власних векторів коваріаційної матриці вона, природно, діагональна, і в цьому базисі коефіцієнт коваріації між різними координатами дорівнює нулю.

Якщо спектр коваріаційної матриці вироджений, то вибирають довільний ортонормований базис власних векторів. Він існує завжди, а власні числа коваріаційної матриці завжди дійсні і невід'ємні.

Сингулярний розклад матриці даних[ред. | ред. код]

Ідея сингулярного розкладу[ред. | ред. код]

Математичний зміст методу головних компонент — це спектральне розкладання коваріаційної матриці , тобто подання простору даних у вигляді суми взаємно ортогональних власних підпросторів , а самої матриці  — у вигляді лінійної комбінації ортогональних проекторів на ці підпростори з коефіцієнтами . Якщо  — матриця, складена з векторів-рядків (розмірності ) центрованих даних, то і задача про спектральний розклад коваріаційної матриці перетворюється на задачу про сингулярний розклад матриці даних .

Число називається сингулярним числом матриці тоді і тільки тоді, коли існують правий і лівий сингулярні вектори: такі -вимірний вектор-рядок і -вимірний вектор-стовпець (обидва одиничної довжини), що виконуються дві рівності:

Нехай  — ранг матриці даних. Сингулярний розклад матриці даних  — це її подання у вигляді

де  — сингулярне число,  — відповідний правий сингулярний вектор-стовпець, а  — відповідний лівий сингулярний вектор-рядок (). Праві сингулярні вектори-стовпці , що беруть участь у цьому розкладі, є векторами головних компонент і власними векторами емпіричної коваріаційної матриці , що відповідають додатним власним числам .

Хоча формально завдання сингулярного розкладу матриці даних і спектрального розкладу коваріаційної матриці збігаються, алгоритми обчислення сингулярного розкладу безпосередньо, без обчислення коваріаційної матриці і її спектра, більш ефективні і стійкі[4].

Теорія сингулярного розкладання була створена Джеймсом Джозефом Сильвестром у 1889 році і викладена в усіх докладних посібниках з теорії матриць[5].

Простий ітераційний алгоритм сингулярного розкладання[ред. | ред. код]

Основна процедура — пошук найкращого наближення довільної матриці матрицею виду (де  — -вимірний вектор, а  — -вимірний вектор) методом найменших квадратів:

Розв'язок цієї задачі дається послідовними ітераціями за явними формулами. При фіксованому векторі значення , що надають мінімум формі однозначно і явно визначаються з рівностей  :

Аналогічно, при фіксованому векторі визначаються значення :

Як початкове наближення вектора береться випадковий вектор одиничної довжини, обчислюємо вектор , далі для цього вектора обчислюємо вектор і т. д. Кожен крок зменшує значення . Як критерій зупинки використовується малість відносного зменшення значення функціоналу , що мінімізується, за крок ітерації () або малість самого значення .

Внаслідок цього для матриці отримується найкраще наближення матрицею виду (тут верхнім індексом позначено номер наближення). Далі, з матриці віднімається отримана матриця , і для отриманої матриці ухилень знову шукається найкраще наближення цього ж виду і т. д., поки, наприклад, норма не стане достатньо малою. В результаті отримали ітераційну процедуру розкладання матриці у вигляді суми матриць рангу 1, тобто . Приймаємо і нормуємо вектори : В результаті отримано апроксимацію сингулярних чисел і сингулярних векторів (правих — і лівих — ).

До переваг цього алгоритму відноситься його виняткова простота і можливість майже без змін перенести його на дані з прогалинами[6], а також зважені дані.

Існують різні модифікації базового алгоритму, що поліпшують точність і стійкість. Наприклад, вектори головних компонент при різних повинні бути ортогональні «за побудовою», однак за великого числа ітерацій (велика розмірність, багато компонент) малі відхилення від ортогональності накопичуються і може знадобитися спеціальна корекція на кожному кроці, що забезпечує його ортогональність раніше знайденим головним компонентам.

Для квадратних симетричних додатно визначених матриць описаний алгоритм перетворюється на метод прямих ітерацій для пошуку власних векторів (див. статтю Власні вектори та власні числа).

Сингулярне розкладання тензорів і тензорний метод головних компонент[ред. | ред. код]

Часто вектор даних має додаткову структуру прямокутної таблиці (наприклад, плоске зображення) або навіть багатовимірної таблиці — тобто тензора: , . У цьому випадку також ефективно застосовувати сингулярне розкладання. Визначення, основні формули та алгоритми переносяться практично без змін: замість матриці даних маємо -індексну величину , де перший індекс -номер точки (тензора) даних.

Основна процедура — пошук найкращого наближення тензора тензором виду (де  — -вимірний вектор ( — кількість точок даних),  — вектор розмірності при ) методом найменших квадратів:

Розв'язок цієї задачі отримується послідовними ітераціями за явними формулами. Якщо задано всі вектори-співмножники крім одного , то він визначається явно з достатніх умов мінімуму.

Як початкове наближення векторів () беруться випадкові вектори одиничної довжини, обчислимо вектор далі для цього вектора і даних векторів обчислюється вектор і так далі (циклічно перебираючи індекси). Кожен крок зменшує значення . Алгоритм, очевидно, збігається. Як критерій зупинки використовується малість відносного зменшення значення функціоналу , що мінімізується, за цикл або малість самого значення . Далі, від тензора віднімається отримане наближення і для залишку знову шукається найкраще наближення цього ж вигляду і т. д., поки, наприклад, норма чергового залишку не стане достатньо малою.

Це багатокомпонентне сингулярне розкладання (тензорний метод головних компонент) успішно застосовується при обробці зображень, відеосигналів, і, ширше, будь-яких даних, що мають табличну або тензорну структуру.

Матриця перетворення до головних компонентів[ред. | ред. код]

Матриця перетворення даних до головних компонент складається з векторів головних компонент, розташованих у порядку спадання власних значень:

( означає транспонування), причому

Тобто, матриця є ортогональною.

Велика частина варіації даних буде зосереджена в перших координатах, що дозволяє перейти до простору меншої розмірності.

Залишкова дисперсія[ред. | ред. код]

Нехай дані центровані, . При заміні векторів даних їх проекцією на перші головних компонент вноситься середній квадрат помилки в розрахунку на один вектор даних:

де  — власні значення емпіричної коваріаційної матриці , розташовані в порядку спадання, з урахуванням кратності.

Ця величина називається залишковою дисперсією. Величина

називається поясненою дисперсією. Їх сума дорівнює вибірковій дисперсії. Відповідний квадрат відносної помилки — це відношення залишкової дисперсії до вибіркової дисперсії (тобто частка непоясненої дисперсії):

За відносною помилкою оцінюється придатність методу головних компонент з проеціюванням на перші компонент.

Зауваження: в більшості обчислювальних алгоритмів власні числа з відповідними власними векторами головними компонентами обчислюються в порядку «від великих  — до менших». Для обчислення достатньо обчислити перші власних чисел і слід емпіричної коваріаційної матриці , (суму діагональних елементів , тобто дисперсій за осями). Тоді

Відбір головних компонент за правилом Кайзера[ред. | ред. код]

Цільовий підхід до оцінки числа головних компонент з необхідною часткою поясненої дисперсії формально застосовується завжди, однак неявно він припускає, що немає поділу на «сигнал» і «шум», і будь-яка наперед задана точність має сенс. Тому часто більш продуктивна інша евристика, яка ґрунтується на гіпотезі про наявність «сигналу» (порівняно мала розмірність, відносно велика амплітуда) і «шуму» (велика розмірність, відносно мала амплітуда). З цієї точки зору метод головних компонент працює як фільтр: сигнал міститься, в основному, в проекції на перші головні компоненти, а в інших компонентах пропорція шуму значно вища.

Питання: як оцінити число необхідних головних компонент, якщо відношення «сигнал/шум» заздалегідь не відоме?

Найпростіший і найстаріший метод відбору головних компонент дає правило Кайзера (англ. Kaiser's rule): значущі ті головні компоненти, для яких

тобто перевищує середнє значення (середню вибіркову дисперсію координат вектора даних). Правило Кайзера добре працює в простих випадках, коли є декілька головних компонент з , які значно перевищують середнє значення, а інші власні числа, менші за нього. У більш складних випадках воно може давати занадто багато значущих головних компонент. Якщо дані нормовані на одиничну вибіркову дисперсію за осями, то правило Кайзера набуває особливо простого вигляду: значущі тільки ті головні компоненти, для яких .

Оцінка числа головних компонент за правилом зламаної тростини[ред. | ред. код]

Приклад: оцінка числа головних компонент за правилом зламаної тростини в розмірності 5.

Одним з найбільш популярних евристичних підходів до оцінки числа необхідних головних компонент є правило зламаної тростини (англ. Broken stick model)[7]. Набір нормованих на одиничну суму власних чисел (, ) порівнюється з розподілом довжин уламків тростини одиничної довжини, зламаної в -й випадково вибраній точці (точки зламу вибираються незалежно і рівномірно розподілені вздовж тростини). Нехай () — довжини отриманих шматків тростини, занумеровані в порядку зменшення довжини. Нескладно знайти математичне сподівання :

За правилом зламаної тростини -й власний вектор (у порядку зменшення власних чисел ) зберігається в списку головних компонент, якщо

На рисунку наведено приклад для 5-вимірного випадку:

=(1+1/2+1/3+1/4+1/5)/5; =(1/2+1/3+1/4+1/5)/5; =(1/3+1/4+1/5)/5; =(1/4+1/5)/5; =(1/5)/5.

Для прикладу вибрано

=0.5; =0.3; =0.1; =0.06; =0.04.

За правилом зламаної тростини в цьому прикладі слід залишати 2 головні компоненти:

За оцінками користувачів, правило зламаної тростини має тенденцію занижувати кількість значущих головних компонент.

Нормування[ред. | ред. код]

Нормування після зведення до головних компонент[ред. | ред. код]

Після проеціювання на перші головних компонент з зручно провести нормування на одиничну (вибіркову) дисперсію за осями. Дисперсія вздовж -ї головної компоненти дорівнює ), тому для нормування треба поділити відповідну координату на . Це перетворення не є ортогональним і не зберігає скалярного добутку. Коваріаційна матриця проекції даних після нормування стає одиничною, проекції на будь-які два ортогональні напрямки стають незалежними величинами, а будь-який ортонормований базис стає базисом головних компонент (нагадаємо, що нормування змінює відношення ортогональності векторів). Відображення простору початкових даних на перші головних компонент разом з нормуванням задається матрицею

.

Саме це перетворення найчастіше називається перетворенням Кархунена — Лоева. Тут  — вектори-стовпці, а верхній індекс означає транспонування.

Нормування до обчислення головних компонент[ред. | ред. код]

Попередження: не слід плутати нормування, що проводиться після перетворення до головних компонент, з нормуванням і «знерозмірюванням» при передобробці даних, що проводиться до обчислення головних компонент. Попереднє нормування потрібне для обґрунтованого вибору метрики, в якій буде обчислюватися найкраща апроксимація даних, або будуть шукатися напрямки найбільшого розкиду (що еквівалентно). Наприклад, якщо дані являють собою просторові вектори з «метрів, літрів і кілограмів», то при використанні стандартної евклідової відстані різниця на 1 метр за першою координатою робитиме такий самий внесок, що й різниця на 1 літр за другою, або на 1 кг за третьою. Зазвичай системи одиниць, в яких подані початкові дані, недостатньо точно відображають наші уявлення про природні масштаби за осями, і проводиться «знерозмірювання»: кожна координата ділиться на певний масштаб, який визначається даними, цілями їх обробки і процесами вимірювання і збору даних.

Є три істотно різних стандартних підходи до такого нормування: на одиничну дисперсію за осями (масштаби за осями дорівнюють середнім квадратичним ухиленням — після цього перетворення коваріаційна матриця збігається з матрицею коефіцієнтів кореляції), на рівну точність вимірювання (масштаб за віссю пропорційний точності вимірювання даної величини) і на рівні вимоги в задачі (масштаб за віссю визначається необхідною точністю прогнозу даної величини або допустимим її спотворенням — рівнем толерантності). На вибір передобробки впливають змістовна постановка задачі, а також умови збору даних (наприклад, якщо колекція даних принципово не завершена і дані будуть ще надходити, то нераціонально вибирати нормування строго на одиничну дисперсію, навіть якщо це відповідає змісту завдання, оскільки це передбачає ренормалізацію всіх даних після отримання нової порції; розумніше вибрати певний масштаб, що грубо оцінює стандартне відхилення, і далі його не змінювати).

Попереднє нормування на одиничну дисперсію за осями руйнується поворотом системи координат, якщо осі не є головними компонентами, і нормування при передобробці даних не замінює нормування після зведення до головних компонент.

Механічна аналогія і метод головних компонент для зважених даних[ред. | ред. код]

Якщо зіставити кожному вектору даних одиничну масу, то емпірична коваріаційна матриця збіжиться з тензором інерції цієї системи точкових мас (поділеним на повну масу ), а задача про головні компоненти — із задачею зведення тензора інерції до головних осей. Можна використовувати додаткову свободу у виборі значень мас для врахування важливості точок даних або надійності їхніх значень (важливим даними або даними з більш надійних джерел приписуються великі маси). Якщо вектору даних надається маса , то замість емпіричної коваріаційної матриці отримаємо

Всі подальші операції зі зведення до головних компонент виконуються так само, як і в основній версії методу: шукається ортонормований власний базис , впорядковується за спаданням власних значень, оцінюється середньозважена помилка апроксимації даних першими компонентами (за сумами власних чисел ), проводиться нормування і так далі.

Більш загальний спосіб зважування дає максимізація зваженої суми попарних відстаней[8] між проекціями. Для кожних двох точок даних, вводиться вага ; і . Замість емпіричної коваріаційної матриці використовується

При симетрична матриця додатно визначена, оскільки додатна квадратична форма:

Далі шукаємо ортонормований власний базис , впорядковуємо його за спаданням власних значень, оцінюємо середню помилку апроксимації даних першими компонентами і т. д. — так само, як і в основному алгоритмі.

Цей спосіб застосовується за наявності класів: для з різних класів вага вага вибирається більшою, ніж для точок одного класу. Як наслідок, у проекції на зважені головні компоненти різні класи «розсуваються» на більшу відстань.

Інше застосування — зниження впливу великих ухилень, так званих викидів (en.:outlier), які можуть спотворювати картину через використання середньоквадратичної відстані: якщо вибрати , то вплив великих ухилень буде зменшено. Таким чином, описана модифікація методу головних компонент є більш робастною, ніж класична.

Спеціальна термінологія[ред. | ред. код]

В статистиці при використанні методу головних компонент використовують кілька спеціальних термінів.

  • Матриця даних — ; кожен рядок — вектор передоброблених даних (центрованих і правильно нормованих), число рядків — (кількість векторів даних), число стовпців — (розмірність простору даних);
  • Матриця навантажень (англ. loadings) — ; кожен стовпець — вектор головних компонент, число рядків — (розмірність простору даних), число стовпців — (кількість векторів головних компонент, вибраних для проеціювання);
  • Матриця рахунків (англ. scores) — ; кожен рядок — проекція вектора даних на головних компонент; число рядків — (кількість векторів даних), число стовпців — (кількість векторів головних компонент, вибраних для проеціювання);
  • Матриця -рахунків (англ. -scores) — ; кожен рядок — проекція вектора даних на головних компонент, нормована на одиничну вибіркову дисперсію; число рядків — (кількість векторів даних), число стовпців — (кількість векторів головних компонент, вибраних для проектування);
  • Матриця помилок (або залишків) (англ. errors або residuals) — .
  • Основна формула: .

Межі застосування та обмеження ефективності методу[ред. | ред. код]

Метод головних компонент застосовний завжди. Розповсюджене твердження про те, що він застосовний тільки до нормально розподілених даних (або для розподілів близьких до нормальних) хибне: у початковому формулюванні Пірсона ставиться задача про наближення скінченної множини даних та відсутня навіть гіпотеза про їх статистичне породження, не кажучи вже про розподіл.

Однак метод не завжди ефективно знижує розмірність за заданих обмежень на точність . Прямі і площини не завжди забезпечують гарну апроксимацію. Наприклад, дані можуть з хорошою точністю дотримуватися якоїсь кривої, а ця крива може бути складно розташована у просторі даних. У цьому випадку метод головних компонент для прийнятної точності зажадає декількох компонент (замість однієї), або взагалі не дасть зниження розмірності за прийнятної точності. Для роботи з такими «кривими» головними компонентами винайдено метод головних многовидів[9] і різні версії нелінійного методу головних компонент[10][11]. Найбільше неприємностей можуть спричинити дані складної топології. Для їх апроксимації також винайдено різні методи, наприклад самоорганізаційні карти Кохонена, нейронний газ[ru][12] або топологічні граматики[13]. Якщо дані статистично породжені з розподілом, що дуже відрізняється від нормального, то для апроксимації розподілу корисно перейти від головних компонент до незалежних компонент[14], які вже не ортогональні у початковому скалярному добутку. Нарешті, для ізотропного розподілу (навіть нормального) замість еліпсоїда розсіювання отримуємо кулю, і зменшити розмірність методами апроксимації неможливо.

Приклади використання[ред. | ред. код]

Візуалізація даних[ред. | ред. код]

Візуалізація даних — подання в наочній формі даних експерименту або результатів теоретичного дослідження.

Першим вибором у візуалізації множини даних є ортогональне проеціювання на площину перших двох головних компонент (або 3-вимірний простір перших трьох головних компонент). Площина проеціювання є, по суті, плоским двовимірним «екраном», розташованим таким чином, щоб забезпечити «картинку» даних з найменшими спотвореннями. Така проекція буде оптимальною (серед усіх ортогональних проекцій на різні двовимірні екрани) в трьох аспектах:

  1. Мінімальна сума квадратів відстаней від точок даних до проекцій на площину перших головних компонент, тобто екран розташований максимально близько по відношенню до хмари точок.
  2. Мінімальна сума спотворень квадратів відстаней між усіма парами точок з хмари даних після проеціювання точок на площину.
  3. Мінімальна сума спотворень квадратів відстаней між усіма точками даних і їх «центром тяжіння».

Візуалізація даних є одним з найбільш широко використовуваних застосувань методу головних компонент та його нелінійних узагальнень[3].

Стиснення зображень і відео[ред. | ред. код]

Для зменшення просторової надмірності пікселів під час кодування зображень і відео використовується лінійне перетворення блоків пікселів. Подальші квантування отриманих коефіцієнтів і кодування без втрат дозволяють отримати значні коефіцієнти стиснення. Використання перетворення PCA як лінійне перетворення є для деяких типів даних оптимальним з точки зору розміру отриманих даних за однакового спотворення[15]. На даний момент цей метод активно не використовується, в основному через велику обчислювальну складність. Також стиснення даних можна досягти відкидаючи останні коефіцієнти перетворення.

Придушення шуму на фотографіях[ред. | ред. код]

Основна суть методу[16] — при видаленні шуму з блоку пікселів подати окіл цього блоку у вигляді набору точок у багатовимірному просторі, застосувати до нього PCA і залишити тільки перші компоненти перетворення. При цьому передбачається, що в перших компонентах міститься основна корисна інформація, решта ж компонент містять непотрібний шум. Застосувавши зворотне перетворення після редукції базису головних компонент, отримаємо зображення без шуму.

Індексація відео[ред. | ред. код]

Основна ідея — подати за допомогою PCA кожен кадр відео кількома значеннями, які в подальшому будуть використовуватися при побудові бази даних та запитів до неї. Настільки істотна редукція даних дозволяє значно збільшити швидкість роботи і стійкість до ряду спотворень у відео.

Біоінформатика[ред. | ред. код]

Рис. А. Проекція ДНК-блукання на перші 2 головні компоненти для геному бактерії Streptomyces coelicolor[en]
Рис. Б. Проекція ДНК-блукання на перші 3 головні компоненти для геному бактерії Streptomyces coelicolor. Обертання застосовується для візуалізації тривимірної конфігурації

Метод головних компонент інтенсивно використовується в біоінформатиці для скорочення розмірності опису, виділення значущої інформації, візуалізації даних тощо. Один з поширених варіантів використання — аналіз відповідностей[17][18][19]. На ілюстраціях (рис. А, Б) генетичний текст[20] поданий як множина точок у 64-вимірному просторі частот триплетів. Кожна точка відповідає фрагменту ДНК у ковзному вікні завдовжки 300 нуклеотидів (ДНК-блукання). Цей фрагмент розбивається на триплети, що не перекриваються, починаючи з першої позиції. Відносні частоти цих триплетів у фрагменті і складають 64-вимірний вектор. На рис. А наведено проекцію на перші 2 головні компоненти для геному бактерії Streptomyces coelicolor[en]. На рис. Б наведено проекцію на перші 3 головні компоненти. Відтінками червоного і коричневого виділено фрагменти кодувальних послідовностей у прямому ланцюгу ДНК, а відтінками зеленого виділено фрагменти кодувальних послідовностей у зворотному ланцюгу ДНК. Чорним позначено фрагменти, що належать некодувальній частині. Аналіз методом головних компонент більшості відомих бактеріальних геномів представлений на спеціалізованому сайті[21].

Хемометрика[ред. | ред. код]

Метод головних компонент — один з основних методів в хемометриці. Дозволяє розділити матрицю вихідних даних X на дві частини: «змістовну» і «шум».

Психодіагностика[ред. | ред. код]

Психодіагностика є однією з найбільш розроблених галузей застосування методу головних компонент[22]. Стратегія використання ґрунтується на гіпотезі про автоінформативність експериментальних даних, яка передбачає, що діагностичну модель можна створити шляхом апроксимації геометричної структури множини об'єктів у просторі початкових ознак. Хорошу лінійну діагностичну модель вдається побудувати, коли значна частина початкових ознак є внутрішньо збалансованою. Якщо ця внутрішня узгодженість відображає шуканий психологічний конструкт, то параметри лінійної діагностичної моделі (ваги ознак) дає метод головних компонент.

Економетрика[ред. | ред. код]

Метод головних компонент — один з ключових інструментів економетрики, він застосовується для наочного подання даних, забезпечення лаконізму моделей, спрощення підрахунку та інтерпретації, стиснення обсягів збереженої інформації. Метод забезпечує максимальну інформативність та мінімальне спотворення геометричної структури початкових даних.

Соціологія[ред. | ред. код]

В соціології метод необхідний для вирішення перших двох основних завдань[23]:

  1. аналіз даних (опис результатів опитувань або інших досліджень, представлених у вигляді масивів числових даних);
  2. опис соціальних явищ (побудова моделей явищ, у тому числі і математичних моделей).

Політологія[ред. | ред. код]

У політології метод головних компонент був основним інструментом проекту «Політичний атлас сучасності»[24] для лінійного і нелінійного аналізу рейтингів 192 країн світу з п'яти спеціально розроблених інтегральних індексів (рівня життя, міжнародного впливу, загроз, державності і демократії). Для картографії результатів цього аналізу розроблено спеціальну геоінформаційну систему, що об'єднує географічний простір з простором ознак. Також створено карти даних політичного атласу, що використовують як підкладку двовимірні головні многовиди у 5-вимірному просторі країн. Відмінність карти даних від географічної карти полягає в тому, що на географічній карті поруч виявляються об'єкти, які мають подібні географічні координати, в той час як на карті даних поруч виявляються об'єкти (країни) зі схожими ознаками (індексами).

Скорочення розмірності динамічних моделей[ред. | ред. код]

Прокляття розмірності ускладнює моделювання складних систем. Скорочення розмірності моделі — необхідна умова успіху моделювання. Для досягнення цієї мети створена розгалужена математична технологія. Метод головних компонент також використовується в цих завданнях (часто під назвою істинне або власне ортогональне розкладання — англ. proper orthogonal decomposition (POD)). Наприклад, під час опису динаміки турбулентності динамічні змінні — поле швидкостей — належать нескінченновимірному простору (або, якщо подавати поле його значеннями на досить дрібній сітці, — скінченновимірного простору великої розмірності). Можна набрати велику колекцію миттєвих значень полів і застосувати до цієї множини багатовимірних «векторів даних» метод головних компонент. Ці головні компоненти називаються також емпіричними власними векторами. У деяких випадках (структурна турбулентність) метод дає вражаюче скорочення розмірності[25] Інші галузі застосування цієї техніки скорочення динамічних моделей надзвичайно різноманітні — від теоретичних основ хімічної технології до океанології і кліматології.

Сенсорна оцінка харчових продуктів[ред. | ред. код]

Своє застосування метод головних компонент знайшов при проведенні сенсорної (органолептичної) оцінки властивостей харчових продуктів[26]. Метод головних компонент дозволяє проводити класифікацію харчових продуктів у тих випадках, коли для характеристики їхніх властивостей використовується одночасно велика кількість дескрипторів, наприклад при оцінці властивостей вина,[27] мармеладу,[28] екструдованих харчових продуктів,[29] сиру[30] та інших.

Альтернативи та узагальнення[ред. | ред. код]

Метод головних компонент — найпоширеніший підхід до зниження розмірності, однак існують й інші методи, зокрема, метод незалежних компонент[en], багатовимірне шкалювання, а також численні нелінійні узагальнення: метод головних кривих і многовидів, метод пружних карт[ru], пошук найкращої проекції[ru] (англ. Projection Pursuit), нейромережеві методи «вузького горла[ru]», самоорганізаційні карти Кохонена.

Примітки[ред. | ред. код]

  1. Фактично, метод є емпіричною реалізацією теореми Кархунена — Лоева[ru], згідно з якою будь-який випадковий процес може бути поданий у вигляді нескінченного ряду ортогональних функцій[ru]. У російськомовній науковій літературі поширене також написання «перетворення Карунена — Лоева», що відповідає англійському прочитанню фінського прізвища
  2. Abdi H., Williams L.J. (2010). Principal component analysis.. Wiley Interdisciplinary Reviews: Computational Statistics, 2: 433–459. 
  3. а б Зінов'єв А. Ю., Візуалізація багатовимірних даних, Красноярськ, Вид. КГТУ, 2000.
  4. Bau III, D., Trefethen, L. N., Numerical linear algebra, Philadelphia: Society for Industrial and Applied Mathematics, 1997. (Lecture 31) ISBN 978-0-89871-361-9
  5. Гантмахер Ф. Р., Теория матриц. — М: Наука, 1966. — 576 с.
  6. Россиев А. А.,: Ітераційне моделювання неповних даних за допомогою багатовидів малої розмірності, Вид-во СО РАН, 2005.
  7. Cangelosi R. , Goriely A., Component retention in principal component analysis with application to cDNA microarray data, Biology Direct 2007, 2:2. А також на сайті PCA.
  8. Koren Y., Carmel L., Robust linear dimensionality reduction, IEEE Transactions on Visualisation and Computer Graphics, 10 (4) (2004), 459—470. А також на сайті PCA
  9. З цієї роботи почалося вивчення головних багатовидів. Дисертація T. Хасти: Hastie T., Principal Curves and Surfaces, Ph.D Dissertation, Stanford Linear Accelerator Center, Stanford University, Stanford, California, US, November 1984. А також на сайті PCA
  10. Scholz M., Fraunholz M., Selbig J., Nonlinear Principal Component Analysis: Neural Network Models and Applications, In: Gorban A. N. et al (Eds.), LNCSE 58, Springer, 2007 ISBN 978-3-540-73749-0
  11. Yin H. Learning Nonlinear Principal Manifolds by Self-Organising Maps, In: Gorban A. N. et al (Eds.), LNCSE 58, Springer, 2007 ISBN 978-3-540-73749-0
  12. Martinetz, T. M., Berkovich, S. G., and Schulten K. J., Neural-gas network for vector quantization and its application to time-series prediction. IEEE Transactions on Neural Networks, 4 (1993) #4, 558—569. На сайті PCA
  13. Опис методу можна знайти в статті: Gorban A. N. , Sumner N. R., and Zinovyev A. Y., Topological grammars for data approximation, Applied Mathematics Letters, Volume 20, Issue 4 (2007), 382—386; або Gorban A. N. , Sumner N. R., and Zinovyev A. Y., Beyond The Concept of Manifolds: Principal Trees, Metro Maps, and Elastic Cubic Complexes In: Gorban A. N. et al (Eds.), LNCSE 58, Springer, 2007 ISBN 978-3-540-73749-0; а також в arXiv
  14. Hyvdrinen A, Karhunen J., and Oja E., Independent Component Analysis, A Volume in the Wiley Series on and Adaptive Learning Systems for Signal Processing, Communications, and Control. — John Wiley & Sons, Inc., 2001. — XVI+481 pp. ISBN 0-471-40540-X
  15. Rao, K., Yip P. (eds.), The Transform and Data Compression Handbook, CRC Press, Baton Rouge, 2001.
  16. Muresan D. D., Parks T. W., Adaptive Principal Components and Image Denoising, in: Image Processing, 2003, Proceedings 2003 IEEE International Conference on Image Processing (ICIP), 14-17 Sept. 2003, V. 1, pp. I-101-104. На сайті PCA
  17. англ. Correspondence Analysis
  18. Benzécri, J.-P., L Analyse des Données. Volume II. L Analyse des Correspondences, Dunod, Paris, France, 1973.
  19. Tekaia F., Use of Correspondence Analysis in Genome Exploration Архівовано 12 August 2007[Дата не збігається] у Wayback Machine..
  20. См. статтю Трансляція
  21. Zinovyev A., Сluster structures in genomic word frequency distributions; а також в arXiv: PCA and K-Means decipher genome.
  22. Дюк Ст. А., Комп'ютерна психодіагностика, С-Пб., 1994; окремі розділи див. на сайті «Псі-фактор»
  23. Гуц А. К., Фролова Ю. В., Математичні методи в соціології, Серія: Синергетика: від минулого до майбутнього. — Видавництво «УРСС», 2007. — 216 с.
  24. Політичний атлас сучасності: Досвід багатовимірного статистичного аналізу політичних систем сучасних держав. — М: Изд-во «МДІМВ-Університет», 2007. — 272 с.
  25. Berkooz G, Holmes Ph., and. Lumley J. L, The proper orthogonal decomposition in the analysis of turbulent flows, Annu. Rev. Fluid Mech. 25 (1993), 539—575. Перша публікація для аналізу турбулентності — Lumley, J. L., The structure of inhomogeneous turbulence. In Atmospheric Turbulence and Wave Propagation, ed. A. M. Yaglom, V. I. Tatarski, pp. 166—178. Moscow: Nauka, 1967. (Атмосферна турбулентність і поширення радіохвиль. Праці Міжнародного колоквіуму. Москва, 15-22 червня 1965 р. Під ред. А. М. Яглома і в. І. Татарського. М.: Наука, 1967, 374 с. з іл. і карт. (АН СРСР. Междувед. геофиз. ком. Ін-т фізики атмосфери). Цікаво, що автори цих робіт зводять історію свого підходу до робіт Косамбі[ru] (1943), Лоэва[ru] (1945), Кархунена[en] (1946), Пугачова[ru]]] (1953) та Обухова[ru] (1954), не звернувши увагу на роботи Пірсона і 40 років попередньої історії методу.
  26. Harry T. Lawless, Hildegarde Heymann. . — ISBN 9781441964878, 9781441964885. — DOI:10.1007/978-1-4419-6488-5_18.
  27. . — DOI:10.1016/j.microc.2009.12.007.
  28. Nataliya V Zhilinskaya, Varuzhan A Sarkisyan, Valentina M Vorobieva, Irina S Vorobieva, Alla A Kochetkova, Elena A Smirnova, Irina V Glazkova. .
  29. . — DOI:10.1016/j.jfoodeng.2013.08.007.
  30. . — DOI:10.1016/j.ifset.2013.10.003.

Див. також[ред. | ред. код]

Література[ред. | ред. код]

Класичні роботи
  • Pearson K., On lines and planes of closest fit to systems of points in space, Philosophical Magazine, (1901) 2, 559—572; а также на сайте PCA.
  • Sylvester J.J., On the reduction of a bilinear quantic of the nth order to the form of a sum of n products by a double orthogonal substitution, Messenger of Mathematics, 19 (1889), 42—46; а также на сайте PCA.
  • Frećhet M. Les élements aléatoires de nature quelconque dans un espace distancié. Ann. Inst. H. Poincaré, 10 (1948), 215—310.
Основні керівництва
  • Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика. Классификация и снижение размерности.— М.: Финансы и статистика, 1989.— 607 с.
  • Jolliffe I.T. Principal Component Analysis, Series: Springer Series in Statistics, 2nd ed., Springer, NY, 2002, XXIX, 487 p. 28 illus. ISBN 978-0-387-95442-4
Сучасні огляди
Навчальне програмне забезпечення
  • Java-аплет «Метод головних компонент і самоорганізаційні карти» (E. M. Mirkes, Principal Component Analysis and Self-Organizing Maps: applet. University of Leicester, 2011). Вільно поширювана програма з моделями методу головних компонент, самоорганізаційних карт (SOM) і зростаючих самоорганіаційних карт (Growing Self-Organized Maps, GSOM). Дано опис алгоритмів (англ.), наведено керівництва і деякі публікації. Використовується для виконання невеликих студентських дослідницьких робіт з порівняння різних алгоритмів апроксимації даних.

Посилання[ред. | ред. код]