Вопрос 13 Метод k-ближайшего представителя (ближайшего соседа).

Метод заключается в том, что ищется объект обучающей последовательности, находящийся наиболее близко к исследуемому объекту и считается, что класс нового объекта совпадает с классом объекта обучающей последовательности. Исследуемый объект Х(х₁,х₂,…х_k) и объекты обучающей последовательности можно представить в виде точек k–мерного пространства. При этом могут быть разными методы определения расстояния между объектами. Наиболее распространенными из них являются:

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

«+» простота

«-» обучающая последовательность должна быть исчерпывающей, без ошибок, ее нужно хранить в памяти ЭВМ. Алгоритм занимает довольно много времени. Классы должны четко разделяться.

Метод k–ближних представителей.

До эксперимента, оговаривается k представителей, расстояние до которых определит принадлежность исследуемого объекта к тому или другому классу. Метод заключается в том, что рассчитывается расстояние (₁, ₂ или ₃) от исследуемого объекта до каждого из объектов обучающей последовательности и выбирается те k объектов, до которых расстояние минимально. Объект принадлежит к тому классу, к которому принадлежит большинство из k ближних представителей (минимальное значение ₄):

где k_j – число объектов среди k, принадлежащих классу j;

«+» допускаются ошибки в обучающих последовательностях

«-» теже

Вопрос 14 Метод эталона, решающая функция

Этот метод заключается в том, что для каждого класса определяется эталон – объект, являющийся центром тяжести точек каждого класса. Свойства (параметры) эталонов находятся путём усреднения свойств объектов обучающей последовательности, принадлежащих к соответствующему классу. Ниже приведена формула, позволяющая вычислить x_i–й параметр j–того класса.

где k_j – число объектов обучающей последовательности, принадлежащих j–тому классу.

Принадлежность исследуемого объекта к тому или другому классу определяется по минимальному расстоянию этого объекта до эталонов.

«+» не нужно хранить обучающую последовательность в памяти

Алгоритм сокращается

«-» границы четко определены

Используется если объекты класса группируются вокруг центра тяжести.

Придумать рисунок!

Объект описываемый вектором х может принадлежать только одному классу.

Вопрос 15. Байесовское решающее правило

Недостатком рассмотренных выше методов является то, что они могут применяться только тогда, когда классы чётко разделяются друг от друга. На практике часто встречаются случаи, когда объекты, имеющие совпадающие свойства, относятся к разным классам. Примером могут служить ходовые свойства отцепов. Как правило, тяжёлые отцепы являются хорошими бегунами, а лёгкие – плохими. Но бывает наоборот, тяжёлый бегун оказывается плохим бегуном, а лёгкий – хорошим. Таким образом, объект, имеющий вектор Х свойств, может быть отнесён, с какой-то вероятностью, к любому классу.

Обозначим через P(V_i/X) вероятность того, что объект, имеющий вектор свойств Х, принадлежит классу V_i и через C_ij – потери, вызванные тем, что объект, принадлежащий классу V_i, ошибочно отнесён к классу V_j. Так как объект Х может принадлежать любому из k классов, математическое ожидание потерь, вызванное отнесением этого объекта к классу V_j, будет равно:

Эта величина называется условным средним риском или условными средними потерями.

Вычислим условные средние потери для каждого класса R₁(X), R₂(X), …,R_k(X). Минимальное значение условных средних потерь при отнесении объекта к какому-нибудь классу можно считать признаком того, что объект принадлежит этому классу.

Воспользовавшись формулой Байеса

выражение расчёта условной средней потери можно представить в следующем виде:

Поскольку выражение 1/P(X) входит в качестве множителя во все формулы вычисления условных средних потерь, его можно отбросить.

Для упрощения рассуждений будем считать, что C_ij=0, если i=j (класс определён правильно, потери равны нулю), и C_ij =1, если i  j (потери одинаковы при любой ошибке). Представим функцию потерь в следующем виде: С_ij=1-_ij,, где _ij =1, если i = j, и _ij=0, если i  j.

В этом случае математическое ожидание потерь будет равно:

Поскольку суммирование ведётся по всем классам сумма произведений вероятности класса и вероятности объекта в классе равна вероятности объекта:

Если объект принадлежит классу V_i, должно соблюдаться неравенство:

Отбросив P(X), получим:

Таким образом, решающее правило будет иметь вид:

При этом объект зачисляется в класс V_i, если q_i(x) q_j(x), j =1..k, j i.

P(Vi)= n_i/n, n – общее число объектов обучающей последовательности, n_i – число объектов обучающей последовательности, принадлежащих классу V_i.

R_i (X)=P(X)P(V_i /X). Как и в предыдущем случае, Р(Х) можно отбросить. Таким образом, основной можно считать решающую функцию:

R_i (X)= P(V_i /X).

В отличие от предыдущей функции её можно использовать даже при сравнительно небольшой выборке объектов обучающей последовательности.

R_i (X)>0,5 – объект принадлежит классу V₁, иначе к V₂.