Задача о разбиении множества элементов.

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

В работе такая группировка делается с помощью построения кратчайшего остовного дерева. Алгоритмы разбиения отличаются друг от друга процедурой группировки и критерием качества разбиения множества. Введем некоторые обозначения. Пусть данные таблицы Т, подлежащие разбиению, содержат М объектов (а_1,а_2,..,а_M) ,имеющих N свойств(x_1,x_2,…,x_N), и требуется выявить К классов(S_1,S_2,…,S_K), 1<K<N-1. Различные варианты разбиения объектов на К классов будем сравнивать по некоторому критерию качества разбиения F. Если свойства объекта представить себе в виде координат метрического пространства, то каждый объект со своими значениями свойств будет отображаться в некоторую точку этого пространства. Два объекта с почти одинаковыми значениями свойств отобразятся в две близкие точки, а объекты с сильно отличающимися свойствами будут представлены далекими друг от друга точками. Если имеются сгустки точек, отделенные промежутками от других сгустков, то их целесообразно выделить в отдельные структурные части множества - классы. В дальнейшем можно аппроксимировать сгустки каким-либо известным законом распределения. Можно также указать границы класса, описав их геометрические параметры (например, задав систему уравнений разделяющих гиперплоскостей). По этим описаниям можно узнать, какому классу принадлежит любой объект как изучаемой конечной выборки, так и любого нового объекта из генеральной совокупности.

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