K-засоби; EWSTПерекласти

  • Читання паперу K-середнього значення (PS) або паперу K-засобів (PDF) .
  • Примітка: нещодавно до нас звернули увагу на подібний результат, хоча він і незалежний. До нашої роботи. Для завершення ви також можете прочитати це.
  • Читання паперу за допомогою паперу X (PS) або паперу X (PDF) .
  • Реалізація X-засобів та K-засобів у бінарній формі тепер доступна для завантаження! В даний час існують версії для Linux, OS X та MS-Windows. Вони поширюються за таких умов:
    • Програмне забезпечення може використовуватися лише для експериментальних та дослідницьких цілей.
    • Програмне забезпечення не може розповсюджуватися кому-небудь і не може продаватися повністю або частково у більшому програмному продукті, як у вихідному, так і в двійковому вигляді.
    Щоб завантажити його, просто завантажте файл для себе в розділі завантаження .
  • Х-засоби доступні дослідникам у вихідній формі. Код на стандартній мові C і може запускатися самостійно або через пакет MATLAB. Компіляція відома за GCC (на Linux, Cygwin, OS X, Solaris та FreeBSD) та MSVC ++.
    • На додаток до засобів X, цей код також включає швидку підтримку засобів K. Це пришвидшить роботу програми K-mean за умови, що:
      • Ваші дані мають розмір не більше 15 розмірів. Однак ви можете отримати та використовувати код, якщо це не так, але не сподівайтесь, що він буде особливо швидким. Код включає просту реалізацію засобів K, які не використовують дерева KD.
      • Ви можете розрахувати евклідову відстань між будь-якою з двох точок даних, і ця відстань певним чином для вас є. Це насправді є необхідною умовою будь-якого алгоритму K-засобів.
    • Щоб отримати доступ, заповніть пропуски в цій Ліцензійній угоді та надішліть їх назад Ден Пеллег (так, є знак плюса, залиште його та слова до та після - це працює). В основному, все, що там сказано, це те, що ви не можете використовувати цю комерційну програму. Ви можете подати заявку - ми вже надали близько 800 ліцензій людям із якомога більшої кількості установ, і я завжди радий мати більше користувачів. Я не буду продавати, здавати в оренду, розповсюджувати або використовувати будь-яку іншу адресу вашої електронної пошти з будь-якою іншою метою, окрім як для того, щоб дати вам інструкції щодо завантаження.
    • Існує також список розсилки K-засоби та список розсилки X-засоби .
  • Нижче ми підготували "посібник із мультфільмів" для К-засобів:

Ось набір даних у 2 вимірах, у ньому 8000 точок. Ми проведемо на ній 5 засобів (K-засоби з K = 5). На додаток до балів, які ми бачимо, K-засоби обрали 5 випадкових балів для центрів класів. Це крапки синього, зеленого, червоного, чорного та фіолетового кольорів. Зверніть увагу, що, як є шанс, вони не відповідають гаусівцям (насправді мені довелося змусити програму виробляти ці "перші" вихідні точки - цілком добре отримувати "правильні" вихідні точки) .

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

Наступним кроком алгоритму є перестановка центрів класів. Зелений центр буде розміщений в центрі таблиці всіх зелених точок тощо. Як виявляється, зелений центр рухатиметься вправо і вгору. Чорна лінія, що виходить із зеленого центру, це показує. Зверніть увагу, що чорний і червоний центри ділять половину Гауса ліворуч (і приблизно половину Гауса, в якому вони є), тому обидва "потрібні" ліворуч. Рух фіолетового центру дуже малий.

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

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

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

Вступ до дерев KD

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

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

Ось перші сім шарів дерева KD, все на одній фотографії.

Виготовлення K-швидкого засобу з деревами KD

Всі пояснення в демонстрації K-означає вище відповідали традиційним K-засобам. "Традиційний" означає, що коли ви виходите і вирішуєте, який центр найближчий до кожної точки (наприклад, визначте кольори), зробіть наївний: для кожної точки обчисліть відстань до всіх центрів і знайдіть мінімум. Тоді наша програма набагато розумніша. Спочатку побудуйте kd-дерево для точок (ту, яку ви бачили раніше). Тепер припустимо, що вузол kd повністю належить центру. Це означає, що на наступний центральний рух буде впливати центр мас точок у цьому kd-вузлі (та їх кількість). Отже, попередньо обчисливши центр мас кожного вузла kd і зберігаючи його у вузлі, ми можемо врятувати багато речей. [показати, що вузол повністю належить центру, також можна зробити ефективно - див. короткі паперові K-засоби].

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

Зверніть увагу, як легко було розрахувати чорно-сині центри маси. Чорні взяли лише два вузли і близько 50 додаткових очок. Синій взяв 5 вузлів, плюс близько 10 очок. Порівняйте це з приблизно 8000/5 = 1600 точками, які має кожен (і зробивши 5 відстаней для кожного!).

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

Цей матеріал заснований на роботі, підтриманій грантом Національного наукового фонду № 0121671.