Последовательности этапов решения задач классификации с использованием алгоритмов вычисления оценок

Оценки () и (S) поданных за класс (u = 1,2,…, l) по фиксированному опорному множеству или системе опорных множеств соответственно.

Дадим интерпретацию рассмотренных этапов задания алгоритма (Г-модели) применительно к задаче классификации.

Пусть заданы объекты двух классов:

первого , ,…, и

второго , ,…, .

Каждый из объектов характеризуется набором значений u бинарных признаков. Требуется отнести предъявленную строку S длины u к одному из классов.

Зададим длину опорного множества , равную K и выделим все наборы столбцов длины K (предполагается, что всё множество объектов с u признаками сведено в таблицу T mn2).

Берем первый по порядку набор, составленный из столбцов с номерами 1,2,…,k. В предъявленной строке S и строках , ,…, и , ,…, выделим только первые k столбцов (это возможно, т.к. перестановка столбцов в исходной таблице не приводит к потери информативности заданных описаний).

Полученные после такой операции строки обозначим через , ,…, и , ,…, ; .

Обозначим через число строк из , ,…, совпадающие с , через - число строк из , ,…, , тоже совпавшие с .

Построим величины и для всех наборов , ,…, длины k (эти величины соответствуют оценкам () и ()).

Тогда оценки

(S) =

полученные по всем наборам длины k, естественно назвать числом голосов, поданных строкой S соответственно за первый и второй классы.

Отнесение строки S к одному из классов можно провести одним из рассмотренных ранее решающих правил. Кроме того, следует учитывать удельное число голосов. Например, величины и называют удельным числом голосов, поданных за первый и второй классы строкой S.

Если > , то строку S можно отнести к первому классу. При = = 0 – алгоритм отказывается от классификации строки S. Если же число объектов в обоих классах совпадает, то нет необходимости привлекать при отнесении (классификации) удельное число голосов.

В случае, если решающее правило ориентировано на использование параметров и ,

= (S) - (S);

= (S) / (S); то значение и можно выбрать в процессе обучения (на контрольном материале) следующим образом:

- фиксируются некоторые значения и .

- производится прогноз на контрольном материале.

- за каждый неправильный прогноз и отказ от распознавания начисляются штрафные очки (например, 2 и 1).

- подсчитывается общее число штрафных очков.

- осматривается окрестность и и каждый раз подсчитывается сумма штрафных очков.

- осуществляется переход в точку с минимальным числом штрафных очков и т.д. до нахождения оптимальных и .

Пример:

Пусть задана таблица объектов (m = 6; n 6; l = 2).

объекты класса

- строка S

В качестве голосующих наборов рассмотрим наборы столбцов <1,2>, <3,4>, <5,6>. Две строки будем считать похожими, если они совпадают.

Оставим в таблице сначала столбцы 1и 2, затем 3 и 4 и, наконец, 5 и 6. Получаем, что число совпадений со строками первого класса равно 1, второго 2, т.е. = 1; = 2. Аналогично = 2; = 1; = 1; = 0.

Следовательно, (S) = 4; (S) = 3.

Если решающее правило относит строку по простому большинству голосов, то в данном примере строка будет относиться к классу , т.к. (S) > (S). При = 1 строка S также будет отнесена к классу ; т.к. ( (S) - (S)) = 1 = удельное число голосов, поскольку = .