Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ
Посмотреть оригинал

ОБУЧЕНИЕ БЕЗ УЧИТЕЛЯ

В результате освоения данной главы обучающийся будет: знать

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

Кластеризация /г-средними

Постановка задачи кластеризации

Прежде чем перейти к описанию конкретного алгоритма кластеризации, дадим постановку задачи кластеризации и охарактеризуем основные методы оценки качества данных алгоритмов.

Все алгоритмы кластеризации предназначены для разделения множества объектов на непересекающиеся подмножества, или кластеры {cluster), так, чтобы объекты внутри кластера были максимально однородны и сильно отличались от объектов из других кластеров[1].

Интересно, что задачу кластеризации можно рассматривать как задачу поиска неизвестных классов для объектов обучающей выборки. Именно эта особенность делает кластеризацию особо ценным инструментом в анализе данных, даже при решении задач обучения с учителем. Так, на практике перед обучением финального классификатора производится предварительная обработка признаков. Кластеризация может быть использована с этой целью — прежде чем классифицировать весь набор признаков, можно попытаться автоматически сгенерировать метки классов для некоторой подгруппы признаков, тем самым упростив задачу финальному классификатору.

Все алгоритмы кластеризации опираются на так называемую гипотезу компактности, согласно которой в пространстве признаков все близкие объекты должны относиться к одному кластеру, а все различные объекты — соответственно к разным кластерам (рис. 6.1).

Пример двух очевидных кластеров

Рис. 6.1. Пример двух очевидных кластеров

Основным параметром алгоритма кластеризации данных является метрика. Метрика — это функция, определяющая расстояние между объектами в пространстве признаков. Именно метрика позволяет определить понятие близости в гипотезе компактности. Метрика — очень важный параметр алгоритма кластеризации, который сильно может повлиять на результаты работы алгоритма. Самая простая метрика — евклидово расстояние:

которое будет работать для вещественных признаков (или для порядковых).

В идеале метрика должна удовлетворять следующим условиям[2]:

  • • если d(x, у) = 0, то х = у, где d(x, у) — метрика;
  • d(x, у) = d(y, х);
  • d(x, z) <= d(x, у) + d(y, z) — правило треугольника.

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

Дадим формальную постановку задачи кластеризации. Дано множество объектов X = {xiy х2, х3, xL)f желательное количество кластеров К, а также целевая функция, цель которой — оценить качество кластеризации. Необходимо обучить алгоритм а(х) : X —> —>{1,2, ..., /С}, т.е. найти такую модель, которая бы для входного объекта присваивала ему метку кластера. Целевая функция определена в терминах метрики, меры сходства между объектами, т.е. необходимо минимизировать расстояние между объектами одного кластера.

Также можно говорить о полной и неполной кластеризации. При полной кластеризации весь набор входных объектов должен быть разбит на кластеры, при неполной — часть объектов может не получить метки кластера (например, такие объекты могут быть выбросами). В данной книге мы будем говорить только о полной кластеризации.

Число К называется мощностью кластеризации и обозначает общее число возможных или желательных кластеров. Это число, так же как и метрика, является параметром алгоритма кластеризации и влияет на его качество. Часто при выборе значения этого параметра опираются на внешнее представление данных (как на рис. 6.1), которое может помочь определить количество кластеров. В тех же случаях, когда невозможно на глаз определить количество кластеров, можно прибегнуть к построению кривой обучения, в которой будет отражена зависимость между параметром К и качеством кластеризации.

  • [1] Маннинг К. Д., Рагхаван П. Введение в информационный поиск. М.: Вильямс,2014.
  • [2] Скворцов В. А. Примеры метрических пространств. М.: Изд-во МЦНМО, 2002.
 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы