SHOGUN  v2.0.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 <stdlib.h>
21 #include <stdio.h>
22 #include <time.h>
23 #include <math.h>
24
25
26 /*
27  * In this file, we propose the algorithms for solving the problem:
28  *
29  * min 1/2 \|x - u\|^2
30  * s.t. x1 \ge x2 \ge x3 \ge ... \ge xn \ge 0
31  *
32  *
33  */
34
35 /*
36  *
37  * x= sequence_bottomup(u,n)
38  *
39  * we compute using a bottom up order
40  *
41  */
42
43 void sequence_bottomup(double *x, double *u, int n){
44  int i, j;
45  int *location=(int *)malloc(sizeof(int)*n);
46  int num;
47
48  if(!location){
49  printf("\n Allocation of array failure!");
50  exit(1);
51  }
52
53
54  /*
55  * compute the maximal mean from the root to the i-th point:
56  *
57  * x[i]: the maximal mean
58  * location[i]: the ending index of the mean
59  *
60  */
61
62
63  /* process the last element*/
64  if (n<1){
65  printf("\n n=%d should be an integer over 1!",n);
66  exit(1);
67  }
68  else{
69  i=n-1;
70  x[i]=u[i];
71  location[i]=i;
72  }
73
74  /*process the remaining elements in a bottom-up recursive manner*/
75  for(i=n-2;i>=0;i--){
76
77
78  if (u[i]>x[i+1]){
79  x[i]=u[i];
80  location[i]=i;
81  }
82  else{
83  /*make use of x[i: (n-1)] and location[i: (n-1)] for update*/
84
85  /*merge with the first group*/
86  num=location[i+1]-i;
87  x[i]=(u[i] + x[i+1]*num)/(num+1);
88  location[i]=location[i+1];
89  j=location[i+1]+1;
90
91  /*If necessary, we need to further merge with the remainig groups */
92  for(;j<n;){
93  if(x[i] <= x[j]){
94
95  num=location[j]-j +1;
96  x[i]=( x[i]* (j-i) + x[j]* num ) / (location[j] -i +1);
97  location[i]=location[j];
98
99  j=location[j]+1;
100  }
101  else
102  break;
103  }
104  }
105  }
106
107  /*
108  for(i=0;i<30;i++)
109  printf("\n x[%d]=%2.5f, location[%d]=%d",i+1, x[i], i+1, location[i]+1);
110  */
111
112  /*
113  * compute the solution x with the mean and location
114  *
115  */
116
117  for(i=0;i<n;){
118
119  if (x[i]>0){
120  for(j=i+1;j<=location[i];j++){
121  x[j]=x[i];
122  }
123
124  i=location[i]+1;
125  }
126  else{
127  for(j=i;j<n;j++)
128  x[j]=0;
129  break;
130  }
131  }
132
133  free(location);
134 }
135
136
137 /*
138  *
139  * x= sequence_topdown(u,n)
140  *
141  * we compute using a top to down order
142  *
143  */
144
145 void sequence_topdown(double *x, double *u, int n){
146  int i, j;
147  double sum, max, mean;
148  int num;
149  int *location=(int *)malloc(sizeof(int)*n);
150
151
152  if(!location){
153  printf("\n Allocation of array failure!");
154  exit(1);
155  }
156
157  for(i=0;i<n;){
158
159  /*
160  * From each root node i, we compute the maximal mean from.
161  *
162  */
163
164  max=0;
165  location[i]=i;
166
167  sum=0;
168  num=1;
169  for(j=i;j<n;j++){
170  sum+=u[j];
171  mean=sum/num;
172  num++;
173
174  /* record the most largest mean and the location*/
175  if (mean >= max){
176  max=mean;
177  location[i]=j;
178  }
179  }
180
181  if (max>0){
182  x[i]=max; /*record the maximal mean*/
183  i=location[i]+1; /*the next i*/
184  }
185  else{
186  x[i]=-1; /* any value less or equal to 0
187  *
188  * This shows that the remaining elements should be zero
189  *
190  */
191  break;
192  }
193  }
194
195
196  /*
197  * compute the solution x with the mean and location
198  *
199  */
200
201  for(i=0;i<n;){
202
203  if (x[i]>0){
204  for(j=i+1;j<=location[i];j++){
205  x[j]=x[i];
206  }
207
208  i=location[i]+1;
209  }
210  else{
211  for(j=i;j<n;j++)
212  x[j]=0;
213  break;
214  }
215  }
216
217  free(location);
218 }
219 #endif /* ----- #ifndef SEQUENCE_SLEP ----- */
220

SHOGUN Machine Learning Toolbox - Documentation