Методи зниження розмірності аналізу даних. Зниження розмірності · Loginom Wiki. Текст наукової роботи на тему «Методи зниження розмірності простору статистичних даних»

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

Пов'язані поняття

Згадки у літературі

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

Пов'язані поняття (продовження)

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

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

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

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

Метод дискретного елемента (DEM, від англ. Discrete element method) - це сімейство чисельних методів, призначених для розрахунку руху великої кількості частинок, таких як молекули, піщинки, гравій, галька та інших гранульованих середовищ. Спосіб був спочатку застосований Cundall в 1971 для вирішення завдань механіки гірських порід.

Мета дослідження:

Оцінка ефективності методик зменшення розмірності даних для оптимізації їх застосування практично розпізнавання (ідентифікації).

Завдання дослідження:

1. Огляд літературних джерел про існуючі методи зменшення розмірності даних.

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

Методи дослідження (програмні засоби):

Мова програмування С++, бібліотека OpenCV

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

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

Рішення про вибір методу скорочення розмірності ґрунтується на знанні про особливості вирішуваного завдання та очікувані результати, а також обмеженість часових та обчислювальних ресурсів. За даними літературних оглядів до найбільш часто використовуваних методів зниження розмірності відносяться Principal Component Analisys (PCA), Independent Component Analisys (ICA) та Singular Value Decomposition (SVD).

Аналіз основних компонентів (PCA) - Найпростіший спосіб зменшення розмірності даних. Він широко застосовується перетворення ознак при зменшенні розмірності даних у завданнях класифікації. Метод заснований на проектуванні даних на нову координатну систему меншої розмірності, яка визначається власними векторами та власними числами матриці. З погляду математики метод головних компонент є ортогональне лінійне перетворення.

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

де – математичне очікування випадкової величини X, – математичне очікування випадкової величини Y. Також ми можемо записати формулу (1) у вигляді:

де – середнє Х, де – середнє Y, N – розмірність даних.

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

де P – розмірність нового простору, N – розмірність вихідної вибірки, – власні числа, – граничне значення. У ході роботи алгоритму отримуємо матрицю з даними MP, лінійно перетворену з MN, після чого PCA знаходить лінійне відображення M, що мінімізує функцію оцінки:

де – евклідова відстань між точками та ,– евклідова відстань між точками та , , . Мінімум цієї оцінної функції можна обчислити, виконавши спектральне розкладання матриці Грама та помноживши власні вектори цієї матриці на корінь із відповідних власних чисел.

Аналіз незалежних компонент ( ICA ) , на відміну від PCA - досить новий, але швидко набирає популярності метод. У його основі лежить ідея лінійного перетворення даних на нові компоненти, які максимально статистично незалежні і необов'язково ортогональні один одному. Для досліджень у цій роботі було обрано алгоритм FastICa, докладно описаний у статті . Основними завданнями даного методу є центрування (віднімання середнього з даних) та «відбілювання» (лінійне перетворення вектора x у вектор з некорельованими координатами, дисперсія яких дорівнює одиниці).

Критерієм незалежності в FastICA є негаусова, яка вимірюється за допомогою коефіцієнта ексцесу:

Для гауссівських випадкових величин ця величина дорівнює нулю, тому FastICA максимізує її значення. Якщо – «вибілені» дані, то матриця коварації «вибілених» даних – одинична матриця.

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

де матриця обчислюється покомпонентною операцією:

Експерименти

Для експериментального дослідження запропонованих методів використовувалися розкадровані послідовності з бази даних CASIA GAIT. База містить послідовності бінарних зображень, що відповідають окремим кадрам відеопослідовності, на яких вже виконано виділення об'єктів, що рухаються.

З усієї множини відеопослідовностей було випадково взято 15 класів, у яких кут зйомки становить 90 градусів, люди зображені у звичайному не зимовому одязі і без сумок. У кожному класі було 6 послідовностей. Довжина кожної послідовності становила щонайменше 60 кадрів. Класи були поділені на навчальну та тестову вибірки по 3 послідовності кожна.

Отримані в результаті методів PCA та ICA ознаки використовувалися для навчання класифікатора, якою у цій роботі виступала машина опорних векторів (Support Vector Machines, SVM).

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

Рисунок 1. а) Метод основних компонентів (PCA) б) Метод незалежних компонентів (ICA)

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

Рисунок 2. Залежність часу класифікації від кількості компонентів а) PCA , б) ICA

На малюнку 2(а,б) представлена ​​залежність часу класифікації від кількості компонентів PCA та ICA. Зростання розмірності обох випадках супроводжувався лінійним зростанням часу обробки. З графіків видно, що класифікатор SVM працював швидше після зниження розмірності за допомогою методу основних компонентів (PCA).

Методи Principal Component Analisys (PCA), Independent Component Analisys (ICA) працювали досить швидко і за певних параметрів були отримані високі результати завдання класифікації. Але з даними зі складною структурою ці методи не завжди дозволяють досягти бажаного результату. Тому останнім часом все більше приділяють увагу локальним нелінійним методам, які здійснюють проекцію даних на деяке різноманіття, що дозволяє зберегти структуру даних.

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

Список літератури:

1. Jolliffe, I.T, Principal Component Analysis, Springer, 2002
2. Hyvärinen and Erkki Oja, Independent Component Analysis: Algorithms and Applications, Neural Networks, 13, 2000
3. Josiński, H. Feature Extraction and HMM-Based Classification of Gait Video Sequences for Purpose of Human Identification/ Springer, 2013 - Vol 481.

Розділ 13. МЕТОД ГОЛОВНИХ КОМПОНЕНТ

13.1. Сутність проблеми зниження розмірності та різні методи її вирішення

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

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

Бажання статистика подати кожне зі спостережень (13.1) у вигляді вектора Z деяких допоміжних показників із істотно меншим (чим ) числом компонентів зумовлюється в першу чергу такими причинами:

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

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

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

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

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

Завдання полягає у визначенні такого набору ознак Z, знайденого в класі F допустимих перетворень вихідних показників

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

Пояснимо це на прикладах.

13.1.1. Метод основних компонентів (див. § 13.2-§ 13.6).

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

(тут ) - математичне очікування а як міра інформативності -мірної системи показників вираз

(Тут D, як і раніше, знак операції обчислення дисперсії відповідної випадкової величини).

13.1.2. Факторний аналіз (див. гл. 14).

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

де – «навантаження» загального фактора на вихідний показник – залишкова «специфічна» випадкова компонента, причому – попарно некорельовані.

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

13.1.3. Метод екстремального угруповання ознак (див. 14.2.1).

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

де - коефіцієнт кореляції між змінними.

13.1.4. Багатомірне шкалювання (див. гл. 16).

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

У цьому випадку дослідник має як масив вихідних статистичних даних матрицею розміру (якщо розглядаються характеристики попарної близькості об'єктів) або (якщо розглядаються характеристики попарної близькості ознак) виду

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

Одна із досить загальних схем багатовимірного шкалювання визначається критерієм

де - відстань між об'єктами у вихідному просторі, - відстань між тими самими об'єктами в шуканому просторі меншої розмірності - вільні параметри, вибір конкретних значень яких проводиться на розсуд дослідника.

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

13.1.5. Відбір найінформативніших показників у моделях дискримінантного аналізу (див. § 1.4; 2.5).

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

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

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

13.1.6. Відбір найінформативніших змінних у моделях регресії (див. ).

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

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

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

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

Обговоримо з погляду зниження розмірності приклад використання регресійного аналізу для прогнозування обсягу продажу, розглянутий у підрозділі 3.2.3. По-перше, у цьому прикладі вдалося скоротити кількість незалежних змінних з 17 до 12. По-друге, вдалося сконструювати новий фактор – лінійну функцію від 12 згаданих факторів, яка краще за всіх інших лінійних комбінацій факторів прогнозує обсяг продажів. Тому можна сказати, що в результаті розмірність завдання зменшилася з 18 до 2. Зокрема, залишився один незалежний фактор (наведена в підрозділі 3.2.3 лінійна комбінація) та один залежний – обсяг продажу.

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

Метод основних компонентє одним із найбільш часто використовуваних методів зниження розмірності. Основна його ідея полягає у послідовному виявленні напрямків, у яких дані мають найбільший розкид. Нехай вибірка складається з векторів, однаково розподілених із вектором X = (x(1), x(2), … , x(n)). Розглянемо лінійні комбінації

Y(λ(1), λ(2), …, λ( n)) = λ(1) x(1) + λ(2) x(2) + … + λ( n)x(n),

λ 2 (1) + λ 2 (2) + …+ λ 2 ( n) = 1.

Тут вектор λ = (λ(1), λ(2), …, λ( n)) лежить на одиничній сфері в n-мірному просторі.

У способі основних компонент передусім знаходять напрям максимального розкиду, тобто. таке λ, при якому досягає максимуму дисперсія випадкової величини Y(λ) = Y(λ(1), λ(2), …, λ( n)). Тоді вектор λ визначає першу головну компоненту, а величина Y(λ) є проекцією випадкового вектора Хна вісь першої головної компоненти.

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

У аналізованої гіперплощині процедура повторюється. У ньому знаходять напрям найбільшого розкиду, тобто. другу головну компоненту. Потім виділяють гіперплощину, перпендикулярну першим двом головним компонентам. Її розмірність на 2 менша, ніж розмірність вихідного простору. Далі – наступна ітерація.

З погляду лінійної алгебри йдеться про побудову нового базису n-мірному просторі, ортами якого є основні компоненти.

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

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

Метод головних компонент є одним із методів факторного аналізу. Різні алгоритми факторного аналізу об'єднані тим, що у всіх них відбувається перехід до нового базису у вихідному n-мірному просторі. Важливим є поняття «навантаження фактора», яке застосовується для опису ролі вихідного фактора (змінної) у формуванні певного вектора з нового базису.

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

Описана процедура може бути здійснена не лише за допомогою факторного аналізу. Йдеться про кластер-аналіз ознак (чинників, змінних). Для розбиття ознак групи можна застосовувати різні алгоритми кластер-аналізу. Достатньо ввести відстань (заходи близькості, показник відмінності) між ознаками. Нехай Хі У– дві ознаки. Відмінність d(X, Y) між ними можна вимірювати за допомогою вибіркових коефіцієнтів кореляції:

d 1 (X,Y) = 1 – r n(X,Y), d 2 (X,Y) = 1 - ρ n(X,Y),

де r n(X, Y) – вибірковий лінійний коефіцієнт кореляції Пірсона, ρ n(X, Y) - вибірковий коефіцієнт рангової кореляції Спірмена.

Багатовимірне шкалювання. На використанні відстаней (мір близькості, показників відмінності) d(X, Y) між ознаками Хі Узаснований великий клас методів багатовимірного шкалювання. Основна ідея цього класу методів полягає у поданні кожного об'єкта точкою геометричного простору (зазвичай розмірності 1, 2 або 3), координатами якої служать значення прихованих (латентних) факторів, що в сукупності досить адекватно описують об'єкт. При цьому відносини між об'єктами замінюються відносинами між точками – їхніми представниками. Так, дані про схожість об'єктів - відстанями між точками, дані про перевагу - взаємним розташуванням точок.

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

Нехай є nоб'єктів Про(1), Про(2), …, O(n), для кожної пари об'єктів Про(i), O(j) задана міра їх подібності s(i, j). Вважаємо, що завжди s(i, j) = s(j, i). Походження чисел s(i, j) немає значення для опису роботи алгоритму. Вони могли бути отримані або безпосереднім виміром, або з використанням експертів, або шляхом обчислення сукупності описових характеристик, або якось інакше.

В евклідовому просторі розглядаються nоб'єктів мають бути представлені конфігурацією nточок, причому як міра близькості точок-представників виступає евклідова відстань d(i, j) між відповідними точками. Ступінь відповідності між сукупністю об'єктів і сукупністю точок, що їх представляють, визначається шляхом зіставлення матриць подібності || s(i, j)|| та відстаней || d(i, j)||. Метричний функціонал подібності має вигляд

Геометричну конфігурацію треба вибирати так, щоб функціонал S досягав найменшого значення .

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

Нехай евклідовий простір має розмірність m. Розглянемо мінімум середнього квадрата помилки

,

де мінімум береться за всіма можливими конфігураціями nточок в m-мірному евклідовому просторі Можна показати, що аналізований мінімум досягається деякій конфігурації. Ясно, що при зростанні mвеличина α m монотонно зменшується (точніше, не зростає). Можна показати, що за m > n- 1 вона дорівнює 0 (якщо s(i, j) – метрика). Для збільшення можливостей змістовної інтерпретації бажано діяти у просторі можливо меншої розмірності. Однак розмірність необхідно вибрати так, щоб точки представляли об'єкти без великих спотворень. Виникає питання: як оптимально вибирати розмірність, тобто. натуральне число m?

У межах детермінованого аналізу даних обґрунтованої відповіді це питання, певне, немає. Отже, необхідно вивчити поведінку α m у тих чи інших імовірнісних моделях. Якщо міри близькості s(i, j) є випадковими величинами, розподіл яких залежить від «істинної розмірності» m 0 (і, можливо, від будь-яких параметрів), то можна в класичному математико-статистичному стилі ставити завдання оцінки m 0, шукати заможні оцінки і т.д.

Почнемо будувати імовірнісні моделі. Приймемо, що об'єкти є крапками в евклідовому просторі розмірності k, де kдосить велике. Те, що «справжня розмірність» дорівнює m 0 означає, що всі ці точки лежать на гіперплощині розмірності m 0 . Приймемо для визначеності, що сукупність точок, що розглядаються, являє собою вибірку з кругового нормального розподілу з дисперсією σ 2 (0). Це означає, що об'єкти Про(1), Про(2), …, O(n) є незалежними в сукупності випадковими векторами, кожен із яких будується як ζ(1) e(1) + ζ(2) e(2) + … + ζ( m 0)e(m 0), де e(1), e(2), … , e(m 0) – ортонормальний базис у підпросторі розмірності m 0 , в якому лежать точки, що розглядаються, а ζ(1), ζ(2), … , ζ( m 0) – незалежні в сукупності одновимірні нормальні випадкові величини з математичним очікуванням) та дисперсією σ 2 (0).

Розглянемо дві моделі отримання мір близькості s(i, j). У першій із них s(i, j) відрізняються від евклідової відстані між відповідними точками через те, що точки відомі з спотвореннями. Нехай з(1),з(2), … , з(n) - Розглянуті точки. Тоді

s(i, j) = d(c(i) + ε( i), c(j) + ε( j)), i, j = 1, 2, … , n,

де d- евклідова відстань між точками в k-мірному просторі, вектора ε(1), ε(2), … , ε( n) являють собою вибірку з кругового нормального розподілу k-мірному просторі з нульовим математичним очікуванням та коваріаційною матрицею σ 2 (1) I, де I- одинична матриця. Іншими словами, ε( i) = η(1) e(1) + η(2) e(2) + … + η( k)e(k), де e(1), e(2), …, e(k) – ортонормальний базис у k-мірному просторі, а (η( i, t), i= 1, 2, …, n, t= 1, 2, …, k) – сукупність незалежних у сукупності одновимірних випадкових величин з нульовим математичним очікуванням та дисперсією σ 2 (1).

У другій моделі спотворення накладені безпосередньо на самі відстані:

s(i,j) = d(c(i), c(j)) + ε( i,j), i,j = 1, 2, … , n, i ≠ j,

де (ε( i, j), i, j = 1, 2, … , n) – незалежні в сукупності нормальні випадкові величини з математичним очікуванням) та дисперсією σ 2 (1).

У роботі показано, що для обох сформульованих моделей мінімум середнього квадрата помилки α m при n→ ∞ сходиться ймовірно до

f(m) = f 1 (m) + σ 2 (1)( k – m), m = 1, 2, …, k,

Таким чином, функція f(m) лінійна на інтервалах і , причому на першому інтервалі вона меншає швидше, ніж на другому. Звідси випливає, що статистика

є заможною оцінкою істинної розмірності m 0 .

Отже, з ймовірнісної теорії випливає рекомендація – як оцінку розмірності факторного простору використовувати m*. Зазначимо, що подібна рекомендація була сформульована як евристична одним із засновників багатовимірного шкалювання Дж. Краскалом. Він виходив із досвіду практичного використання багатовимірного шкалювання та обчислювальних експериментів. Імовірна теорія дозволила обґрунтувати цю евристичну рекомендацію.

В результаті вивчення матеріалу глави 5 учень повинен:

знати

• основні поняття та завдання зниження розмірності:
• підходи до розв'язання задач трансформації ознакового простору;

вміти

• використовувати метод основних компонент переходу до стандартизованим ортогональним ознаками;
• оцінювати зменшення інформативності даних у разі зниження розмірності ознакового простору;
• вирішувати задачу побудови оптимальних багатовимірних шкал на дослідження об'єктів;

володіти

• методами зниження розмірності на вирішення прикладних завдань статистичного аналізу;
• навичками інтерпретації змінних у перетвореному ознаковому просторі.

Основні поняття та завдання зниження розмірності

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

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

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

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

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

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

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

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

p align="justify"> Редукція ознакового простору супроводжується певним зниженням інформативності даних, але рівень допустимого зниження може бути визначений заздалегідь. Виділення ознак проектує набір вихідних змінних у простір меншої розмірності. Стиснення ознакового простору до двох-тривимірного може бути корисним для візуалізації даних. Таким чином, процес формування нового ознакового простору зазвичай призводить до меншого набору реально інформативних змінних. На їх основі може бути побудована якісніша модель як заснована на меншому числі найбільш інформативних ознак.

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

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

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

Перетворення вихідного ознакового простору в ортогональне зручно для вирішення завдань класифікації, оскільки дозволяє обґрунтовано застосовувати певні заходи близькості або відмінностей об'єктів, такі як відстань евкліда або квадрат евклідова відстані. У регресійному аналізі побудова рівняння регресії на головних компонентах дозволяє вирішити проблему мультиколінеарності.