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