Master Tree for Active Learning

最近在看Active Learning的paper，標題是Active Learning through density clustering，此篇利用Master Tree來挑選請人label的樣本，以下是研究build Master Tree演算法的心得:



此演算法的內容如Algorithm 2，輸入的U及C所組成的S如Table 1，d_c是群空間距離的門檻值，要自訂。輸出包含Ro陣列，Delta陣列，Master Tree陣列; Ro是每個樣本的鄰居數，鄰居的距離要小於d_c才算; Delta是每個樣本的最短距離，從該樣本的鄰居中，且Ro比該樣本大，但距離是最近的; Master Tree是記錄該樣本的parent，parent是符合Delta條件的鄰居。

距離是用Manhattan距離，Line 2 to 9計算Ro值。Line 10排序樣本，由大Ro到小Ro，O_j代表排名j的樣本號。Line 11 to 19計算符合Delta條件的最短距離，並記錄在Master Tree陣列裡。





Table 1，U是樣本編號，中間四個欄位是每個樣本的屬性，又叫C，class欄是分在哪一群，又叫d。