1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta http-equiv="Content-Style-Type" content="text/css">
<title></title>
<meta name="Generator" content="Cocoa HTML Writer">
<meta name="CocoaVersion" content="824.48">
<style type="text/css">
p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 18.0px Helvetica}
p.p2 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica; min-height: 14.0px}
p.p3 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica; color: #a71d0f}
p.p4 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica}
p.p5 {margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Monaco}
p.p6 {margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Monaco; color: #bf0000}
p.p7 {margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Monaco; color: #000000}
p.p8 {margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Monaco; min-height: 12.0px}
p.p9 {margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Monaco; color: #b71505}
span.s1 {color: #0022b7}
span.s2 {color: #002ef6}
span.s3 {color: #bf0000}
span.s4 {color: #0014bd}
span.s5 {color: #606060}
span.Apple-tab-span {white-space:pre}
</style>
</head>
<body>
<p class="p1"><b>PlaneTree<span class="Apple-tab-span"> </span><span class="Apple-tab-span"> </span>Tree classifier using (hyper)planes – UGen or language-side</b></p>
<p class="p2"><br></p>
<p class="p3"><b>// Server-side (for use in synths):</b></p>
<p class="p4"><span class="s1"><b>PlaneTree</b></span><b>.kr(treebuf, in, gate)</b></p>
<p class="p3"><b>// Language-side:</b></p>
<p class="p4"><span class="s1"><b>PlaneTree</b></span><b>.classify(point, treedata)</b></p>
<p class="p2"><br></p>
<p class="p4">Given a specially-formatted dataset representing a hyperplane-based binary tree classifier, this unit classifies incoming data points. It can handle any dimensionality of data (the dimensionality of the incoming data points needs to match that of the tree) and can branch to arbitrary depths including some branches being deeper than others.</p>
<p class="p2"><br></p>
<p class="p4"><span class="Apple-converted-space"> </span>- <b>treebuf</b> - a multichannel <a href="SC://Buffer"><span class="s2">Buffer</span></a> holding data in the special tree representation. The required data format is described near the bottom of this document.</p>
<p class="p4"><span class="Apple-converted-space"> </span>- <b>in</b> - the input signal to be classified (typically a multichannel signal).</p>
<p class="p4"><span class="Apple-converted-space"> </span>- <b>gate</b> - on or off. While gate>0, classification is performed; otherwise the previous value is held constant.</p>
<p class="p2"><span class="Apple-converted-space"> </span></p>
<p class="p4">The <b>return value</b> is an integer giving a binary representation of the path through the tree. For example:</p>
<p class="p4"><span class="Apple-tab-span"> </span>9 in binary is 1001 – the first 1 <i>always</i> represents the root of the tree, then the remaining digits indicate you go left-left-right.</p>
<p class="p4"><span class="Apple-tab-span"> </span>12 in binary is 1100 - the first 1 is the root, followed by right-left-left.</p>
<p class="p4"><span class="Apple-tab-span"> </span>1 in binary is 1 so this represents the root node.</p>
<p class="p4"><span class="Apple-tab-span"> </span>27.asBinaryDigits gives 11011, so that's right-left-right-right.</p>
<p class="p2"><br></p>
<p class="p4"><b>Example</b></p>
<p class="p2"><br></p>
<p class="p4">This simple example splits 2D data into four classes:</p>
<p class="p2"><br></p>
<p class="p5">(</p>
<p class="p6">// Three nodes in this data. First is always the root.</p>
<p class="p6">// So the first is applied to decide whether to branch down to the second or third.</p>
<p class="p6">// Then those nodes decide whether to classify the datum as 1/2/3/4.</p>
<p class="p7">~treedata = [</p>
<p class="p6">/* xoff,yoff, xvec,yvec, lisl, risl */</p>
<p class="p7"><span class="Apple-converted-space"> </span>[0.5, 0.5, -0.7, 0.4,<span class="Apple-converted-space"> </span>0,<span class="Apple-converted-space"> </span>0],<span class="Apple-converted-space"> </span><span class="s3">// this is the root node, its number is 1</span></p>
<p class="p7"><span class="Apple-converted-space"> </span>[0.3, 0.7,<span class="Apple-converted-space"> </span>0.4, 0.7,<span class="Apple-converted-space"> </span>1,<span class="Apple-converted-space"> </span>1],<span class="Apple-converted-space"> </span><span class="s3">// this one's number is 2</span></p>
<p class="p7"><span class="Apple-converted-space"> </span>[0.5, 0.2, -0.8,-0.8,<span class="Apple-converted-space"> </span>1,<span class="Apple-converted-space"> </span>1] <span class="Apple-converted-space"> </span><span class="s3">// this one's number is 3</span></p>
<p class="p7">];</p>
<p class="p5">)</p>
<p class="p8"><br></p>
<p class="p4">Note that the data points are numbered starting from 1 not 0. This is deliberate and compulsory for the numbering scheme to work correctly, but a little bit confusing - in the above you might expect the three frames to be indexed as [0,1,2] but their integer references are actually [1,2,3].</p>
<p class="p8"><br></p>
<p class="p9">// Now to demonstrate language-side classification, we'll iterate over a grid and classify:</p>
<p class="p5">(</p>
<p class="p5">(0, 0.1 .. 1).collect{<span class="s4">|y|</span></p>
<p class="p5"><span class="Apple-tab-span"> </span>(0, 0.1 .. 1).collect{<span class="s4">|x|</span></p>
<p class="p5"><span class="Apple-tab-span"> </span><span class="Apple-tab-span"> </span><span class="s4">PlaneTree</span>.classify([x,y], ~treedata)</p>
<p class="p5"><span class="Apple-tab-span"> </span>}</p>
<p class="p5">}.do(<span class="s4">_</span>.postln);<span class="s5">""</span></p>
<p class="p5">)</p>
<p class="p8"><br></p>
<p class="p9">// Server-side: run this then move the mouse left/right/up/down - classification should follow same pattern.</p>
<p class="p5">s.boot;</p>
<p class="p5">~treebuf = <span class="s4">Buffer</span>.loadCollection(s, ~treedata.flat, ~treedata[0].size);</p>
<p class="p5">(</p>
<p class="p5">x = {</p>
<p class="p5"><span class="Apple-tab-span"> </span><span class="s4">PlaneTree</span>.kr(~treebuf, [<span class="s4">MouseX</span>.kr(0,1), <span class="s4">MouseY</span>.kr(0,1)]).poll</p>
<p class="p5">}.play</p>
<p class="p5">)</p>
<p class="p5">x.free;</p>
<p class="p2"><br></p>
<p class="p2"><br></p>
<p class="p4"><b>Data format</b></p>
<p class="p2"><br></p>
<p class="p4">Each node in the tree is represented by a multichannel frame in a buffer (or in the language-side representation, by an array in an array). The first node must be the root node and is where classification begins. Each node consists of data defining the hyperplane used for splitting, and then flags indicating whether the split data should recurse further to a different node or whether a numeric classification result is to be returned. More explicitly, for a D-dimensional tree, each node consists of:</p>
<p class="p2"><br></p>
<p class="p5">[</p>
<p class="p5"><span class="Apple-tab-span"> </span>D numbers - the offset vector, subtracted from the incoming data point</p>
<p class="p5"><span class="Apple-tab-span"> </span>D numbers - representing the normal vector, multiplied by the incoming data point (after subtraction) for classification</p>
<p class="p5"><span class="Apple-tab-span"> </span>0 or 1<span class="Apple-converted-space"> </span>- if 1, the "left" split is a leaf and that branch terminates</p>
<p class="p5"><span class="Apple-tab-span"> </span>0 or 1<span class="Apple-converted-space"> </span>- if 1, the "right" split is a leaf and that branch terminates</p>
<p class="p5">]</p>
<p class="p2"><br></p>
<p class="p4">For dimensionality D the data must therefore have 2D + 2 channels.</p>
<p class="p2"><br></p>
<p class="p4">Note that each "layer" of the tree is represented in sequence. The first (numbered 1) is the root, then its two children (binary 10 and 11), then their four children. Branching doesn't have to proceed to the same depth at each branch, so for example node 1001 might not exist even if node 1010 and 1011 exist, but because the frame indices are used to retrieve the data, you would still need some blank/garbage data in the 1001 frame.</p>
<p class="p2"><br></p>
<p class="p4">(c) 2009-2010 Dan Stowell</p>
</body>
</html>
|
