Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Конспект лекцій з дисципліни «Методи обробки та візуалізації багатовимірних даних»

Скачати 168.14 Kb.

Конспект лекцій з дисципліни «Методи обробки та візуалізації багатовимірних даних»




Скачати 168.14 Kb.
Дата конвертації07.04.2017
Розмір168.14 Kb.
ТипКонспект


Міністерство освіти і науки України

Дніпропетровський національний університет імені Олеся Гончара

Факультет прикладної математики

Кафедра математичного забезпечення ЕОМ



ОПОРНИЙ КОНСПЕКТ ЛЕКЦІЙ



з дисципліни «Методи обробки та візуалізації багатовимірних даних»

Напрям підготовки 6.

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

Математичне забезпечення (mathematical support) - сукупність методів, правил, математичних моделей і алгоритмів розв'язання задач;

040301 – Прикладна математика


Укладач: доц. каф. МЗ ЕОМ,

к.т.н. Мацуга О.М.

Дніпропетровськ

2013

ТЕЗИСНИЙ КОНСПЕКТ ЛЕКЦІЙ
Модуль 1.

Змістовий модуль І. Кластерний аналіз.
Тема 1. Основні поняття теорії розпізнавання образів.

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

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

Класифікація та кластерний аналіз.

Феномен розпізнавання як властивість живих організмів.

Приклади застосування теорії розпізнавання образів.

Поняття класу, образу.

Об’єкт та ознаки. Типи ознак: кількісні, якісні, порядкові, номінальні. Геометрична інтерпретація об’єкта.

Гіпотеза компактності.

Постановки задач розпізнавання образів: з навчанням та без навчання. Класифікація як задача розпізнавання образів із навчанням.

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

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

Кластерний аналіз як задача розпізнавання образів без навчання.
Питання до студентів:

  1. У чому полягає задача розпізнавання образів?

  2. Дати визначення образу, класу та об’єкта.

  3. Які типи ознак ви знаєте?

  4. Сформулювати гіпотезу компактності.

  5. Схарактеризувати постановки задач розпізнавання образів?

  6. Які методи застосовуються для розв’язання кожної з задач розпізнавання образів?



Тема 2. Ієрархічні алгоритми кластеризації.

Постановка задачі кластерного аналізу.

Відстань між об’єктами та між кластерами.

Проблема перетворення даних.

Агломеративні та дивізимні ієрархічні алгоритми.

Агломеративні алгоритми: формула Ланса-Вильямса, алгоритм, властивості монотонності, стискування/розтягування, редуктивності, алгоритм кластеризації, алгоритм побудови дендрограми.


Питання до студентів:

  1. У чому полягає задача кластеризації?

  2. Як визначають однорідність об’єктів спостережень?

  3. Що називають метрикою відстані?

  4. У який спосіб обчислюють відстань Мінковського? Які відстані є її окремими випадками?

  5. Як пов’язані між собою відстані евклідова та Махаланобіса?

  6. Як і з якою метою здійснюють стандартизацію даних?

  7. Яка ідея алгомеративних та дивізімних ієрархічних методів кластерного аналізу?

  8. Навести формулу Ланса–Уільямса.

  9. У чому полягає агломеративний метод найближчого сусіда?

    Відстань Мінковського - це метрика на Евклідовому просторі, яка є узагальненням Евклідового простору та Мангетенської відстані.

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



  10. Які параметри формули Ланса–Уільямса для агломеративного методу найвіддаленішого сусіда?

  11. Як обчислюють відстань між кластерами в агломеративному методі Уорда?

  12. Прокоментувати переваги та недоліки алгомеративних методів кластерного аналізу.

  13. Що таке дендрограмма?

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

  15. Що таке редуктивна властивість? Які метрики мають дану властивість?



Тема 3. Алгоритм К-середніх.

Варіанти алгоритму К-середніх Болла–Холла та Мак-Кіна: ідея, алгоритм, переваги та недоліки.


Питання до студентів:

  1. Яка різниця між варіантами методу К-середніх Мак-Кіна та Болла–Холла?

  2. Навести обчислювальну процедуру методу К-середніх у варіанті Мак-Кіна.

  3. Охарактеризувати переваги та недоліки методу К-середніх.



Тема 4. Алгоритми родини FOREL.

Алгоритми FOREL та FOREL2: ідея, алгоритм.


Питання до студентів:

  1. Навести базовий алгоритм FOREL.

  2. Як за допомогою алгоритму FOREL одержати задану кількість кластерів?

  3. Навести обчислювальну процедуру алгоритму FOREL2.

  4. Які за формою кластери дозволяє одержувати алгоритм FOREL?



Тема 5. Графові алгоритми кластеризації.

Графові алгоритми кластеризації: коротший незамкнений шлях, KRAB. Алгоритм побудови коротшого незамкненого шляху.


Питання до студентів:

  1. У чому суть графових алгоритмів кластеризації? Які їх переваги?

  2. Що називають коротшим незамкненим шляхом?

  3. Навести алгоритм побудови коротшого незамкненого шляху.

  4. У чому полягає алгоритм KRAB?

  5. Як в алгоритмі KRAB обчислюється відстань між кластерами?

  6. Як в алгоритмі KRAB обчислюється міра близькості об’єктів всередині кластера?

  7. Як в алгоритмі KRAB обчислюється міра неоднорідності на межах кластерів?

  8. Який вигляд має функціонал якості в алгоритмі KRAB?



Тема 6. Функціонали якості кластеризації.

Функціонали якості кластеризації. Вибір кількості кластерів.


Питання до студентів:

  1. Як оцінюють якість кластеризації?

  2. Які функціонали якості ви знаєте?

  3. У який спосіб оцінюють потрібну кількість кластерів?



Тема 7. Статистичні алгоритми кластеризації.

Модель суміші розподілів. Суміш нормальних розподілів. ЕМ алгоритм. SЕМ алгоритм. Критерій зупинки. Вибір початкового наближення оцінок параметрів. Вибір кількості компонентів суміші у SЕМ алгоритмі.


Питання до студентів:

  1. Який вигляд має функція щільності суміші розподілів?

  2. Як формулюється задача кластеризації в термінах математичної статистики?

    Густина імовірності - один із способів завдання ймовірнісної міри на евклідовому просторі R n ^} . У випадку, коли імовірнісна міра є розподілом випадкової величини, говорять про щільність випадкової величини.

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



  3. З яких кроків складається ЕМ алгоритм? У чому їх суть?

  4. Для яких даних реалізується ЕМ алгоритм?

  5. Який критерій зупинки у ЕМ алгоритмі?

  6. Які недоліки ЕМ алгоритму та способи їх подолання?

  7. У чому відмінність SЕМ від ЕМ алгоритму?

  8. Як за допомогою SЕМ алгоритму оцінити кількість кластерів?



Тема 8. Алгоритми нечіткої кластеризації.

Поняття нечіткої множини. Нечіткість у задачі кластеризації. Алгоритм нечітких К-середніх. Алгоритм Густафсона-Кесселя.


Питання до студентів:

  1. Яку множину називають нечіткою?

  2. Хто є розробник теорії нечітких множин?

  3. Що за нечіткість має місце у задачі кластеризації?

  4. Який вигляд має функціонал Беждека-Данна? На що впливають сталі у даному функціоналі? Які їх рекомендовані знчення?

  5. У чому полягає алгоритм FCM?

  6. У чому полягає алгоритм Густафсона-Кесселя?

Модуль 2.

Змістовий модуль І. Класифікація.
Тема 1. Постановка задачі класифікації.

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

Перевірка якості класифікації
.

Постановка задачі класифікації.

Проблема навчання в задачі класифікації, геометрична картина навчання.

Перевірка якості класифікації: розбиття навчаючої вибірки на дві частини, метод ковзного контролю.

Метричні та статистичні методи класифікації.

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

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


Питання до студентів:

  1. У чому полягає задача класифікації?

  2. Що таке якість класифікації?

  3. Що називають надійністю класифікації?

  4. З яких етапів складається розв’язання задачі класифікації?

  5. Яка різниця між метричними та статистичними методами класифікації?

  6. Як оцінюють якість класифікації?



Тема 2. Метод найближчих сусідів та його модифікації.

Метод найближчих сусідів (NN), модифікований метод найближчих сусідів, метод k найближчих сусідів (kNN).


Питання до студентів:

  1. У чому полягає метод NN?

  2. Навести обчислювальну процедуру модифікованого методу NN.

  3. У чому полягає метод kNN?

  4. Яким чином слід обирати параметр k у методі kNN?

  5. У чому полягає етап навчання в методі NN та його модифікаціях?



Тема 3. Методи еталонів.

Поняття еталону.

Метод на основі порівняння з еталоном.

Метод ДРЕТ.


Питання до студентів:

  1. Що таке еталон?

  2. У чому полягає етап навчання в методі еталонів?

  3. У чому полягає метод ДРЕТ?



Тема 4. Метод потенціальних функцій.

Метод потенціальних функцій. Вибір потенціальної функції. Алгоритм методу, геометрична інтерпретація.


Питання до студентів:

  1. Який вигляд має потенціальна функція?

  2. Як здійснюється навчання у методі потенціальних функцій?

  3. Яка геометрична інтерпретація етапу навчання в методі потенціальних функцій?



Тема 5. Метод опорних векторів.

Поняття оптимальної гіперплощини в методі опорних векторів.

Побудова оптимальної гіперплощини для класів, що лінійно подільні.

Побудова оптимальної гіперплощини для класів, що лінійно неподільні.

Побудова нелінійної подільної поверхні. Ядро скалярного добутку.
Питання до студентів:


  1. Яку гіперплощину називають оптимальною?

  2. Що таке опорний вектор?

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

  4. Записати функцію Лагранжа для пошуку оптимальної гіперплощини.

    Скалярний добуток (англ. dot product, англ. scalar product, нім. Skalarprodukt, рос. скалярное произведение) - бінарна операція над векторами, результатом якої є скаляр.

    Функція Лагранжа L [ φ i ] }[\varphi _]} фізичної системи - функція узагальнених координат φ i ( s ) (s)} , що використовується у фізиці для побудови через певний варіаційний принцип рівнянь руху, які описують еволюцію фізичної системи.



  5. Як побудувати нелінійну подільну поверхню?

  6. Які ядра скалярного добутку можуть застосовуватися в методі опорних векторів?



Тема 6. Дерева розв’язків у задачі класифікації.

Основні поняття теорії дерев розв’язків.

Застосування дерев розв’язків у задачі класифікації.

Базова процедура побудови дерева розв’язків.

Алгоритми C4.5 та CART.
Питання до студентів:


  1. Що таке дерево розв’язків?

  2. Як відбувається класифікація нових об’єктів за допомогою дерева розв’язків?

  3. Сформулювати загальну процедуру побудови дерева розв’язків.

  4. Які критерії зупинки побудови дерева розв’язків застосовуються?

  5. Що таке відсікання гілок та як воно здійснюється?

  6. Які критерії вибору ознаки для побудови чергового вузла застосовують в алгоритмах C4.5 та CART? Які їх недоліки? Як їх можна модифікувати?

  7. Як побудувати вузол перевірки на основі кількісної ознаки?

  8. Як здійснюється обробка відсутніх значень в алгоритмі C4.5?

  9. Схарактеризувати переваги та недоліки алгоритму C4.5.

  10. Яке значення має абревіатура CART?

  11. Які дерева дозволяє будувати алгоритм CART?

  12. Як здійснюється обробка відсутніх значень в алгоритмі CART?

  13. Який механізм для відсікання дерева застосовується в алгоритмі CART?

  14. Схарактеризувати переваги та недоліки алгоритму CART.



Тема 7. Ансамблі класифікаторів.

Поняття ансамблю класифікаторів.

Boosting. Поняття слабкого та сильного класифікаторів. Еквівалентність слабкого та сильного класифікаторів. Алгоритми Boost1 та AdaBoost.

Поняття bootstrap-вибірки. Алгоритм Bagging.


Питання до студентів:

  1. Що називають ансамблем класифікаторів?

  2. Які методики побудови ансамблів ви знаєте?

  3. Які класифікатори називають слабкими та сильними?

  4. Що означає еквівалентність слабкого та сильного класифікаторів?

  5. Сформулювати алгоритми Boost1 та AdaBoost.

  6. Що таке bootstrap-вибірка?

  7. Сформулювати алгоритм Bagging.



Змістовий модуль ІІ. Статистичні методи класифікації.
Тема 1. Імовірнісна постановка задачі класифікації. Байєсівське вирішальне правило. Ймовірності помилок.

Імовірнісна постановка задачі класифікації та принцип максимуму правдоподібності.

Функціонал середнього ризику.

Оптимальність баєсівського вирішального правила.

Ймовірності помилок І та ІІ роду, інтеграли помилок.
Питання до студентів:


  1. Яке вирішальне правило називають оптимальним?

  2. Сформулювати баєсівське вирішальне правило.

  3. Які таке помилки І та ІІ роду?

  4. Довести, що баєсівське вирішальне правило є оптимальне.

  5. Що таке дискримінантна функція?



Тема 2. Баєсівське вирішальне правило для нормального розподілу. Параметричне оцінювання функції щільності.

Параметричне оцінювання щільності ймовірностей.

Нормальний дискримінантний аналіз. Оцінка параметрів нормального розподілу за методом максимальної правдоподібності. Геометрична інтерпретація.

Лінійні та квадратичні розділяючі поверхні.


Питання до студентів:

  1. Навести функцію щільності багатовимірного нормального розподілу.

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

    Багатовимірний нормальний розподіл (чи багатовимірний гаусів розподіл) у теорії ймовірностей - це узагальнення одновимірного нормального розподілу.



  2. Одержати дискримінантну функцію для випадку нормального розподілу.

  3. Який вигляд має дискримінантна функція, коли кожен клас описується нормальним розподілом з однаковими коваріаційним матрицями?



Тема 3. RBF-мережа.

Мережі радіальних базисних функцій (RBF) та їх налаштування за допомогою ЕМ-алгоритму або SЕМ-алгоритму.


Питання до студентів:

  1. Що таке радіальна функція?

  2. Яка структура RBF мережі?

  3. Як здійснюються налаштування RBF мережі?



Змістовий ІІІ. Мінімізація простору ознак.
Тема 1. Постановка задачі. Методи відбору інформативних ознак.

Проблема розмірності у задача розпізнавання образів.

Поняття інформативності ознак. Залежні та незалежні ознаки.

Методи відбору інформативних ознак: апроксимації матриці відстаней, Кендалла, гойдалки, голосування.

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

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


Питання до студентів:

  1. Що розуміють під мінімізацією простору ознак?

  2. Які ознаки називають інформативними?

  3. Схарактеризувати метод апроксимації матриці відстаней (Кендалла, гойдалки, голосування).

  4. Навести алгоритм методу послідовного додавання ознак (послідовного скорочення ознак, випадкового пошуку, випадкового пошуку з адаптацією).



Тема 2. Багатовимірне шкалювання.

Постановка задачі багатовимірного шкалювання.

Метричне шкалювання.

Неметричне шкалювання.

Критерії стресу. Мінімізація критеріїв стресу.
Питання до студентів:


  1. Сформулювати задачу багатовимірного шкалювання.

  2. Чим відрізняються метричне та неметричне шкалювання?

  3. Який вигляд має критерій стресу під час метричного шкалювання? А під час неметричного шкалювання?

  4. У який спосіб розв’язується задача шкалювання?

  5. Що таке діаграма Шепарда?



Тема 3. Компонентний та факторний аналіз.

Постановка задачі компонентного аналізу.

Геометрична інтерпретація головних компонентів.

Модель компонентного аналізу.

Метод головних компонентів (МГК).

Модель факторного аналізу.

Постановка задачі розвідницького факторного аналізу.

Методи оцінки загальності.

Обчислювальні схеми факторного аналізу.

Оцінка кількості загальних факторів.



Обертання факторів.
Питання до студентів:

  1. Що розуміють під мінімізацією простору ознак?

  2. Які ознаки називають інформативними?

  3. Схарактеризувати метод апроксимації матриці відстаней (Кендалла, гойдалки, голосування).

  4. Записати головні компоненти як комбінації початкових ознак.

  5. Яким співвідношенням пов’язані дисперсії початкових ознак та головних компонент?

  6. Записати зворотне перетворення для визначення вихідних даних через головні компоненти.

  7. Сформулювати обчислювальну процедуру методу головних компонент.

  8. Чому дорівнює сума власних чисел кореляційної матриці?

  9. Який відсоток дисперсії k-ої вихідної ознаки xk пояснюється першими w головними компонентами?

  10. Сформулювати постановку задачі розвідницького факторного аналізу.

  11. Дати інтерпретацію матриці факторного відображення.

  12. Яке пояснення має дисперсія k-ої вихідної ознаки xk при реалізації моделі факторного аналізу?

  13. Який загальний внесок v-го загального фактора у підсумкову дисперсію параметра xk?

  14. Чому дорівнює повний внесок усіх загальних факторів у загальну дисперсію багатовимірної вибірки?

  15. Дати визначення загальності, характерності та редукційної матриці.

  16. Сформулювати математичну постановку задачі розвідницького факторного аналізу.

  17. Навести приклади проведення оцінки загальності.

  18. Як оцінюють кількість загальних факторів?

  19. Сформулювати обчислювальну процедуру методу головних факторів.

  20. Як і з якої метою здійснюють обертання факторів?

  21. Що таке проста структура?

  22. Які методи обертання застосовуються?


МІНІ-ЛЕКСИКОН

Агломеративна кластеризація – див. ієрархічна кластерзація.

Алгоритм C4.5 – удосконалена версія алгоритму побудови дерева розв’язків ID3, в який додані можливості роботи з пропущеними даними, вдосконалений критерій розбиття дерева, запропонований механізм видобування та спрощення правил. Він також містить евристичні методи для оптимізації структури дерев розв’язків (відсікання гілок) без втрати якості розпізнавання. Розроблений Р. Куинленом.

Алгоритм CART – один з популярних алгоритмів побудови дерева розв’язків, запропонований в 1984 р. Абревіатура CART означає Classification and Regression Tree – дерево класифікації та регресії. Алгоритм будує бінарні дерева класифікації, які містять лише двох нащадків в кожному вузлі.

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

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

Алгоритм ID3 – один з найбільш ранніх алгоритмів навчання дерева розв’язків (1992 р.), що використовує рекурсивне розбиття підмножин у вузлах дерева за одним з обраних атрибутів.

Атрибут – ознака, що характеризує певну властивість досліджуваного об’єкта або процесу.

Ансамбль класифікаторів – набір класифікаторів, що використовуються для розв’язання єдиної задачі. Існують дві основні методики побудови ансамблів – бустінг та беггінг.

Байеса класифікатор – класифікатор, який дозволяє визначити імовірність належності об’єктів до одного з класів. Теоретично, Байеса класифікатор є оптимальний, тобто забезпечує мінімальну імовірність помилки класифікації.

Баєсівське вирішальне правило – те саме, що і Байеса класифікатор.

Беггінг (Bagging) – метод формування ансамблю класифікаторів з використанням випадкової вибірки з поверненням або бутстрепа.

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

Назва методу пройшла від англ.
Bootstrap AggregatINGbagging. Метод був запропонований у 1994 році Лео Брейманом.

Бустінг (Boosting) – метод формування ансамблю класифікаторів шляхом «підсилення» «слабких» класифікаторів. Ідея бустінга була запропонована Робертом Шапейре наприкінці 80-х років. В її основі лежить побудова ланцюжка (ансамблю) класифікаторів, кожен з яких (окрім перового) навчається на помилках попереднього, тобто об’єктах, на яких попередній класифікатор допустив помилку.


Бутстреп (Bootstrap) – метод формування декількох вибірок даних того ж розміру, що і початкова, але з різними розподілами величини, яка цікавить. Був запропонований у 1977 році Б. Ефроном. Те саме, що вибірка з поверненням, вибірка з заміщенням.

Вирішальне правило – правло вигляду «Якщо …, то …», яке дозволяє приймати рішення щодо належності об’єкта до одного з класів.

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

Вузол дерева розв’язків – структурний елемент дерева розв’язків, в якому знаходиться вирішальне правило вигляду «Якщо …, то …» і з яким асоціюється деяка множина об’єктів.


Дендрограмма – графічне зображення ієрархічної структури даних;

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

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

Дерево розв’язків – це класифікатор у вигляді дерева, одержаний з навчаючої множини.

Дивізійна кластеризація – див. ієрархічна кластерзація.

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

Ентропія – поняття міри інформації, введену в статистику Клодом Шенноном.

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


Інформативні ознаки – ознаки, одержані в результаті мінімізації простору ознак.

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

Класифікація – задача розбиття множини об’єктів на групи, які називаються класами.

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

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

Кластеризація – це є розбиття множини об’єктів на однорідні підмножини за схожістю опису ознак об’єктів. Одержані підмножини називають кластерами. Набір кластерів заздалегідь невідомий.

Метод k-найближчих сусідів (k-nearest neighbor) – метод розв’язання задачі класифікації, який відносить об’єкт до класу, до якого належить більшість з його k найближчих сусідів.


Метод К-середніх (С-means) – найбільш поширений серед неієрархічних методів кластеризації. Для його роботи попередньо необхідно задавати кількість кластерів . Існує у двох варіантах: Болла–Холла та Мак-Кіна.

Метод опорних векторів (Support vector machines) – алгоритм класифікації, що використовує лінійний поділ об’єктів у просторі ознак за допомогою гіперплощини.

В розпізнаванні образів та машинному навчанні ве́ктор озна́к (англ. feature vector) - це n-вимірний вектор числових ознак, що представляють певний об'єкт. Багато алгоритмів у машинному навчанні вимагають чисельного представлення об'єктів, оскільки такі представлення полегшують обробку та статистичний аналіз.

В машинному навчанні ме́тод опо́рних векторі́в (рос. метод опорных векторов) - це метод аналізу даних для класифікації та регресійного аналізу за допомогою моделей з керованим навчанням з пов'язаними алгоритмами навчання, які називаються опо́рно-ве́кторними маши́нами (ОВМ, англ. support vector machines, SVM, також опо́рно-ве́кторними мере́жами, англ. support vector networks)

Метод використовується для розв’язання задачі бінарної класифікації.

Бінарнарна класифікація - клас задач класифікації елементів набору даних на дві групи на підставі правила класифікації.

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


Метрика відстані – це невід’ємна функція , що задовольняє умовам: 1) невід’ємності: для ; 2) максимальної схожості об’єкта із самим собою: , коли ; 3) симетрії: для ; 4) нерівності трикутника: для .

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

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


Образ – те саме, що і клас.

Об’єкт – предмет, явище, сигнал, на який направлена певна діяльність і який є предметом пізнання.


Ознака – те саме, що атрибут.

Прецедент – об’єкт, для якого відомий клас, до якого він належить.

Розпізнаванням образів – процес віднесення деякого об’єкту (предмета, явища, ситуації, сигналу) до певного образу (або класу).

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


Функціонал якості кластеризації – кількісний критерій, що дозволяє віддати перевагу одному із розбиттів.



Скачати 168.14 Kb.

  • Агломеративна кластеризація – див. ієрархічна кластерзація.
  • Атрибут – ознака, що характеризує певну властивість досліджуваного об’єкта або процесу.
  • Баєсівське вирішальне правило – те саме, що і Б
  • Дивізійна кластеризація – див. ієрархічна кластерзація.
  • Ентропія – поняття міри інформації, введену в статистику Клодом Шенноном.
  • Об’єкт – предмет, явище, сигнал, на який направлена певна діяльність і який є предметом пізнання.