4.5.3. Иерархическое группирование

В алгоритмах иерархического группирования предполагается, что данные, подлежащее группированию, берутся из единственного класса, который можно разбить на подклассы и подподклассы. Один из наиболее широко применяемых методов иерархического группирования принадлежит Джонсону (1967). Этот метод можно использовать как в евклидовом, так и в неевклидовом пространствах, если считать меру расстояния между двумя точками некоторой мерой, определяемой для любых двух точек в X.

Метод Джонсона иерархического группирования

(1) Определим матрицу Н, элементами которой служат расстояния между парами экспериментальных точек:

(2) Проведем группирование в котором каждия экспериментальная точка относится к классу, содержащему только ее саму. Ясно, что расстояние между любыми двумя скоплениями в этом случае равно

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

(4) Переопределим матрицу Н, вычеркивая все элементы, относящиеся к и добавляя расстояния до нового скопления определяемые для и некоторого третьего элемента с по правилу максимума

или правилу минимума

(5) Повторяем шаги 3 и 4 до тех пор, пока все начальные экспериментальные точки не объединятся в одну группу.

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

Как и в случае средних, иерархическая процедура Джонсона обычно проверяется примерами. Один из них — задача акустической неразборчивости. Испытуемых просили идентифицировать фонемы в плохих условиях слышимости. Результаты эксперимента представили в виде „матрицы неразборчивости", элементами которой были вероятности того, что распознавалась фонема в то время как была произнесена фонема Матрица неразборчивости рассматривалась как матрица . Были получены следующие группы для одного уровня: глухие взрывные звонкие взрывные глухие фрикативные звонкие фрикативные носовые Таким образом, этот алгоритм произвел Деление на группы, имеющие акустический смысл. Аналогично другие авторы получили разумные результаты в ряде приложений теории поведения.