Ітераційний алгоритм обчислення головних компонент.

Метод головних компонент (англ. Principal component analysis, PCA) - Один з основних способів зменшити розмірність даних, втративши найменшу кількість інформації. Винайдено К. Пірсоном (англ. Karl Pearson) В 1901 р. Застосовується в багатьох областях, таких як розпізнавання образів, комп'ютерне зір, стиснення даних і т. п. Обчислення головних компонент зводиться до обчислення власних векторів і власних значень ковариационной матриці вихідних даних. Іноді метод головних компонент називають перетворенням Кархунена-Лоева (англ. Karhunen-Loeve) або перетворенням Хотеллінга (англ. Hotelling transform). Інші способи зменшення розмірності даних - це метод незалежних компонент, багатовимірне шкалювання, а також численні нелінійні узагальнення: метод головних кривих і різноманіть, метод пружних карт, пошук найкращої проекції (англ. Projection Pursuit), нейромережеві методи "вузького горла", самоорганізуються карти Кохонена та ін. Завдання аналізу головних компонент, має, як мінімум, чотири базових версії:

1. апроксимувати дані лінійними різноманіття меншої розмірності;

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

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

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

Перші три версії оперують кінцевими множинами даних. Вони еквівалентні і не використовують жодної гіпотези про статистичний породженні даних. Четверта версія оперує випадковими величинами. Кінцеві безлічі з'являються тут як вибірки з даного розподілу, а рішення трьох перших завдань - як наближення до "істинного" перетворенню Кархунена-Лоева. При цьому виникає додатковий і не цілком тривіальне питання про точність цього наближення. Математичний зміст методу головних компонент - це спектральне розкладання коваріаційної матриці C. Тобто уявлення простору даних у вигляді суми взаємно ортогональних власних підпросторів C, а самої матриці C - у вигляді лінійної комбінації ортогональних проекторів на ці підпростору з коефіцієнтами λ_i.

Дерева рішень. Методи опорних векторів, «найближчого сусіда», Байеса.

Дерева рішень є найдавнішим алгоритмом аналізу даних. Роботи в цьому напрямку розчали Ховленд (Hoveland) та Хант (Hunt) у 1950-х роках. Дерева рішень – це спосіб представлення правил в ієрархічно послідовній структурі, де кожному об’єкту відповідає лише єдиний кінцевий вузол, що надає відповідь. Під правилом розуміють логічну конструкцію, що надана у вигляді «Якщо А, Тоді Б». При побудові дерев рішень особлива увага приділяється наступним питанням: вибір критерію атрибуту, за яким відбувається розбиття, зупинка навчання і відсікання гілок. Розглянемо всі ці правила по порядку.

Правило розбиття

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

Зупинка навчання

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

Правило відсікання

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

· Побудувати дерево.

· Відсікти або замінити піддеревом ті гілки, які призводять до зростання помилки.

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

Метод опорних векторів - це набір схожих алгоритмів виду «навчання із вчителем». Ці алгоритми зазвичай використовуються для задач класифікації та регресійного аналізу. Метод належить до розряду лінійних класифікаторів. Також може розглядатись як особливий випадок регуляризації за А. Н. Тихоновим. Особливою властивістю методу опорних векторів є безперервне зменшення емпіричної помилки класифікації та збільшення проміжку. Тому цей метод також відомий як метод класифікатора з максимальним проміжком. Основна ідея методу опорних векторів – перевід вихідних векторів у простір більш високої розмірності та пошук роздільної гіперплощини з максимальним проміжком у цьому просторі. Дві паралельні гіперплощини будуються по обидва боки гіперплощини, що розділяє наші класи. Роздільною гіперплощиною буде та, що максимізує відстань до двох паралельних гіперплощин. Алгоритм працює у припущенні, що чим більша різниця або відстань між цими паралельними гіперплощинами, тим меншою буде середня помилка класифікатора. Часто в алгоритмах машинного навчання виникає необхідність класифікувати дані. Кожен об'єкт даних представлений як вектор (точка) у р -вимірному просторі (послідовність р чисел) Кожна з цих точок належить тільки одному з двох класів. Нас цікавить, чи можемо ми розділити точки гіперплощиною розмірністю (р -1). Це типовий випадок лінійної роздільності. Таких гіперплощин може бути багато. Тому цілком природно вважати, що максимізація зазору між класами сприяє більш впевненій класифікації. Тобто чи можемо ми знайти таку гіперплощину, щоб відстань від неї до найближчої точки було максимальною. Це б означало, що відстань між двома найближчими точками, що лежать по різні сторони гіперплощини, максимальна. Якщо така гіперплощина існує, то вона нас буде цікавити найбільше; вона називається оптимальною розділяючою гіперплощиною, а відповідний їй лінійний класифікатор називається оптимально поділяючим класифікатором. Алгоритм найближчого сусіда — один з перших і найбільш простих евристичних методів розв'язування задачі комівояжера. Відноситься до категорії жадібних алгоритмів. За кожен крок його виконання до знайденої частини маршруту додається нове ребро. Алгоритм припиняє роботу, коли розв’язок знайдено і не намагається його покращити. Формулюється таким чином:

Алгоритм найближчого сусіда починається в довільній точці та поступово відвідує кожну найближчу точку, яка ще не була відвідана. Пункти обходу плану послідовно включаються до маршруту, причому, кожен черговий пункт, що включається до маршруту, повинен бути найближчим до останнього вибраного пункту серед усіх інших, ще не включених до складу маршруту. Алгоритм завершується, коли відвідано всі точки. Остання точка з’єднується з першою. Вхідні дані: множина точок V розмірністю N Вихідні дані: маршрут Т, що складається з послідовності відвідування точок множини V.

Кроки алгоритму (варіант 1):

1. Вибрати довільну точку V1

2. Т1 = V1

3. Для і=2 до і=N виконати:

4. Вибрати точку Vi, найближчу до точки Ті-1

5. Ti = Vi

6. Т N +1 = V1

7. Кінець алгоритму

Кроки алгоритму (варіант 2):

1. Довільно обрати поточну точку

2. Знайти найкоротше ребро, що сполучає поточну точку з досі ще не відвіданою точкою V

3. Зробити точку V поточною

4. Позначити точку V, як відвідану

5. Коли всі точки розмірності N відвідані, припинити пошук маршруту

6. Перейти до другого кроку

Алгоритм простий у реалізації, швидко виконується, але, як і інші «жадібні» алгоритми, може видавати неоптимальні рішення. Обчислювальна складність алгоритму – O(n2). Результатом виконання алгоритму найближчого сусіда є маршрут, приблизно на 25% довший від оптимального. Одним з евристичних критеріїв оцінки рішення є правило: якщо шлях, пройдений на останніх кроках алгоритму, зіставний зі шляхом, пройденим на початкових кроках, то можна умовно вважати знайдений маршрут прийнятним, інакше, імовірно, існують кращі рішення. Інший варіант оцінки рішення полягає у використанні алгоритму нижньої граничної оцінки. Другий критерій оцінки рішення полягає в застосуванні алгоритму нижньої граничної оцінки. Для будь-якої кількості міст більшій за три в задачі комівояжера можна підібрати таке розташування міст (значення відстаней між вершинами графа і вказівка початкової вершини), що алгоритм найближчого сусіда буде видавати найгірше рішення. Метод Байєса - це простий класифікатор, заснований на імовірнісній моделі, що має сильне припущення незалежності компонент вектора ознак. Метод Байєса - це простий класифікатор, заснований на імовірнісній моделі, що має сильне припущення незалежності компонент вектора ознак. Розуміється, метод Байєса має недоліки: великий обсяг попередньою інформацією, «пригнічення» рідко зустрічаються діагнозів та ін. Однак у випадках, коли обсяг статистичних даних дозволяє застосувати метод Байєса, його доцільно використовувати як один з найбільш надійних і ефективних методів. Метод заснований на простій формулі Байєса. Якщо є стан (діагноз) D_i і проста ознака k_j, що зустрічається при цьому діагнозі, то ймовірність спільного появи подій (наявність у об'єкта стану D_i і ознаки k_j) P(D_ik_j) = P(D_i)P(k_j/D_i) = P(k_j)P(D_i/k_j). З цієї рівності випливає формула Байєса P(D_i/k_j) = P(D_i)P(k_i/D_i)/P (k_j). Дуже важливо визначити точний зміст всіх вхідних в цю формулу величин. P(D_i) - ймовірність діагнозу D_i, обумовлена ​​за статистичними даними (апріорна ймовірність діагнозу). Так, якщо попередньо обстежено N об'єктів і у N_i об'єктів малося стан D_i, то P(D_i) = N_i/N. P(k_j/D_i) - ймовірність появи ознаки k_j у об'єктів зі станом D_i. Якщо серед N_i об'єктів, що мають діагноз D_i, у N_ij проявився ознака k_j, то P(k_j/D_i) = N_ij/N_i. P(k_j) - ймовірність появи ознаки k_j у всіх об'єктах незалежно від стану (діагнозу) об'єкта. Нехай із загального числа N об'єктів ознака k_j був виявлений у N_j об'єктів, тоді P(k_j) = N_j/N. Для встановлення діагнозу спеціальне обчислення P(k_j) не потрібно. Як буде ясно з подальшого, значення P(D_i) і P(k_j/D_i), відомі для всіх можливих станів, визначають величину P(k_j).