Эффективный алгоритм обрезания дендрограммы

Question

Я реализовал алгоритм иерархической кластеризации и простой метод для рисования дендрограммы на C#. Теперь я хочу добавить метод отсечки дендрограммы и еще один для раскрашивания ветвей дендрограммы. Что было бы эффективным алгоритмом для этого?

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

структуры узла выглядит следующим образом:

class DendrogramNode 
{ 
    String Id { get; set; } 
    DendrogramNode LeftNode { get; set; } 
    DendrogramNode RightNode { get; set; } 
    Double Height { get; set; } 
} 

метод CutOff должен иметь следующую подпись

List<DendrogramNode> CufOff(int numberOfClusters) 

Что я сделал до сих пор:

1. Моей первой попыткой было создать e список всех DendrogramNodes и сортировать их в порядке убывания. Затем возьмите numberOfClusters первые записи из отсортированного списка. - Это не удается, потому что мы можем получить список, содержащий родительские узлы, к которым также принадлежат все дети. В такой ситуации родительские узлы должны быть удалены.

2. Вторая попытка состояла в том, чтобы создать список всех связей и сохранить их в порядке привязки. Таким образом, я мог взять последние numberOfClusters linages и использовать их, чтобы создать список отсечки - это работает отлично, но я не хотел бы хранить эту информацию, так как трудно поддерживать (специально для итеративной кластеризации)

Он видит как простую проблему, но каким-то образом я уложился в это. Можете ли вы помочь мне найти эффективное решение?

Я предполагаю, что решение 1 было ОК в какой-то момент, но тогда должна быть какая-то часть, которая удаляет родительские узлы, когда все их дети также находятся в списке, объявление должно быть каким-то итеративным/рекурсивным, поскольку удаление узла создает чтобы добавить другое.

Answer 1

Хорошее решение заключается в использовании PriorityQueue (ITES являются узлами приоритет узла высота):

private List<DendrogramNode> GetCutOffNodes(int numberOfClusters) 
{ 
    numberOfClusters = System.Math.Min(this.NumberOfInstances, System.Math.Max(numberOfClusters, 0)); 
    PriorityQueue<DendrogramNode, DendrogramNodeDescendingComparer> queue = newPriorityQueue<DendrogramNode, DendrogramNodeDescendingComparer>(); 
    queue.Enqueue(this.Root); 
    intclusters2Find = numberOfClusters - 1; 
    DendrogramNodenode = null; 
    while(queue.Count > 0 && clusters2Find > 0) 
    { 
     node = queue.Dequeue(); 

     if(node.LeftNode != null) 
      queue.Enqueue(node.LeftNode); 

     if(node.RightNode != null) 
      queue.Enqueue(node.RightNode); 

     clusters2Find--; 
    } 

    List<DendrogramNode> result = new List<DendrogramNode>(numberOfClusters); 
    while(queue.Count > 0) 
     result.Add(queue.Dequeue()); 
    return result; 
}