Алгоритм классификации объектов. Метод шаров.

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

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

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

    Предположим, что известен некоторый радиус , соизмеримый со средним расстоянием между точками . Тогда из любой точки, как из центра можно построить круг, радиусом  и посчитать число точек, которые находятся внутри любого круга. Круг, содержащий наибольшее число точек, определяет первое подмножество (класс). Если есть несколько кругов с одним числом наибольших точек, то первое подмножество образует точки круга, центры которых расположены ближе всего к началу системы координат. Дальнейшее разбиение производится подобно образом, но число Э^ов множества снижается за счет Э^ов первого подмножества.                                                   

лучший из этих трех ибо он ближе к центру (началу координат).

Рис. 1. Геометрическая интерпретация метода шаров.

На рис. 1. Показано расположение пяти точек объекта. После вычеркивания кругов и подсчета числа точек в каждом круге можно убедится, что при выбранном , исходное множество объектов поделено на 3 класса: Объект образ 1 класса,  при этом оказывается самостоятельными классами.

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

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

Дано множество:

Для любой точки  строится шар заданного  и подсчитывается число точек  находящихся внутри любого шара.

Эти точки образуют подмножество

подмножество, содержащие  точек.

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

    Разновидностью этого метода является метод тяжелого шара. Он состоит в следующем:

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

Для них вычисляются центр точек, и центр сферы перемещается в этот центр точек. Процедура смещения центра гипер-сферы радиуса  повторяется до тех пор пока не перестанут изменятся координаты центра точек гипер-сферы.

Найденнаягипер-сфера образует подмножество . Для определения, следующего подмножество точки класса исключают из дальнейшего рассмотрения. А центр следующего такой же гиперсферы совмещают с любой из оставшихся точек.

Описанная процедура повторяется до тех пор, пока все исходное множество не будет разделено между классами.

Радиус  целесообразно определять по следующей формуле:

расстояния до точек

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

   Граф кратчайших незамкнутых путей характеризуется тем, что он соединяет все точки и при этом сумма длин всех его звеньев минимальна.

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

Обобщённый образ группы

Обобщённый образ – типовой объект, который характеризуется средними значениями признаков. Он может совпадать с одним из объектов данного класса, но может и не совпадать ни с одним из них и характеризоваться некоторыми средними значениями признаков. С группами, которые имеют большое количество объектов поступают так:

   Формулируется граф, любое звено которого представляет собой расстояние от исходных точек  до точек .

   Рассчитывается расстояние от исходного объекта  до остальных объектов данного класса и определяется сумма всех расстояний.

 число объектов в рассматриваемом классе.

Процедура  проводится для всех точек ,  при этом, очевидно, что для одной из точек сумма расстояний будет нашим оптимумом. т.е.  следующая точка  и будет искомой.