凸包参考的二维分类高效实现
17374 为本文评分:
尚无评分
凸包参考的二维分类高效实现
匿名作者 2014年10月9日，星期四
一种监督分类技术包括：拥有一组已知的参考样本来定义一个类别，然后将另一组未知样本与参考样本进行比较，以确定哪些样本足够相似，属于已知类别。一种可能的方法是测试未知样本是否包含在参考样本的凸包（convex hull）内，被包含在凸包内的样本即被认为属于该类。这种方法可以用于任意维度数量的样本空间。以下是一个针对二维采样空间的示例实现。
; 一种用于查找二维点的有效算法 ; 该算法用于在参考点集的凸包内查找点。 ; 此方法可用于根据一组已知的代表性参考点 ; 对新点样本进行分类。 ; 该代码经过优化，在 nPts 变得非常大的情况下 ; 能够快速运行（前提是先移除 PLOT 调用）。
pro PointOverlap
compile_opt idl2,logical_predicate
; 参考点 nRef = 300
xRef = randomn(seed, nRef) * 20 + 40
yRef = randomn(seed, nRef) * 55 + 25
p = list()
p->Add, plot(xRef, yRef, 'r+')
; 待测试点 nPts = 800
x = randomn(seed, nPts) * 50 + 50
y = randomn(seed, nPts) * 50 + 50
; 使用凸包查找参考点的范围 qhull, xRef, yRef, lines
; 测试每个其他点是否包含在凸包内 intern = bytarr(nPts)
for i=0, n_elements(lines)/2-1 do begin
seg = lines[*,i]
a = yRef[seg[0]] - y
b = yRef[seg[1]] gt y
w0 = a/(yRef[seg[0]] - yRef[seg[1]])
xval = xRef[seg[0]]*(1.0-w0) + xRef[seg[1]]*w0
; 当有奇数次交叉时，点被包含在内 intern xor= ((a gt 0) xor b) and (xval gt x)
endfor
w = where(intern, complement=v)
p->Add, plot(x[w], y[w], 'go', /over)
p->Add, plot(x[v], y[v], 'bX', /over)
for i=0, n_elements(lines)/2-1 do begin
seg = lines[*,i]
p->Add, plot(xRef[seg], yRef[seg], 'r', /over)
endfor
end