4.2. ИСПОЛЬЗУЕМЫЕ АЛГОРИТМЫ

Снова обратимся к структурам представительства, рассмотренным в гл. 2, постоянно оставаясь в рамках схемы, предусматривающей наличие единственного представителя от класса, а именно:

Таблица 4.1 (см. скан)

а) в качестве представителя подмножества используется центр тяжести этого подмножества, а мера сходства между элементом а множества и представителем определяется соотношением

где -мерный вектор-столбец (в нашем примере и некоторая симметричная, положительно определенная матрица порядка очевидно, что каждому разбиению множества на два класса ставится в соответствие пара центров тяжести этих двух классов и, наоборот, каждой паре (при заданной выше мере сходства ставится в соответствие разбиение;

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

где как и ранее, — центр тяжести подмножества Заметим, что последняя мера сходства не удовлетворяет допущениям 1 и 2 из 1.3.1 и соответственно не позволяет определить монотонно убывающую последовательность в алгоритме МДС. Тем не менее во всех рассмотренных нами практических ситуациях эта последовательность сходилась.

При реализации любого из алгоритмов МДС рассмотрим отображение множества разбиений (исследуемой совокупности на два класса на себя, где является суперпозицией (сверткой) двух отображений т. е. Очевидно (см. о построении и свойствах алгоритмов МДС в 1.3.5 и 1.3.6), сходимость алгоритмов МДС достигается на «неподвижных» точках (по отношению к множества т. е. на таких на которых

Рассмотрим граф где -множество пар : каждая дуга графа начинается из к и заканчивается в Гипотеза о сходимости алгоритма МДС, построенного по схеме, основанной на суперпозиции позволяет утверждать, что граф не содержит циклов. Разобьем граф на связные компоненты, каждый из которых является, таким образом, «прадеревом с петлей в корне», так как он не содержит циклов за исключением «петли» в исходной вершине, т. е. в корне. Таким образом, множество решений алгоритма МДС (подмножество разбиений из будет, в терминологии теории графов, множеством корней всех связных компонент графа