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

SHOGUN Machine Learning Toolbox - Documentation