Алгоритмы обучения «без учителя»

Предлагается рассмотреть два метода обучения. В обучении с учителем, учитель определяет классы и предлагает примеры объектов каждого класса. Система должна найти общие свойства объектов каждого класса, сформировав тем самым описание класса. Описание класса вместе с самим классом дает нам классифицирующее правило “если < описание> то < класс> ”, которое может быть использовано для предсказания класса объектов, неизвестных системе ранее. Другой метод обучения – обучение без учителя – предполагает, что системе предъявляется совокупность объектов, не разделенных на классы. Количество классов также может быть неизвестным. Система должна сама определить классы объектов, основываясь на общих свойствах объектов из данного множества примеров.

Пусть обучающая выборка содержит М объектов: = {X₁, X₂, … X_M}. Каждый из этих объектов представляет собой n-мерный вектор Х_i, значений признаков:     X=< x_i1, x_i2, …, x_in>.

Здесь x_ij – значение j-го признака для i-го объекта, n – количество признаков, характеризующих объект. Напомним, что признаки, используемые для описания объекта, чисто количественные.

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

Для числовых объектов мерой близости является расстояние. Расстояние  между двумя объектами, может быть определено по одной из формул:

,

,

,

где X, Y – векторы (наборы) значений признаков двух объектов, x_k., y_k – соответствующие значения k–го признака объектов, n – общее число признаков. В дальнейшем будем использовать обозначение , когда расстояние можно ввести любым из перечисленных способов; если речь идет о расстоянии по Евклиду, будем применять также общепринятое обозначение .

Требуется в соответствии с заданным критерием разделить набор  на классы, количество которых заранее неизвестно. Под критерием подразумевается мера близости всех объектов одного класса между собой. Будем считать, что работа алгоритма завершена успешно, если классы, сформированные в результате работы алгоритма, достаточно компактны и, возможно, выполнены некоторые дополнительные критерии.

При решении задачи обучения без учителя самыми несложными являются алгоритмы, основанные на мерах близости. Для достижения цели – компактного формирования классов – введем понятие точки–прототипа, или точки в n- мерном пространстве признаков, являющейся наиболее " типичной" представительницей построенного класса. В дальнейшем расстояние от объекта до класса будет заменяться расстоянием от объекта до точки-прототипа. Точка-прототип может быть сопоставлена каждому сформированному классу и при этом вовсе не обязательно существование реального объекта, соответствующего точке-прототипу. Представим алгоритмы этого типа на нескольких примерах.