4.1.2. Алгоритм решения задачи автоматической классификации

Установим меру сходства между объектами по совокупности

параметров. Для этого сначала нормализуем балльные оценки

параметров так, чтобы в сумме они составляли 1. Полученные таким

образом оценки обозначим {w[j], j=1,..,M}:

w[j] = b[j] / (b[1]+b[2]+...+b[M])

Легко видеть, что, действительно w[1]+w[2]+...+w[M]=1. Назовем

оценки w[j] весами параметров. Назовем теперь расстоянием от объекта

R[k] до объекта R[l] сумму абсолютных значений разностей между

значениями каждого из параметров объекта в данный момент времени,

умноженных на веса соответствующих параметров:

d(k,l,t)=w[1]*abs(p[k,1,t]-p[l,1,t]) +

w[2]*abs(p[k,2,t]-p[l,2,t]) +

........................... +

w[M]*abs(p[k,M,t]-p[l,M,t])

Легко видеть, что функция d(k,l,t) действительно обладает

свойствами расстояния: d(k,l,t) неотрицательно при любых k,l и t;

d(k,k,t)=0 при любом t. Теперь можно определить меру сходства

объектов следующим образом: чем меньше d(k,l,t), тем более похожи

друг на друга объекты R[k] и R[l].

Будем называть представителем класса объект, являющийся в

некотором смысле наиболее типичным объектом этого класса. Тогда

можно определить функцию представительства (выбора представителя

класса) следующим образом: объект R[k] является представителем

класса C[q], если сумма расстояний от него до всех объектов этого

класса минимальна по всем объектам класса:

min { d(l,1,t)+d(l,2,t)+...+d(l,M,t) } =

R[l] входит в C[q]

= d(k,1,t)+d(k,2,t)+...+d(k,M,t)

Сформируем теперь функцию назначения (отнесения объекта к

классу). Предположим, нам известны представители всех классов. Тогда

будем считать, что объект R[k] относится к классу C[q], если расстояние

от представителя этого класса до данного объекта меньше, чем от

представителя любого другого класса.

Теперь мы имеем все необходимое для того, чтобы сформировать

алгоритм классификации объектов по совокупности параметров.

Перечислим основные шаги алгоритма классификации:

1.Выберем произвольные L объектов из общей совокупности. Будем

считать их представителями классов.

2.Проведем процедуру назначения для всех объектов, не

являющихся представителями классов.

3.Для вновь сформированных классов проведем процедуру

представительства. Если ни один из представителей классов не

изменился, то классификация закончена. В противном случае

возвращаемся к п.2.

Существует строгое доказательство того, что данный алгоритм

всегда сходится (9).

Следует обратить внимание на то, что предлагаемый алгоритм

работает безотносительно к экономическому смыслу используемых

параметров. Результатом работы данного алгоритма является набор

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

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

возможно, что в классе будут объединены регионы, которые по одному

индикатору являются стабильными и благополучными, а по другому -

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

может дать богатый материал для социально-экономического

осмысления ситуации как по России в целом, так и по регионам.

Отметим, что рассмотренный алгоритм классификации выбран с

точки зрения простоты его реализации. В кластер-анализе предлагается

большое число агоритмов, однако мы выбрали именно этот, поскольку

при существующей точности исходных данных более сложные

алгоритмы вряд ли могут оказаться более приемлемыми.