Старый император молча уставился в дальний темный угол тронного зала. У него ныло сердце, и он никак не мог вспомнить, какие из городов обширной империи уже заплатили дань в текущем финансовом году, а какие - еще нет. Хуже того - он совсем не мог вспомнить, куда дел свитки из королевской налоговой инспекции. "Старею", - подумал владыка и решил, что пора переходить от командно-административных методов руководства к развитию местного самоуправления. Для начала было решено ввести наиболее естественную систему территориального деления. Управлять государством станет легче, если разделить его на провинции. В империи имелось n городов. Владыка многократно объезжал свои владения и точно мог сказать, на сколько часов пути отстоят друг от друга все его города. Исходя из этого, приступая к решению задачи раздела государства, он поставил условие, чтобы раздел империи на провинции был географически обоснованным. То есть подмножество городов, выделяемое в отдельную провинцию, должно быть действительно территориально обособлено. При этом император не желал обременять казну содержанием лишних губернаторов. Поэтому он решил, что общее количество провинций должно быть возможно меньшим, но для них условие географической обособленности должно соблюдаться. Он хорошо понимал, что решить эту задачу графически при помощи карты сложно. Ведь близость точек на бумаге еще не означает, что они действительно близки. Между ними, например, может лежать высокий горный хребет. Тогда из точки А попасть в точку Б будет сложнее и дольше, чем в более удаленную точку С, расположенную на равнине. "Да, многомерная задача...", - промолвил император, достал мобильник и позвонил мне :-). Я предложил следующее решение. Необходимо сесть на коня и выехать из столицы в ближайший город, записав в список его название и время, проведенное в пути. Из него следует ехать в ближайший к нему город, но не обратно в столицу. Потом из каждого города нужно ехать в ближайший к нему из числа тех городов, которые еще не посещались, не забывая при этом вести дневник путешествия. После того, как все города будут посещены, следует вернуться в столицу, не забыв записать и этот переход. (С учетом того, что императору и так известны все расстояния между городами, путешествие может быть только воображаемым). Далее необходимо открыть дневник путешествия и вычеркнуть из него два самых длинных перехода. В результате этого множество всех городов будет разделено на две группы. Для каждой из групп следует проверить - выполняется ли условие географической обособленности? Группу городов будем считать провинцией, если максимальное внутригрупповое расстояние меньше минимального межгруппового расстояния для всех городов рассматриваемого подмножества. Если для какой-нибудь из групп (или сразу для обеих) условие выполняется, то ее следует считать провинцией и назначать губернатора. Если же условие не выполняется, следует снова вычеркнуть из дневника путешествия один самый длинный из еще не вычеркнутых переходов. Затем проверить выполнение условия географической обособленности для вновь образовавшихся подмножеств.

Задачи выделения подмножеств сходных элементов из неклассифицированных множеств объектов возникает в самых различных отраслях науки от физики до социологии. Для их решения создано множество различных алгоритмов. Однако задача автоматической классификации неклассифицированного множества или так называемая задача кластерного анализа не имеет какого-то однозначного универсального решения. "Отметим, что в случае задачи кластер анализа, когда априорная информация об изображениях (анализируемых множествах - курсив мой А.К.) целиком отсутствует, не существует никаких внешних по отношению к задаче критериев качества ее решения, кроме экспертных оценок этого качества". (Кольцов П.П. Математические модели распознавания образов//Компьютер и задачи выбора. - М.: Наука, 1989. - с.89-119). Не существует каких-то универсальных алгоритмов кластерного анализа, которые одинаково хорошо работали бы с любыми множествами объектов. Разные алгоритмы более применимы в одних случаях проявления упорядоченности данных и менее применимы в других. Поэтому поиск "хороших" алгоритмов кластерного анализа для различных типов данных по-прежнему остается актуальной задачей.

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

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

А. КОЛЕСНИКОВ,
[email protected]