DecisionTree using Julia

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

1. module DecisionTree
   
2. 
   
3. import Base: length, convert, promote_rule, show, start, next, done
   
4. 
   
5. export Leaf, Node, Ensemble, print_tree, depth,
   
6.        build_stump, build_tree, prune_tree, apply_tree, nfoldCV_tree,
   
7.        build_forest, apply_forest, nfoldCV_forest,
   
8.        build_adaboost_stumps, apply_adaboost_stumps, nfoldCV_stumps,
   
9.        majority_vote, ConfusionMatrix, confusion_matrix,
   
10.        mean_squared_error, R2
    
11. 
    
12. include("measures.jl")
    
13. 
    
14. immutable Leaf
    
15.     majority::Any
    
16.     values::Vector
    
17. end
    
18. 
    
19. immutable Node
    
20.     featid::Integer
    
21.     featval::Any
    
22.     left::Union(Leaf,Node)
    
23.     right::Union(Leaf,Node)
    
24. end
    
25. 
    
26. immutable Ensemble
    
27.     trees::Vector{Node}
    
28. end
    
29. 
    
30. convert(::Type{Node}, x::Leaf) = Node(0, nothing, x, Leaf(nothing,[nothing]))
    
31. promote_rule(::Type{Node}, ::Type{Leaf}) = Node
    
32. promote_rule(::Type{Leaf}, ::Type{Node}) = Node
    
33. 
    
34. immutable UniqueRanges
    
35.     v::AbstractVector
    
36. end
    
37. 
    
38. start(u::UniqueRanges) = 1
    
39. done(u::UniqueRanges, s) = done(u.v, s)
    
40. next(u::UniqueRanges, s) = (val = u.v[s];
    
41.                             t = searchsortedlast(u.v, val, s, length(u.v), Base.Order.Forward);
    
42.                             ((val, s:t), t+1))
    
43. 
    
44. length(leaf::Leaf) = 1
    
45. length(tree::Node) = length(tree.left) + length(tree.right)
    
46. length(ensemble::Ensemble) = length(ensemble.trees)
    
47. 
    
48. depth(leaf::Leaf) = 0
    
49. depth(tree::Node) = 1 + max(depth(tree.left), depth(tree.right))
    
50. 
    
51. function print_tree(leaf::Leaf, depth=-1, indent=0)
    
52.     matches = find(leaf.values .== leaf.majority)
    
53.     ratio = string(length(matches)) * "/" * string(length(leaf.values))
    
54.     println("$(leaf.majority) : $(ratio)")
    
55. end
    
56. 
    
57. function print_tree(tree::Node, depth=-1, indent=0)
    
58.     if depth == indent
    
59.         println()
    
60.         return
    
61.     end
    
62.     println("Feature $(tree.featid), Threshold $(tree.featval)")
    
63.     print("    " ^ indent * "L-> ")
    
64.     print_tree(tree.left, depth, indent + 1)
    
65.     print("    " ^ indent * "R-> ")
    
66.     print_tree(tree.right, depth, indent + 1)
    
67. end
    
68. 
    
69. const NO_BEST=(0,0)
    
70. 
    
71. 
    
72. ### Classification ###
    
73. 
    
74. function _split(labels::Vector, features::Matrix, nsubfeatures::Int, weights::Vector)
    
75.     if weights == [0]
    
76.         _split_info_gain(labels, features, nsubfeatures)
    
77.     else
    
78.         _split_neg_z1_loss(labels, features, weights)
    
79.     end
    
80. end
    
81. 
    
82. function _split_info_gain(labels::Vector, features::Matrix, nsubfeatures::Int)
    
83.     nf = size(features, 2)
    
84.     N = length(labels)
    
85. 
    
86.     best = NO_BEST
    
87.     best_val = -Inf
    
88. 
    
89.     if nsubfeatures > 0
    
90.         r = randperm(nf)
    
91.         inds = r[1:nsubfeatures]
    
92.     else
    
93.         inds = 1:nf
    
94.     end
    
95. 
    
96.     for i in inds
    
97.         ord = sortperm(features[:,i])
    
98.         features_i = features[ord,i]
    
99.         labels_i = labels[ord]
    
100. 
     
101.         hist1 = _hist(labels_i, 1:0)
     
102.         hist2 = _hist(labels_i)
     
103.         N1 = 0
     
104.         N2 = N
     
105. 
     
106.         for (d, range) in UniqueRanges(features_i)
     
107.             value = _info_gain(N1, hist1, N2, hist2)
     
108.             if value > best_val
     
109.                 best_val = value
     
110.                 best = (i, d)
     
111.             end
     
112. 
     
113.             deltaN = length(range)
     
114. 
     
115.             _hist_shift!(hist2, hist1, labels_i, range)
     
116.             N1 += deltaN
     
117.             N2 -= deltaN
     
118.         end
     
119.     end
     
120.     return best
     
121. end
     
122. 
     
123. function _split_neg_z1_loss(labels::Vector, features::Matrix, weights::Vector)
     
124.     best = NO_BEST
     
125.     best_val = -Inf
     
126.     for i in 1:size(features,2)
     
127.         domain_i = sort(unique(features[:,i]))
     
128.         for thresh in domain_i[2:end]
     
129.             cur_split = features[:,i] .< thresh
     
130.             value = _neg_z1_loss(labels[cur_split], weights[cur_split]) + _neg_z1_loss(labels[!cur_split], weights[!cur_split])
     
131.             if value > best_val
     
132.                 best_val = value
     
133.                 best = (i, thresh)
     
134.             end
     
135.         end
     
136.     end
     
137.     return best
     
138. end
     
139. 
     
140. function build_stump(labels::Vector, features::Matrix, weights=[0])
     
141.     S = _split(labels, features, 0, weights)
     
142.     if S == NO_BEST
     
143.         return Leaf(majority_vote(labels), labels)
     
144.     end
     
145.     id, thresh = S
     
146.     split = features[:,id] .< thresh
     
147.     return Node(id, thresh,
     
148.                 Leaf(majority_vote(labels[split]), labels[split]),
     
149.                 Leaf(majority_vote(labels[!split]), labels[!split]))
     
150. end
     
151. 
     
152. function build_tree(labels::Vector, features::Matrix, nsubfeatures=0)
     
153.     S = _split(labels, features, nsubfeatures, [0])
     
154.     if S == NO_BEST
     
155.         return Leaf(majority_vote(labels), labels)
     
156.     end
     
157.     id, thresh = S
     
158.     split = features[:,id] .< thresh
     
159.     labels_left = labels[split]
     
160.     labels_right = labels[!split]
     
161.     pure_left = all(labels_left .== labels_left[1])
     
162.     pure_right = all(labels_right .== labels_right[1])
     
163.     if pure_right && pure_left
     
164.         return Node(id, thresh,
     
165.                     Leaf(labels_left[1], labels_left),
     
166.                     Leaf(labels_right[1], labels_right))
     
167.     elseif pure_left
     
168.         return Node(id, thresh,
     
169.                     Leaf(labels_left[1], labels_left),
     
170.                     build_tree(labels_right,features[!split,:], nsubfeatures))
     
171.     elseif pure_right
     
172.         return Node(id, thresh,
     
173.                     build_tree(labels_left,features[split,:], nsubfeatures),
     
174.                     Leaf(labels_right[1], labels_right))
     
175.     else
     
176.         return Node(id, thresh,
     
177.                     build_tree(labels_left,features[split,:], nsubfeatures),
     
178.                     build_tree(labels_right,features[!split,:], nsubfeatures))
     
179.     end
     
180. end
     
181. 
     
182. function prune_tree(tree::Union(Leaf,Node), purity_thresh=1.0)
     
183.     function _prune_run(tree::Union(Leaf,Node), purity_thresh::Real)
     
184.         N = length(tree)
     
185.         if N == 1        ## a Leaf
     
186.             return tree
     
187.         elseif N == 2    ## a stump
     
188.             all_labels = [tree.left.values; tree.right.values]
     
189.             majority = majority_vote(all_labels)
     
190.             matches = find(all_labels .== majority)
     
191.             purity = length(matches) / length(all_labels)
     
192.             if purity >= purity_thresh
     
193.                 return Leaf(majority, all_labels)
     
194.             else
     
195.                 return tree
     
196.             end
     
197.         else
     
198.             return Node(tree.featid, tree.featval,
     
199.                         _prune_run(tree.left, purity_thresh),
     
200.                         _prune_run(tree.right, purity_thresh))
     
201.         end
     
202.     end
     
203.     pruned = _prune_run(tree, purity_thresh)
     
204.     while length(pruned) < length(tree)
     
205.         tree = pruned
     
206.         pruned = _prune_run(tree, purity_thresh)
     
207.     end
     
208.     return pruned
     
209. end
     
210. 
     
211. apply_tree(leaf::Leaf, feature::Vector) = leaf.majority
     
212. 
     
213. function apply_tree(tree::Node, features::Vector)
     
214.     if tree.featval == nothing
     
215.         return apply_tree(tree.left, features)
     
216.     elseif features[tree.featid] < tree.featval
     
217.         return apply_tree(tree.left, features)
     
218.     else
     
219.         return apply_tree(tree.right, features)
     
220.     end
     
221. end
     
222. 
     
223. function apply_tree(tree::Union(Leaf,Node), features::Matrix)
     
224.     N = size(features,1)
     
225.     predictions = Array(Any,N)
     
226.     for i in 1:N
     
227.         predictions[i] = apply_tree(tree, squeeze(features[i,:],1))
     
228.     end
     
229.     if typeof(predictions[1]) <: FloatingPoint
     
230.         return float(predictions)
     
231.     else
     
232.         return predictions
     
233.     end
     
234. end
     
235. 
     
236. function build_forest(labels::Vector, features::Matrix, nsubfeatures::Integer, ntrees::Integer, partialsampling=0.7)
     
237.     partialsampling = partialsampling > 1.0 ? 1.0 : partialsampling
     
238.     Nlabels = length(labels)
     
239.     Nsamples = int(partialsampling * Nlabels)
     
240.     forest = @parallel (vcat) for i in 1:ntrees
     
241.         inds = rand(1:Nlabels, Nsamples)
     
242.         build_tree(labels[inds], features[inds,:], nsubfeatures)
     
243.     end
     
244.     return Ensemble([forest;])
     
245. end
     
246. 
     
247. function apply_forest(forest::Ensemble, features::Vector)
     
248.     ntrees = length(forest)
     
249.     votes = Array(Any,ntrees)
     
250.     for i in 1:ntrees
     
251.         votes[i] = apply_tree(forest.trees[i],features)
     
252.     end
     
253.     if typeof(votes[1]) <: FloatingPoint
     
254.         return mean(votes)
     
255.     else
     
256.         return majority_vote(votes)
     
257.     end
     
258. end
     
259. 
     
260. function apply_forest(forest::Ensemble, features::Matrix)
     
261.     N = size(features,1)
     
262.     predictions = Array(Any,N)
     
263.     for i in 1:N
     
264.         predictions[i] = apply_forest(forest, squeeze(features[i,:],1))
     
265.     end
     
266.     if typeof(predictions[1]) <: FloatingPoint
     
267.         return float(predictions)
     
268.     else
     
269.         return predictions
     
270.     end
     
271. end
     
272. 
     
273. function build_adaboost_stumps(labels::Vector, features::Matrix, niterations::Integer)
     
274.     N = length(labels)
     
275.     weights = ones(N) / N
     
276.     stumps = Node[]
     
277.     coeffs = FloatingPoint[]
     
278.     for i in 1:niterations
     
279.         new_stump = build_stump(labels, features, weights)
     
280.         predictions = apply_tree(new_stump, features)
     
281.         err = _weighted_error(labels, predictions, weights)
     
282.         new_coeff = 0.5 * log((1.0 + err) / (1.0 - err))
     
283.         matches = labels .== predictions
     
284.         weights[!matches] *= exp(new_coeff)
     
285.         weights[matches] *= exp(-new_coeff)
     
286.         weights /= sum(weights)
     
287.         push!(coeffs, new_coeff)
     
288.         push!(stumps, new_stump)
     
289.         if err < 1e-6
     
290.             break
     
291.         end
     
292.     end
     
293.     return (Ensemble(stumps), coeffs)
     
294. end
     
295. 
     
296. function apply_adaboost_stumps(stumps::Ensemble, coeffs::Vector{FloatingPoint}, features::Vector)
     
297.     nstumps = length(stumps)
     
298.     counts = Dict()
     
299.     for i in 1:nstumps
     
300.         prediction = apply_tree(stumps.trees[i], features)
     
301.         counts[prediction] = get(counts, prediction, 0.0) + coeffs[i]
     
302.     end
     
303.     top_prediction = stumps.trees[1].left.majority
     
304.     top_count = -Inf
     
305.     for (k,v) in counts
     
306.         if v > top_count
     
307.             top_prediction = k
     
308.             top_count = v
     
309.         end
     
310.     end
     
311.     return top_prediction
     
312. end
     
313. 
     
314. function apply_adaboost_stumps(stumps::Ensemble, coeffs::Vector{FloatingPoint}, features::Matrix)
     
315.     N = size(features,1)
     
316.     predictions = Array(Any,N)
     
317.     for i in 1:N
     
318.         predictions[i] = apply_adaboost_stumps(stumps, coeffs, squeeze(features[i,:],1))
     
319.     end
     
320.     return predictions
     
321. end
     
322. 
     
323. function show(io::IO, leaf::Leaf)
     
324.     println(io, "Decision Leaf")
     
325.     println(io, "Majority: $(leaf.majority)")
     
326.     print(io,   "Samples:  $(length(leaf.values))")
     
327. end
     
328. 
     
329. function show(io::IO, tree::Node)
     
330.     println(io, "Decision Tree")
     
331.     println(io, "Leaves: $(length(tree))")
     
332.     print(io,   "Depth:  $(depth(tree))")
     
333. end
     
334. 
     
335. function show(io::IO, ensemble::Ensemble)
     
336.     println(io, "Ensemble of Decision Trees")
     
337.     println(io, "Trees:      $(length(ensemble))")
     
338.     println(io, "Avg Leaves: $(mean([length(tree) for tree in ensemble.trees]))")
     
339.     print(io,   "Avg Depth:  $(mean([depth(tree) for tree in ensemble.trees]))")
     
340. end
     
341. 
     
342. 
     
343. ### Regression ###
     
344. 
     
345. function _split_mse{T<:FloatingPoint, U<:Real}(labels::Vector{T}, features::Matrix{U}, nsubfeatures::Int)
     
346.     nr, nf = size(features)
     
347.     best = NO_BEST
     
348.     best_val = -Inf
     
349. 
     
350.     if nsubfeatures > 0
     
351.         r = randperm(nf)
     
352.         inds = r[1:nsubfeatures]
     
353.     else
     
354.         inds = 1:nf
     
355.     end
     
356. 
     
357.     for i in inds
     
358.         if nr > 100
     
359.             features_i = features[:,i]
     
360.             domain_i = quantile(features_i, linspace(0.01, 0.99, 99))
     
361.             labels_i = labels
     
362.         else
     
363.             ord = sortperm(features[:,i])
     
364.             features_i = features[ord,i]
     
365.             domain_i = features_i
     
366.             labels_i = labels[ord]
     
367.         end
     
368.         for thresh in domain_i[2:end]
     
369.             value = _mse_loss(labels_i, features_i, thresh)
     
370.             if value > best_val
     
371.                 best_val = value
     
372.                 best = (i, thresh)
     
373.             end
     
374.         end
     
375.     end
     
376.     return best
     
377. end
     
378. 
     
379. function build_stump{T<:FloatingPoint, U<:Real}(labels::Vector{T}, features::Matrix{U})
     
380.     S = _split_mse(labels, features, 0)
     
381.     if S == NO_BEST
     
382.         return Leaf(mean(labels), labels)
     
383.     end
     
384.     id, thresh = S
     
385.     split = features[:,id] .< thresh
     
386.     return Node(id, thresh,
     
387.                 Leaf(mean(labels[split]), labels[split]),
     
388.                 Leaf(mean(labels[!split]), labels[!split]))
     
389. end
     
390. 
     
391. function build_tree{T<:FloatingPoint, U<:Real}(labels::Vector{T}, features::Matrix{U}, maxlabels=5, nsubfeatures=0)
     
392.     if length(labels) <= maxlabels
     
393.         return Leaf(mean(labels), labels)
     
394.     end
     
395.     S = _split_mse(labels, features, nsubfeatures)
     
396.     if S == NO_BEST
     
397.         return Leaf(mean(labels), labels)
     
398.     end
     
399.     id, thresh = S
     
400.     split = features[:,id] .< thresh
     
401.     return Node(id, thresh,
     
402.                 build_tree(labels[split], features[split,:], maxlabels, nsubfeatures),
     
403.                 build_tree(labels[!split], features[!split,:], maxlabels, nsubfeatures))
     
404. end
     
405. 
     
406. function build_forest{T<:FloatingPoint, U<:Real}(labels::Vector{T}, features::Matrix{U}, nsubfeatures::Integer, ntrees::Integer, maxlabels=0.5, partialsampling=0.7)
     
407.     partialsampling = partialsampling > 1.0 ? 1.0 : partialsampling
     
408.     Nlabels = length(labels)
     
409.     Nsamples = int(partialsampling * Nlabels)
     
410.     forest = @parallel (vcat) for i in 1:ntrees
     
411.         inds = rand(1:Nlabels, Nsamples)
     
412.         build_tree(labels[inds], features[inds,:], maxlabels, nsubfeatures)
     
413.     end
     
414.     return Ensemble([forest;])
     
415. end
     
416. 
     
417. 
     
418. end # module

复制代码

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：Decision Julia Using CISI Tree convert values start