АЛГОРИТМ ПАРЗЕНА - РОЗЕНБЛАТТА

Для уявлення про метод Парзена - Розенблатта почнемо з найпростішого випадку - відновлення одновимірної щільності розподілу р (х | у).

Для випадку дискретної змінної х можна відновити щільність за допомогою гістограми:

Для безперервної змінної можна зробити відновлення по її по щільності по визначенню цього поняття:

Вираз (5.7) називається емпіричною оцінкою щільності розподілу але вікна шириною / ?. Нотація Аверсона в даному виразі дозволяє виконати відновлення щільності за допомогою кусочно-постійної функції. Недоліком використання такої функції можна вважати те, що точки x if потрапляють в скануючий вікно ширини А, будуть давати однаковий внесок незалежно від відстані до центру.

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

  • • ядро К (г) має бути парною функцією;
  • К (г) - нормована функція, тобто jK (r) dr = 1;
  • • за особливим винятком К (г ) - незростаюча, неотрицательная функція (мається на увазі її права гілка, так як вона парна).

Таким чином, ми приходимо до узагальненої оцінки Парзена - Розенблатта по вікну шириною / г [1] :

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

На практиці часто береться гауссово ядро:

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

де V (h ) - об'єм кулі в ^ -мірному просторі ознак; р (х, Xj) - метрика, введених для оцінки відстані між об'єктами в ^ -мірному просторі.

Обсяг кулі V (h) можна розрахувати за наступною формулою:

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

Підставивши вираз (5.8) в (5.6), отримаємо фінальний вигляд методу Парзена - Розенблатта:

де /, у - число об'єктів класу у на навчальній вибірці.

Як видно з (5.9), метод Парзена - Розеблатта вимагає зберігання всієї навчальної вибірки і залежить від розміру вікна h. Але як його вибрати? В даному випадку може стати в нагоді метод для вибору оптимальних параметрів алгоритму машинного навчання, званий методом ковзаючого контролю ( Leave-One-Out , LOO) [2] :

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

  • [1] Див .: Воронцов К. В. Лекції за статистичними (Байєсова) алгорітмам.URL: http://www.machinelearning.rU/wiki/images/e/ed/Voron-ML-Bayes.pdf
  • [2] Statistical Learning: Stability is Sufficient for Generalization and Necessary andSufficient for Consistency of Empirical Risk Minimization / S. Mukherjee, P. Niyogi, T. Poggio, R. Rifkin // Advances in Computational Mathematics. 2006. № 25.
 
Переглянути оригінал
< Попер   ЗМІСТ   ОРИГІНАЛ   Наст >