Алгоритми інтелектуального аналізу даних


Дізнайтесь більше про нові кар'єрні можливості в EchoUA. Цікаві проекти, ринкова оплата, гарний колектив. Надсилайте резюме та приєднуйтеся до нас.

Розповідає Рей Ли, автор блогу raily.net


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

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

Давайте почнемо!

1. C4.5

Що він робить? C4.5 створює класифікатор у вигляді дерева рішень. Для цього C4.5 дається набір даних, що є вже класифікованими речами.

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

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

Отже:

Враховуючи ці атрибути, ми хочемо передбачити, чи захворіє пацієнт раком. Пацієнт може потрапити в один з двох класів: “захворіє раком” і “не захворіє раком”. Ми повідомляємо C4.5 про відповідний клас кожного пацієнта.

Справа ось в чому:

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

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

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

Підсумок:

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

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

Так чим же С4.5 відрізняється від інших систем дерев рішень?

Чому варто спробувати С4.5? Мабуть, головною перевагою дерев рішень є простота їх розуміння і пояснення. Вони також досить швидкі, дуже поширені і їх виведення легкий для читання для людини.

Де його використовують? Популярну відкриту Java- реалізацію можна знайти на OpenTox. Orange, загальнодоступна програма для візуалізації і аналізу даних використовує С4.5 у своєму класифікаторові дерев рішень.

Класифікатори – це, звичайно, здорово, але все таки вам варто прочитати про наступний алгоритм і кластерний аналіз.

2. k – means

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

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

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

Дивіться:

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

Ви, напевно, ставите питання:

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

Хочете упізнати кращу властивість k – means?

Ви лише задаєте кількість потрібних вам кластерів. K – means піклується про усе інше.

Як же k – means піклується про усе інше? У k – means є багато варіацій для оптимізації певних типів даних.

Не вдаючись до подробиць, це відбувається приблизно так:

  • k – means вибирає точки у багатовимірному просторі для кожного з k кластерів. Їх називають центроїдами.
  • Кожен з пацієнтів буде ближчий всього до одного з цих центроїдів. Швидше за все, не усі з них будуть ближчі всього до одного і тому ж центроїда, так що сформується декілька кластерів навколо відповідних центроїдів.
  • У нас тепер є k кількість кластерів, і кожен з пацієнтів належить до одного з них.
  • k – means після цього знаходить центр кожного кластера, спираючись на членів цих кластерів (використовуючи вектори характеристик пацієнтів).
  • Цей центр стає новим центроїдом кластера.
  • Оскільки центроїд тепер у іншому місці, пацієнти можуть виявитися ближче до іншого центроїда. Іншими словами, вони можуть перейти в інший кластер.
  • Кроки 2-6 повторюються до тих пір, поки центроїди більше не змінюються. Це називається конвергенцією.

Це навчання з учителем або без? Більшість рахують k – means самонавчальним алгоритмом. Окрім вказівки кількості кластерів, k – means ” дізнається” кластери сам по собі, без якої-небудь інформації про те, до якого кластера належить та або інша ознака. K – means може, проте, бути напівконтрольованим.

Чому варто спробувати k – means? Мені здається, це зрозуміло.

Головною перевагою k – means являється його простота. Те, що він простий в реалізації, означає, що він зазвичай швидше і ефективніше за інші алгоритми, особливо при роботі з великим набором даних.

До того ж, k – means можна використати для попереднього кластерного аналізу величезних наборів даних, щоб потім скористатися більше витратним алгоритмом кластерного аналізу на самих кластерах. K – means також може вивчати упущені зв’язки в наборі даних шляхом різкої зміни k.

Але не все так веселково:

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

Де він використовується? Величезна кількість реалізацій k – means доступні в мережі:

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

3. Метод опорних векторів

Що він робить? Метод опорних векторів (SVM) знаходить гіперплощину для класифікації даних в два класи. Двома словами, SVM виконує завдання, аналогічну C4.5, за винятком того, що він не використовує дерева рішень.

Почекайте, гипер-что? Гіперплощина – це функція, приміром, як лінійне рівняння у = kх + b. Для простого завдання з класифікації, де є тільки дві властивості, гіперплощина може бути лінією.

Як з’ясовується.

SVM може спроектувати ваші дані у більш високі виміри. А після цього.

. SVM знаходить найбільш відповідну гіперплощину, що розділяє ваші дані в два класи.

Можна приклад? Зрозуміло. Представимо декілька червоних і синіх куль на столі. Якщо кулі не занадто сильно перемішані, ви можете покласти між ними палицю, не рухаючи самих куль.

Як бачите :

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

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

А знаєте, що в цьому найчудовіше?

Те, що SVM сам з’ясовує функцію гіперплощини.

А що, якщо все ускладнити? Якщо кулі перемішані між собою, пряма палиця не спрацює.

Ось обхідне рішення:

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

А це хіба не шахрайство?

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

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

Мені це допомогла зрозуміти наступна візуалізація:

На Reddit теж є два чудові пояснення на ELI5 і ML.

Як же кулі на столі або в повітрі співвідносяться з реальними даними? У кулі на столі є місце розташування, яке можна визначити за допомогою координат. Наприклад, куля може лежати на 20 см від лівого краю і 50 см від нижнього краю. Іншими словами, куля знаходиться у (x, y) координат, або (20, 50). x і y – два виміри цієї кулі.

Справа ось в чому:

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

У результаті:

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

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

Головне:

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

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

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

Чому варто використати саме SVM? SVM і C4.5 – два класифікатори, які варто спробувати в першу чергу. Немає класифікатора, ідеального в усіх сенсах із-за теореми No Free Lunch. Крім того, іншими недоліками алгоритму є вибір ядра і інтерпретується.

Де він використовується? Існує досить багато реалізацій SVM. Найвідомішими з них є scikit – learn, MATLAB і, звичайно же, libsvm.

Наступний алгоритм – один з моїх коханих.

4. Apriori

Що він робить? Алгоритм Apriori шукає асоціативні правила і застосують їх до бази даних, що містить велику кількість транзакцій.

Що таке асоціативні правила? Пошук асоціативних правил – це метод витягання даних для вивчення кореляцій і взаємозв’язку між змінними у базі даних.

Наведіть приклад Apriori. Уявимо, що у нас є база даних, повна транзакцій одного супермаркету. Можна думати про базу даних, як про велетенську таблицю, де кожен рядок – транзакція клієнта, а кожен стовпець є різним продуктом.

Краща новина така:

Застосовуючи Apriori, ми можемо дізнатися про те, які продукти отримуються разом, тобто про асоціативні правила.

Тобто, ви можете знайти ті товари, які купують разом частіше, ніж інші. Разом вони називаються елементами набору. Кінцевою метою є збільшення кількості покупок.

Приміром:

Номер Транзакції

Чіпси

Соус

Газована вода

Яблука

Молоко

1

Х

Х

Х

2

Х

Х

Х

3

Х

Х

Ви швидше за все розумієте, що чіпси і газовану воду часто купують разом. Їх називають 2-елементним набором. При досить великому наборі даних буде складніший побачити такі взаємовідносини, особливо якщо ви маєте справу з 3-елементними наборами і більше. Це саме те, в чому вам може допомогти Apriori!

Як же працює Apriori? Перед тим, як розібратися в основі алгоритму, вам треба визначитися з трьома пунктами:

  1. Розмір вашого елементного набору.
  2. Підтримка, чи кількість транзакцій, в яких зустрічається цей елементний набір, що ділиться на загальну кількість транзакцій. Елементний набір, чия підтримка більше або дорівнює мінімальній підтримці, називається частим елементним набором.
  3. Достовірність, чи умовна вірогідність того, як часто деякий елемент зустрічається у вашому елементному наборі, при наявність в нім іншого певного елементу. Приміром, якщо в елементному наборі є чіпси, то з достовірністю 67% там також є і газований напій.

У основі Apriori 3 етапи:

  1. Об’єднання. Сканування усієї бази даних, щоб визначити, як часто зустрічаються 1-елементні набори.
  2. Скорочення. Ці елементні набори, що задовольняють підтримку і достовірність, проходять в наступний раунд для 2-елементних наборів.
  3. Повтор. Ця послідовність повторюється для кожного елементного набору, поки не досягнутий визначений раніше розмір.

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

Але почекайте, це ще не усе.

Apriori можна модифікувати, щоб класифікувати на основі потрібних даних.

Чому варто використати Apriori? Apriori легко зрозуміти, реалізувати, і у нього є безліч похідних.

З іншого боку.

Алгоритм може бути досить вимогливий по відношенню до пам’яті і часу генерації елементних наборів.

Де його використовують? Apriori досить часто зустрічається. Деякими з найвідоміших застосувань є ARtool, Weka, і Orange.

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

5.EM

Що він робить? У витяганні даних EM найчастіше використовується як алгоритм кластеризації (як k – means) для виявлення знань.

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

Давайте я поясню.

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

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

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

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

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

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

Повертаючись до сценарію іспиту, розподіл оцінок за іспит (вимірні результати) відповідав кривій нормального розподілу. Середнє значення – 85, дисперсія – 100 .

Щоб охарактеризувати нормальний розподіл потрібні наступні два параметри:

  1. середнє значення,
  2. дисперсія.

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

Справа ось в чому:

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

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

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

Вам, напевно, цікаво, чим же тоді являється вірогідність?

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

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

Здорово! Тоді в чому різниця між спостережуваними і неспостережуваними даними? Спостережувані дані – це дані, які у вас є. Неспостережуваних даних – це не вистачає дані. Даних може не бути з багатьох причин (не враховані, проігноровані і так далі).

Сіль ось в чому:

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

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

Краще всього, що.

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

Як же EM допомагає з кластеризацією? EM розпочинає з вгадування параметрів моделі.

Потім він вступає в наступний ітеративний трьохкроковий процес:

  1. E- етап: на підставі параметрів моделі обчислюється вірогідність для привласнення значень кожної точки даних до кластера.
  2. M- етап: оновлюються параметри моделі на підставі кластерних привласнень з попереднього кроку.
  3. Повторювати доки параметри моделі і привласнення кластера стабілізуються (конвергенція).

Це навчання з учителем або без? Оскільки ми не надаємо маркіровану інформацію класу, це навчання без учителя.

Чому варто спробувати EM? Головним достоїнством EM є проста і прямолінійна реалізація. До того ж, він не лише може оптимізувати параметри моделі, але і багаторазово намагається вгадувати не вистачає дані.

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

У EM все ж є недоліки.

  • EM швидкий на ранніх ітераціях, але стає повільніше в подальших.
  • EM не завжди знаходить оптимальні параметри і застряє в локальному оптимумі, а не в глобальному оптимумі.

Де він використовується? Алгоритм EM доступний в Weka. У R є реалізація в пакеті mclust. scikit – learn також використовує його в модулі gmm.

Який метод здобичі даних використовує Google? Давайте подивимося.

6.PageRank

Що він робить? PageRank є алгоритмом посилального ранжирування, розробленим для визначення відносної ” важливості” якого-небудь об’єкту в мережі об’єктів.

Мда. Що таке посилальне ранжирування? Це тип аналізу мереж, що досліджує зв’язки (посилання) між об’єктами.

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

Дозвольте пояснити:

Веб-сторінки у всесвітній павутині посилаються один на одного. Якщо на tproger.ru є посилання на CNN, йому нараховується ” голос”, що означає, що tproger.ru вважає веб-сторінку CNN актуальною.

Але це не усе

Голоси tproger.ru у свою чергу міряються по авторитетності і актуальності самого tproger.ru. Іншими словами, будь-яка веб-сторінка, що проголосувала за tproger.ru, підвищує його актуальність.

Підсумок?

Така концепція голосування і актуальності і є PageRank. Голос tproger.ru за CNN збільшує PageRank CNN, і авторитетність tproger.ru впливає на те, як сильно цей голос впливає на PageRank CNN.

Що означає PageRank 0, 1, 2, 3 і так далі? Хоча точне значення числа PageRank Google не розголошує, ми можемо отримати уявлення про його зразкове значення.

Ось він і є:

СайтPageRank
twitter.com10
facebook.com9
reddit.com8
stackoverflow.com7
tumblr.com6
crucial.com5
programmingzen.com4
dearblogger.org3

Це щось подібне до рейтингу популярності. У нас у усіх є уявлення про те, які сайти актуальні і популярні. PageRank – це просто дуже елегантний спосіб це визначити.

Де ще застосовується PageRank? PageRank був розроблений спеціально для всесвітньої павутини.

Подумайте, за своєю суттю, PageRank – це просто дуже ефективний спосіб аналізу посилань. Об’єкти, пов’язані один з одним, не зобов’язані бути веб-сторінками.

Ось 3 інноваційні застосування PageRank:

  1. Доктор наук Стефано Аллесина (Dr. Stefano Allesina) з університету Чикаго застосував PageRank до екології, щоб визначити, які види мають вирішальне значення для підтримки екосистеми.
  2. Твиттер розробив WTF (Who – to – Follow, кого-стоит-читать), який по суті є системою рекомендацій PageRank, що персоналізується, про того, кого варто читати в Твиттере.
  3. Бен Цзян (Bin Jiang) з Гонконзького політехнічного університету використав версію PageRank, щоб передбачити швидкість пересування людей в Лондоні на основі топографічних показників.

Це навчання з учителем або без? PageRank, як правило, вважається самонавчальним алгоритмом, оскільки він часто використовується для виявлення важливості і актуальності веб-сторінки.

Чому варто спробувати PageRank? Мабуть, головною перевагою PageRank є його стійкість, бо отримання відповідного посилання, що входить, досить важко.

Простіше кажучи:

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

Де він використовується? Товарний знак PageRank належить Google. Проте, алгоритм насправді запатентований Стенфордским університетом.

Вам напевно цікаво, чи маєте ви право користуватися PageRank.

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

Ось 3 реалізації PageRank:

  1. C++ OpenSource PageRank Implementation
  2. Python PageRank Implementation
  3. igraph – Пакет аналізу мереж (R)

7. AdaBoost

Що він робить? AdaBoost – це алгоритм посилення класифікаторів.

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

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

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

З іншого боку.

У сильного учня точність набагато вища, і часто використовуваним прикладом сильного учня є SVM.

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

Як би нам передбачити, чи отримає пацієнт рак?

От як AdaBoost відповідає на це питання.

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

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

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

У другому раунді: AdaBoost знову намагається знайти кращого учня.

І сіль ось в чому:

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

Чому?

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

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

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

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

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

Чому варто використати AdaBoost? AdaBoost простий. Алгоритм досить легко реалізувати.

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

Ще дещо.

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

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

Де він використовується? У AdaBoost є дуже багато реалізацій і варіацій. Ось декілька з них:

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

8. kNN

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

Що таке ледачий учень? Ледачий учень особливо нічого не робить під час процесу навчання, окрім збереження даних навчання. Цей тип учня класифікує тільки тоді, коли введені нові немаркіровані дані.

З іншого боку, старанний учень будує модель класифікації під час навчання. Коли вводяться нові немаркіровані дані, цей тип учня передає дані в модель класифікації.

Що щодо C4.5, SVM і AdaBoost? Вони усі є старанними учнями.

Ось чому:

  1. C4.5 будує дерево рішень під час навчання.
  2. SVM створює модель класифікації у вигляді гіперплощини під час навчання.
  3. AdaBoost cоздает агрегацію моделей класифікації під час навчання.

Так що ж робить kNN? kNN не створює таких моделей класифікації. Замість цього, він просто зберігає маркіровані дані.

Коли вводяться нові немаркіровані дані, kNN робить ось що:

  1. Спочатку він дивиться на k найближчих маркірованих точок даних. Іншими словами, на k найближчих сусідів.
  2. Потім, використовуючи класи сусідів, kNN отримує краще уявлення про те, як нові дані мають бути класифіковані.

Ви, напевно, ставите наступне питання.

Як kNN з’ясовує, що знаходиться ближче? Для безперервних даних, kNN використовує функцію дистанції, наприклад, дистанцію в просторі Евкліда. Вибір функції дистанції значною мірою залежить від даних. Хтось навіть пропонує визначати функції дистанції, грунтуючись на даних навчання. Є величезна кількість робіт про функцію дистанції kNN.

Ідея в тому, щоб перетворити дискретні дані у безперервні. Ось два приклади:

  1. Використання відстані Хемминга для метрики ” близькості” двох текстових рядків.
  2. Перетворення дискретних даних в двійкові функції.

У цих двох тредах Stack Overflow ви знайдете більше пропозицій для роботи з дискретними даними:

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

Можу посперечатися, що ви можете вгадати, в якому випадку все перестає бути таким простим.

Як же kNN визначає клас, коли у сусідів він різний?

Є два поширені методи для боротьби з цим:

  1. Візьміть просту більшість голосів від сусідів. Той клас, у якого більше голосів, стає класом нової точки даних.
  2. Візьміть голоси, але задайте більшу вагу найближчим сусідам. Найпростіше використати взаємне розташування. Наприклад, якщо сусід знаходиться на відстані п’яти одиниць, то його вага його голосу – 1/5. Чим далі сусід, тим взаємне розташування стає менше і менше. А це саме те, що нам потрібно!

Це навчання з учителем або без учителя? Це навчання з учителем, оскільки kNN надається маркірований набір даних для навчання.

Чому варто використати kNN? Простота в розумінні і реалізації – головні причини для використання kNN. Залежно від функції відстані, kNN може бути досить точним.

Але це лише одна сторона медалі.

Ось п’ять речей, яких варто остерігатися :

  1. kNN може стати дуже витратним в обчисленнях, коли він намагається визначити найближчих сусідів у великому наборі даних.
  2. Неточні дані можуть завадити правильній класифікації.
  3. Властивості з великим діапазоном значень можуть домінувати у функції відстаней відносно характеристик з меншим діапазоном, так що вибір масштабу дуже важливий.
  4. Оскільки обробка даних відкладається, kNN зазвичай вимагає більше місця для зберігання, чим старанні класифікатори.
  5. Вибір відповідної функції відстані має вирішальне значення для точності kNN.

Де він використовується?

Спам? Забудьте про нього! Читайте далі, щоб дізнатися більше про наступний алгоритм.

9.Наївний байесовский класифікатор

Що він робить? Наївний байесовский є не єдиним алгоритмом, а сімейством алгоритмів класифікації, які розділяють одно загальне припущення :

Кожна з властивостей даних, що класифікуються, не залежить від усіх інших властивостей.

Що мається на увазі під незалежним? Дві властивості є незалежними, якщо їх значення не має ніякого впливу на значення іншої властивості.

Приміром:

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

А інші властивості незалежні?

А жалю, немає. Ось три взаємозв’язані властивості:

  • Якщо збільшується зростання, вага ймовірно теж збільшиться.
  • Якщо збільшився рівень холестерину, то вага теж, швидше за все, збільшився.
  • Якщо збільшився рівень холестерину, то пульс теж, швидше за все, збільшився.

По моєму досвіду, властивості набору даних найчастіше не є незалежними.

І це приводить нас до наступного питання.

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

Хто такий Байес? Томас Байес був британським статистиком, на честь якого названа теорема Байеса. Ви можете дізнатися більше о теоремі Байеса тут.

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

Спрощена формула для класифікації виглядає приблизно так:

Давайте трохи заглибимося в це.

Що є ця формула? Ця формула знаходить вірогідність Класу А залежно від властивостей 1 і 2. Іншими словами, якщо ви бачите Властивості 1 і 2, це і є вірогідність того, що дані належать Класу А.

Рівняння свідчить: вірогідність Класу А, враховуючи Властивості 1 і 2, є дробом.

  • Чисельником дробу є вірогідність Властивості 1, в Класі А, помножена на вірогідність Властивості 2 в Класі А, помножену на вірогідність Класу А.
  • Знаменником дробу є вірогідність Властивості 1, помноженої на вірогідність Властивості 2.

Що є прикладом Наївного байесовского класифікатора? Нижче відмінний приклад з Stack Overflow.

Отже:

  • У нас є учбовий набір даних з 1000 фруктів.
  • Фрукт може бути Бананом, Апельсином або Іншим (це наші класи).
  • Фрукт може бути Довгим, Солодким або Жовтим (це наші властивості).

Клас

ДовгийСолодкийЖовтийРазом
Банан400350450500
Апельсин0150300300
Інше10015050200
Разом5006508001000

Що ми бачимо в учбовому наборі даних?

  • з 500 бананів, 400 довгих, 350 солодких і 450 жовтих;
  • з 300 апельсинів, 0 довгих, 150 солодкий і 300 жовтих;
  • з решти 200 фруктів, 100 довгих, 150 солодких і 50 жовтих.

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

Припустимо, ми знаємо, що фрукт довгий, солодкий і жовтий.

От як ми вичислимо усю вірогідність в 4 етапи:

Етап 1: Обчислюємо вірогідність того, що це банан. Це вірогідність класу Банан, враховуючи властивості Довгий, Солодкий і Жовтий, або в лаконічнішій формі:

P (Банан| Довгий, Солодкий, Жовтий)

Це ідентично рівнянню, що обговорювалося раніше.

Етап 2: Починаючи з чисельника, давайте вставимо все у формулу.

  • P (Довгий| Банан) = 400/500 = 0.8
  • P (Солодкий| Банан) = 350/500 = 0.7
  • P (Жовтий| Банан) = 450/500 = 0.9
  • P ( Банан) = 500/1000 = 0.5

Перемноживши все один з одним (як в рівнянні), ми отримуємо:

0.8 х 0.7 х 0.9 х 0.5 = 0.252

Етап 3: ігноруємо знаменник, оскільки він буде однаковим для все інших розрахунків.

Етап 4: проводимо схожі обчислення для усіх інших класів:

  • P (Апельсин| Довгий, Солодкий, Жовтий) = 0
  • P (Інше| Довгий, Солодкий, Жовтий) = 0.01875

Оскільки 0.252 більше 0.01875, Наївний Байесовский класифікує цей довгий, солодкий і жовтий фрукт як банан.

Це навчання з учителем або без? Це навчання з учителем, оскільки Наївному Байесовскому надається маркірований учбовий набір даних для створення таблиць.

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

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

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

Де він використовується? Реалізацію Наївного Байесовского можна знайти в Orange, scikit – learn, Weka і R.

Нарешті, перейдемо до десятого алгоритму.

10. CART

Що він робить? CART означає дерево класифікації і регресії (Classification and Regression Tree). Це метод навчання способом побудови дерева рішень, який видає або дерева класифікації, або регресії. Як і C4.5, CART є класифікатором.

Дерево класифікації схоже на дерево рішень? Дерево класифікації є видом дерева рішень. Виведенням дерева класифікацій є клас.

Приміром, маючи набір даних пацієнта, ви можете спробувати передбачити, чи захворіє пацієнт раком або ні. Клас тоді буде або “захворіє раком”, або “не захворіє раком”.

Що таке дерево регресій? На відміну від дерева класифікацій, яке передбачає клас, дерево регресій передбачає числове або безперервне значення. Наприклад, час перебування пацієнта в лікарні або ціну смартфону.

Ось простий спосіб запам’ятати.

Дерева класифікацій видають класи, а дерева регресій – числа.

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

Як можна порівняти CART з C4.5?

C4.5CART
Використовує інформаційну ентропію для сегментації даних під час створення дерева рішеньВикористовує критерій Джини (не плутайте з коеффицентом Джини). Непогане обговорення відмінностей між критерієм і коефіцієнтом доступно на Stack Overflow.
Використовує однопрохідне усікання гілок для полегшення перенавчанняВикористовує метод ціни-складності при усіканні дерев. Починаючи з низу дерева, CART оцінює ціну неправильної класифікації з вузлом і без вузла. Якщо ціна не вища за встановлену максимальну, його усікають.
У вузлів рішень може бути дві або більше за гілку.У вузлів рішень мають бути рівно дві гілки.
Імовірнісний розподіляє бракуючі значення нащадкамВикористовує сурогати для розподілу бракуючих значень нащадкам

Це навчання з учителем або без? CART – це метод навчання з учителем, оскільки йому дається маркірований учбовий набір для створення моделі дерев класифікації і регресії.

Чому варто використати CART? Більшість причин, по яких ви б стали використовувати C4.5, так само застосовні до CART, оскільки обидва методи використовують дерева рішень. Легкість в інтерпретації і розумінні також є перевагами CART.

Як і C4.5, він досить швидкий, широко використовуваний, а виведення зручне для розуміння людини.

Де він використовується? scikit – learn реалізує CART в його класифікаторові дерева рішень. Пакет дерев R також має свою реалізацію CART. Їм також користуються Weka і MATLAB.

Цікаві посилання

Тепер ваша черга.

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

  • Чи збираєтеся ви тепер спробувати витягання даних?
  • Про які алгоритми, не згадані в цій статті, ви знаєте?
  • Чи є у вас які-небудь питання?

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

Переклад статті “Top 10 data mining algorithms in plain english”

Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?


Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *