-
Notifications
You must be signed in to change notification settings - Fork 2
/
detect.go
135 lines (106 loc) · 2.73 KB
/
detect.go
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
package impact
import (
"math/rand"
"os"
"runtime"
"strconv"
"sync"
"time"
"github.com/drewlanenga/govector"
)
// the operator indicates whether the candidate series has increased,
// decreased or stayed largely the same
type Operator int
type series govector.Vector
const (
EQUALS Operator = 0
GREATER_THAN Operator = 1
LESS_THAN Operator = 2
)
var (
smoother uint = 2 // the amount of smoothing on either side
rnd = rand.New(rand.NewSource(time.Now().UnixNano()))
rndMutex = &sync.Mutex{}
)
func walks(niter, nsteps, ncpu int, start float64, history govector.Vector) series {
destinations := make(series, niter)
steps := history.Diff()
c := make(chan int, ncpu)
for i := 0; i < niter; i++ {
go destinations.walk(i, nsteps, start, steps, c)
}
// drain the channel
for i := 0; i < ncpu; i++ {
<-c // wait for one task to complete
}
// all done
return destinations
}
// take random steps in a walk based on the `diff`. (`diff` is a bunch of steps.)
func (s series) walk(i, nsteps int, start float64, diff govector.Vector, c chan int) {
walkrnd := rand.New(rand.NewSource(time.Now().UnixNano()))
n := len(diff)
dest := start
for i := 0; i < nsteps; i++ {
which := walkrnd.Intn(n)
dest += diff[which]
}
s[i] = dest
c <- 1 // signal that the walk has finished
}
// DetectImpact performs Monte Carlo based changepoint detection between two disjoint
// and adjacent subseries of a larger time series. Increase `niter` to improve
// accuracy of the detection.
func DetectImpact(x1, x2 []float64, niter int) (float64, Operator, error) {
v1, err := govector.AsVector(x1)
if err != nil {
return 0.0, EQUALS, err
}
v2, err := govector.AsVector(x2)
if err != nil {
return 0.0, EQUALS, err
}
x1smooth := v1.Smooth(smoother, smoother)
x2smooth := v2.Smooth(smoother, smoother)
x1diff := x1smooth.Diff()
ncpu, _ := strconv.Atoi(os.Getenv("GOMAXPROCS"))
if ncpu == 0 {
ncpu = runtime.NumCPU()
}
runtime.GOMAXPROCS(ncpu)
// the final destinations of a bunch of random walks
simDest := walks(niter, len(x2), ncpu, x1smooth[len(x1)-1], x1diff)
realDest := x2smooth[len(x2)-1]
plower := float64(lt(realDest, simDest)) / float64(niter)
pupper := float64(gt(realDest, simDest)) / float64(niter)
p := 1.0
op := EQUALS
if plower < pupper {
p = plower
op = LESS_THAN
} else if pupper < plower {
p = pupper
op = GREATER_THAN
}
return p, op, nil
}
// count the number of xs greater than x
func gt(x float64, xs []float64) int {
count := 0
for _, value := range xs {
if x < value {
count++
}
}
return count
}
// count the number of xs less than x
func lt(x float64, xs []float64) int {
count := 0
for _, value := range xs {
if x > value {
count++
}
}
return count
}