樹狀圖截斷的高效算法

-1

我已經實現了層次聚類算法以及在C＃中繪製樹狀圖的簡單方法。現在我想添加樹狀圖截止方法和另一個着色樹狀圖分支。什麼將是一個有效的算法來做到這一點？樹狀圖截斷的高效算法

截斷方法應該返回一個樹形圖節點列表，每個子樹下表示一個集羣。我的數據結構由根節點代表一個簡單的二進制樹

節點結構如下：

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

截止方法應具有以下特徵

List<DendrogramNode> CufOff(int numberOfClusters)

我做的事到目前爲止：

我的第一次嘗試是創造e所有樹形節點的列表並按降序對它們進行排序。然後從排序列表中選取numberOfClusters第一個條目。 - 這會失敗，因爲我們最終會得到一個包含所有孩子也屬於的父節點的列表。在這種情況下，應該刪除父節點。
第二次嘗試是創建一個關閉所有鏈接的列表並按鏈接順序存儲它們。這樣，我可以把最後numberOfClusters linages並使用它們來創建截止名單 - 這工作得很好，但我不喜歡來存儲這些信息，因爲它是很難維持的（專門針對反覆集羣）

它看起來像一個簡單的問題，但不知何故，我已經堆積在這。你能幫我找到一個有效的解決方案嗎？

我想解決方案1在某些方面是可以的，但是當應用程序的所有孩子都在列表中時，應該有一些部分刪除父節點，它應該以某種方式迭代/遞歸，因爲刪除節點會創建空間添加另一個。

來源

2014-12-28 Sebastian Widz

良好解決方案是使用的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; 
}

來源

2014-12-28 19:42:11

樹狀圖截斷的高效算法

回答

相關問題