source: trunk/greenstone3-extensions/vishnu/src/vishnu/sammon/Sammon.java@ 8189

Last change on this file since 8189 was 8189, checked in by kjdon, 20 years ago

first version of Imperial College's Visualiser code
  • Property svn:executable set to *
  • Property svn:keywords set to Author Date Id Revision
File size: 7.3 KB
Line 
1
2/**
3 * Title: jsammon<p>
4 * Description: Java implementation of restricted sammon map algorithm<p>
5 * Copyright: Copyright (c) Matthew Carey & Shalini Sewraz<p>
6 * Company: <p>
7 * @author Matthew Carey & Shalini Sewraz
8 * @version 1.0
9 */
10package vishnu.sammon;
11
12import java.io.*;
13import java.util.*;
14import vishnu.datablock.Point2D;
15
16public class Sammon
17{
18
19
20 public static final double MF = 0.3; /* Magic Factor */
21 public static final double _MAX_Err = 0.00005; /* Max Mapping Error */
22 public static final int _MAX_M = 1000; /* Max Iteration Number */
23 public static final int _MAX_N = 1000; /* Max Number of Entries */
24 public static final int _MAX_L = 128; /* Max Dimension for X */
25
26
27 double[][] Xs;
28 double[][] Ys;
29 int number;
30 int dimension;
31 double total_Xs_dists;
32/* SS298: Added function for scaling values between 0 and 1
33* n : number of entries
34*/
35 void scale_values(int n)
36 {
37
38 // get the maximum and the minimum of Ys array
39
40 // get the maximum and the minimum of Ys array
41
42 double maxX = Ys[0][0];
43 double minX = Ys[0][0];
44 double maxY = Ys[0][1];
45 double minY = Ys[0][1];
46
47 int i;
48 for (i = 1 ; i < n ; i++)
49 {
50
51 if (maxX < Ys[i][0]) maxX = Ys[i][0];
52 if (minX > Ys[i][0]) minX = Ys[i][0];
53 if (maxY < Ys[i][1]) maxY = Ys[i][1];
54 if (minY > Ys[i][1]) minY = Ys[i][1];
55 }
56 maxY -= minY;
57 maxX -= minX;
58 for (i = 0 ; i < n ; i++)
59 {
60 if (maxX > 0)
61 {
62 Ys[i][0] -= minX;
63 Ys[i][0] /= maxX;
64 Ys[i][0] *=0.8;
65 Ys[i][0] +=0.1;
66 }
67 else Ys[i][0]=0.5;
68 if (maxY > 0)
69 {
70 Ys[i][1] -= minY;
71 Ys[i][1] /= maxY;
72 Ys[i][1] *= 0.8;
73 Ys[i][1] += 0.1;
74 }
75 else Ys[i][1]=0.5;
76 }
77
78 }
79
80
81
82/* return a Euclidean distance between two 'd'-dimensional vectors 'xs' and 'ys'
83*/
84 double eucl_dist(int d, double[] xs, double[] ys)
85 {
86 double ans=0.0;
87 double tmp;
88 int i;
89 for(i=0;i<d;i++)
90 {
91 tmp = xs[i]-ys[i];
92 ans += tmp * tmp;
93 }
94 return Math.sqrt(ans);
95 }
96
97
98/* n - number of entries
99* d - dimension
100* post:
101* return an array of eucidean distances for X
102* and assign its total distance (will be used in the mapping error) to 'total'
103*/
104 double[] compute_Xs_eucl_dists()
105 {
106 double tmp[];
107 int i,j,k;
108 tmp = new double[number*(number-1)/2];
109
110 total_Xs_dists=0.0;
111 k=0;
112 for(i=1;i<number;i++)
113 for(j=0;j<i;j++)
114 {
115 tmp[k] = eucl_dist(dimension, Xs[i], Xs[j]);
116 total_Xs_dists+=tmp[k];
117 k++;
118 }
119 return tmp;
120 }
121
122
123 public Point2D [] getMapping()
124 {
125 Point2D [] sam = new Point2D[Ys.length];
126 for (int c=0;c<Ys.length;c++)
127 {
128 float fx = (float) Ys[c][0];
129 float fy = (float) Ys[c][1];
130 sam[c]=new Point2D(fx,fy);
131 }
132 return sam;
133
134 }
135
136
137
138/*----------------------------------------------------------------*/
139
140 public Sammon(double [][] centroids)
141 {
142
143 int i, j, m, p;
144 double[] Xs_dists;
145
146 double dist_star,dist, alpha, beta, gamma, zeta, err;
147 double uppDer0, uppDer1, lowDer0, lowDer1;
148 double maxX=0.0;
149 double minX=0.0;
150 double maxY=0.0;
151 double minY=0.0;
152
153
154 number = centroids.length;
155 dimension = centroids[0].length;
156
157 Xs = centroids;
158 Ys = new double[number][2];
159
160
161 /*
162 for (i=0;i<number;i++)
163 {
164 for(p=0;p<dimension;p++)
165 System.out.print(Xs[i][p]+" ");
166 System.out.println();
167 }
168 */
169 Xs_dists = compute_Xs_eucl_dists();
170
171 //System.out.println("X dists length "+ Xs_dists.length);
172 /* ??????????????????????????????????? */
173
174 p=0;
175 for (i=0;i<number;i++)
176 {
177 Ys[i][0] = Xs[i][0];
178 double value = Xs_dists.length>0?Xs_dists[(i==(number-1))?i:p]:
179 0.0;
180 Ys[i][1] = Xs[i][0]+value;
181 p+=(number-(i+1));
182 }
183
184 m=0; /* iteration counter */
185 do{
186
187 for(p=0;p<number;p++)
188 {
189 uppDer0=uppDer1=lowDer0=lowDer1=0.0;
190 /* calcuate partial derivatives */
191 for(j=0;j<number;j++)
192 {
193 if (p==j) continue;
194 dist_star = Xs_dists[(j>p) ? (j*(j-1)/2+p) : (p*(p-1)/2+j)];
195
196 dist = eucl_dist(2,Ys[p],Ys[j]);
197 if (dist == 0) dist = 0.00001;
198 alpha = dist_star-dist;
199 beta = dist_star*dist;
200 if (beta == 0) beta = 0.00000000000001;
201 gamma = alpha/beta;
202
203 /* 1st dimension */
204 zeta = Ys[p][0]-Ys[j][0];
205 uppDer0 += gamma * zeta;
206 lowDer0 += (alpha-(zeta*zeta/dist) * (1+alpha/dist))/beta;
207
208 /* 2nd dimension */
209 zeta = Ys[p][1]-Ys[j][1];
210 uppDer1 += gamma * zeta;
211 lowDer1 += (alpha-(zeta*zeta/dist) * (1+alpha/dist))/beta;
212 } /* for */
213
214 Ys[p][0] = Ys[p][0]+MF*uppDer0/Math.abs(lowDer0);
215 Ys[p][1] = Ys[p][1]+MF*uppDer1/Math.abs(lowDer1);
216 if(p==0)
217 {
218 maxX = Ys[0][0];
219 minX = Ys[0][0];
220 maxY = Ys[0][1];
221 minY = Ys[0][1];
222 }
223 else
224 {
225 if (maxX < Ys[p][0]) maxX = Ys[p][0];
226 if (minX > Ys[p][0]) minX = Ys[p][0];
227 if (maxY < Ys[p][1]) maxY = Ys[p][1];
228 if (minY > Ys[p][1]) minY = Ys[p][1];
229 }
230
231
232 } /* for */
233
234 /* calcuate the mapping error */
235 err=0.0;
236 p=0;
237 for(j=1;j<number;j++)
238 for(i=0;i<j;i++)
239 {
240 dist_star = Xs_dists[p++];
241 alpha = dist_star - eucl_dist(2,Ys[j],Ys[i]);
242 err += (alpha*alpha/dist_star);
243 }
244 err=err / total_Xs_dists;
245
246 m++;
247 } while ((err>_MAX_Err) && (m!=_MAX_M));
248 // This is ugly desperate measures
249 if(maxY==minY)
250 {
251 System.out.println("Warning: simulated 'y' values in mapping");
252 for(p=0;p<number;p++)
253 Ys[p][1]=Math.random();
254 }
255 if(maxX==minX)
256 {
257 System.out.println("Warning: simulated 'x' values in mapping");
258 for(p=0;p<number;p++)
259 Ys[p][0]=Math.random();
260 }
261
262 scale_values(number);
263
264
265 /*for(i=0;i<number;i++)
266 System.out.println(Ys[i][0] + " " + Ys[i][1]);
267
268 System.out.println();
269 System.out.println();*/
270 }
271}
Note: See TracBrowser for help on using the repository browser.