SHOGUN  4.2.0
sequence.h
Go to the documentation of this file.
1 /* This program is free software: you can redistribute it and/or modify
3  * the Free Software Foundation, either version 3 of the License, or
4  * (at your option) any later version.
5  *
6  * This program is distributed in the hope that it will be useful,
7  * but WITHOUT ANY WARRANTY; without even the implied warranty of
8  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
9  * GNU General Public License for more details.
10  *
11  * You should have received a copy of the GNU General Public License
12  * along with this program. If not, see <http://www.gnu.org/licenses/>.
13  *
14  * Copyright (C) 2009 - 2012 Jun Liu and Jieping Ye
15  */
16
17 #ifndef SEQUENCE_SLEP
18 #define SEQUENCE_SLEP
19
20 #include <shogun/lib/config.h>
21
22 #ifdef USE_GPL_SHOGUN
23
24 #include <stdlib.h>
25 #include <stdio.h>
26 #include <time.h>
27 #include <math.h>
28
29
30 /*
31  * In this file, we propose the algorithms for solving the problem:
32  *
33  * min 1/2 \|x - u\|^2
34  * s.t. x1 \ge x2 \ge x3 \ge ... \ge xn \ge 0
35  *
36  *
37  */
38
39 /*
40  *
41  * x= sequence_bottomup(u,n)
42  *
43  * we compute using a bottom up order
44  *
45  */
46
47 void sequence_bottomup(double *x, double *u, int n){
48  int i, j;
49  int *location=(int *)malloc(sizeof(int)*n);
50  int num;
51
52  if(!location){
53  printf("\n Allocation of array failure!");
54  exit(1);
55  }
56
57
58  /*
59  * compute the maximal mean from the root to the i-th point:
60  *
61  * x[i]: the maximal mean
62  * location[i]: the ending index of the mean
63  *
64  */
65
66
67  /* process the last element*/
68  if (n<1){
69  printf("\n n=%d should be an integer over 1!",n);
70  exit(1);
71  }
72  else{
73  i=n-1;
74  x[i]=u[i];
75  location[i]=i;
76  }
77
78  /*process the remaining elements in a bottom-up recursive manner*/
79  for(i=n-2;i>=0;i--){
80
81
82  if (u[i]>x[i+1]){
83  x[i]=u[i];
84  location[i]=i;
85  }
86  else{
87  /*make use of x[i: (n-1)] and location[i: (n-1)] for update*/
88
89  /*merge with the first group*/
90  num=location[i+1]-i;
91  x[i]=(u[i] + x[i+1]*num)/(num+1);
92  location[i]=location[i+1];
93  j=location[i+1]+1;
94
95  /*If necessary, we need to further merge with the remainig groups */
96  for(;j<n;){
97  if(x[i] <= x[j]){
98
99  num=location[j]-j +1;
100  x[i]=( x[i]* (j-i) + x[j]* num ) / (location[j] -i +1);
101  location[i]=location[j];
102
103  j=location[j]+1;
104  }
105  else
106  break;
107  }
108  }
109  }
110
111  /*
112  for(i=0;i<30;i++)
113  printf("\n x[%d]=%2.5f, location[%d]=%d",i+1, x[i], i+1, location[i]+1);
114  */
115
116  /*
117  * compute the solution x with the mean and location
118  *
119  */
120
121  for(i=0;i<n;){
122
123  if (x[i]>0){
124  for(j=i+1;j<=location[i];j++){
125  x[j]=x[i];
126  }
127
128  i=location[i]+1;
129  }
130  else{
131  for(j=i;j<n;j++)
132  x[j]=0;
133  break;
134  }
135  }
136
137  free(location);
138 }
139
140
141 /*
142  *
143  * x= sequence_topdown(u,n)
144  *
145  * we compute using a top to down order
146  *
147  */
148
149 void sequence_topdown(double *x, double *u, int n){
150  int i, j;
151  double sum, max, mean;
152  int num;
153  int *location=(int *)malloc(sizeof(int)*n);
154
155
156  if(!location){
157  printf("\n Allocation of array failure!");
158  exit(1);
159  }
160
161  for(i=0;i<n;){
162
163  /*
164  * From each root node i, we compute the maximal mean from.
165  *
166  */
167
168  max=0;
169  location[i]=i;
170
171  sum=0;
172  num=1;
173  for(j=i;j<n;j++){
174  sum+=u[j];
175  mean=sum/num;
176  num++;
177
178  /* record the most largest mean and the location*/
179  if (mean >= max){
180  max=mean;
181  location[i]=j;
182  }
183  }
184
185  if (max>0){
186  x[i]=max; /*record the maximal mean*/
187  i=location[i]+1; /*the next i*/
188  }
189  else{
190  x[i]=-1; /* any value less or equal to 0
191  *
192  * This shows that the remaining elements should be zero
193  *
194  */
195  break;
196  }
197  }
198
199
200  /*
201  * compute the solution x with the mean and location
202  *
203  */
204
205  for(i=0;i<n;){
206
207  if (x[i]>0){
208  for(j=i+1;j<=location[i];j++){
209  x[j]=x[i];
210  }
211
212  i=location[i]+1;
213  }
214  else{
215  for(j=i;j<n;j++)
216  x[j]=0;
217  break;
218  }
219  }
220
221  free(location);
222 }
223 #endif //USE_GPL_SHOGUN
224 #endif /* ----- #ifndef SEQUENCE_SLEP ----- */
225
Matrix::Scalar max(Matrix m)
Definition: Redux.h:68

SHOGUN Machine Learning Toolbox - Documentation