|
2.5. Алгоритм k-ближайшего соседа
Когда записи интерпретируются как точки в пространстве данных, можно определить понятие соседства (окрестности):
Записи, близкие друг другу, находятся по соседству (в окрестности) друг с другом
Предположим, что необходимо предсказать поведение множества заказчиков и у нас есть база данных с записями, описывающими этих заказчиков. Основная гипотеза, требуемая для того чтобы сделать такое предсказание, состоит в том, чтобы заказчики одного и того же типа показывали одно и то же поведение. В терминах нашего многомерного пространства данных тип - это область в этом пространстве данных. Другими словами, записи одного и того же типа будут близки друг другу в пространстве данных; они будут находиться по соседству друг с другом. Основываясь на этом понимании, разработан очень простой, но мощный алгоритм обучения - k-ближайший сосед [3]. Основной идеей алгоритма k-ближайшего соседа является - " делай так, как делают ваши соседи". Если необходимо предсказать поведение некоторого индивидуума, то необходимо рассматривать поведение, например, десяти личностей, которые близки к нему в пространстве данных. Далее вычисляется среднее поведение этих десяти соседей, и это среднее и будет предсказание для нашего индивидуума. Число k в алгоритме k-ближайшего соседа означает число исследуемых соседей: так алгоритм 5-ближайший сосед рассматривает пять соседей, а l-ближайший сосед принимает во внимание только одного соседа.
Простой алгоритм k-ближайший сосед не является реально алгоритмом обучения, а больше методом поиска. Однако, это - один из самых эффективных методов поиска, потому что набор данных непосредственно используется как ссылка. Тем не менее, его вычислительная сложность достаточно велика. Например, если мы хотим сделать предсказание для каждого элемента в наборе данных, содержащем n записей, то необходимо сравнить каждую запись с каждый другой записью. Это приводит к квадратичной сложности, которая не желательна для больших наборов данных. Так при анализе БД с миллионом записей с помощью простого алгоритма k-ближайший сосед, необходимо выполнить тысячу миллиардов сравнений. Такой подход не очень хорош, хотя существует множество исследовательских результатов, которые помогают ускорять этот процесс поиска. В общем случае, алгоритмы обнаружения знаний не должны иметь сложности, превышающей величину n (log n), где n - число записей. На практике алгоритм k-ближайшего соседа используется в основном на подвыборках или наборах данных ограниченного размера.
В табл. 2.4. представлены результаты применения процесса k-ближайшего соседа к базе данных журналов.
Таблица 2.4.
Результаты работы алгоритма k-ближайшего соседа
Журнал
|
Точность предсказания
|
Автомобильный
|
89 % правильно
|
“Дом”
|
60 % правильно
|
Спортивный
|
74 % правильно
|
Музыкальный
|
93 % правильно
|
Комиксы
|
92 % правильно
|
Можно видеть, что для журналов по автомобилям, спорту и музыке, алгоритм k-ближайшего соседа делает предсказание гораздо лучше, чем наивное предсказание. Предсказание для комиксов примерно такое же, что и наивное, поэтому в этом случае алгоритм k-ближайшего соседа не очень помогает. Однако, интересно отметить, что для журнала о доме алгоритм k-ближайший сосед делает худшее предсказание. чем наивное. Возможно это потому, что читатели этого журнала распределены случайно в наборе данных, так что никаких реальных образцов не были обнаружены, или набор данных слишком мал, чтобы выявить специфические детализированные образцы поведения этой целевой группы. Необходимо исследовать читателей журнала о доме другими методами.
Проблемы приложений алгоритма k-ближайшего соседа связаны с существованием таблиц, содержащих достаточно большое число атрибутов. Если эти атрибуты независимы друг от друга, это означает, что мы работаем с высоко размерным пространством поиска, что нежелательно по нескольким причинам. Одно из основных недостатков высоко размерных пространств состоит в том, что наша нормальная интуиция плохо работает с таким пространством. Трёхмерное пространство с равномерным распределением миллиона точек данных достаточно заполнено, и мы получим хорошие результаты от запросов по алгоритму k-ближайшего соседа. Вопреки нашей интуиции, двадцатимерное пространство с равномерным распределением миллиона точек данных чрезвычайно пусто и, что хуже всего, расстояния между любыми двумя точками данных почти равны. Таким образом, алгоритм k-ближайшего соседа в таком пространстве работает плохо.
Однако существует много возможных стратегий, которые дают возможность справиться с этой проблемой. Один из подходов состоит в том, чтобы вычислить относительную важность каждого из атрибутов. То есть определить какая информация в таблице действительно помогает предсказывать интерес клиента к определенным продуктам. Некоторые алгоритмы будут выполняться хорошо на некоторых фрагментах набора данных, в то время как другие алгоритмы бесполезны. Обнаружение знаний - процесс постоянного обучения, который непрерывно увеличивает и улучшает понимание наших наборов данных.
Do'stlaringiz bilan baham: |
