(1) Given a distance measure between two vectors X and Y,
D(X,Y) = 1⁄2 { (var(X) + var(Y))2 - √[ (var(X) + var(Y))2 - 4 var(X) var(Y) (1-ρ(X,Y)2 ] }
ρ(x,y) = cov(X,Y)/√(var(X)var(Y)).
var(X) = (1/n) (∑(X-meanX)2), where n is the dimensionality of vector X.
cov(X,Y) = (1/n) (∑(X-meanX)(Y-meanY)), where both X and Y have the same dimensionality, n.
(2) Given a number of features (n), there exists a feature set O = {Fi, i= 1, 2... n}, which may be reducible. For the sake of this test, the features are represented by ‘feature vectors’ (e.g., X=<FV1, FV2, ... FVn>), where the dimensions of each and every vector is equal to the number of randomly-picked instances of a dataset used to construct the feature vectors (say 10% of the available instances).
(3) Implement the following cluster-density-reducing unsupervised feature selection algorithm (or CDR)
For every feature vector, compute the D distance between the vector and all other vectors; Find the smallest distance (>0) between any two vectors: call that D_min_global;
Let e = k x D_min_global (where k is a real-valued constant =>1 entered by the user);
Repeat {
For all vectors whose minimum D distance to another vector =~ D_min_global Do
{
Find a nearest vector (this will give you a pair of vectors, Va and Vb); Discard one of the pair of vectors (Va, Vb); // function description below
}
Re-compute D_min_global; // as the elimination of features will alter it }
Until (D_min_global > e)
Output retained features; // just a list of feature indexes, such as FV1, FV3, FV14.
Discard one of the pair of vectors (Va, Vb) { Create a vector_cluster = {Va,Vb};
Let k=2; // meaning 2nd nearest neighbour
10: If there are no more nearest neighbours Then { Randomly discard Va or Vb; Flip switch; Exit function };
}
Find the k-nearest_neighbour of Va and of Vb; // they may be two distinct vectors or the same one Let vector_cluster = vector_cluster + k-nearest_neighbour of Va and of Vb;
Calculate D_average of Va and of Vb to the other vectors in the vector_cluster;
If D_average of (Va>Vb) OR (Va<Vb) Do
{
If (switch = true) Then discard Va or Vb with lowest D_average Else discard the other; Switch = NOT(switch); // flip the Switch, where switch is a global Boolean variable
}
Else { k++; go to 10 } // in order to increase the size of the vector_cluster
(4) To solve the test, you will need to:
- Implementing & debugging the distance measure (described above)
- Possibly, adapt a nearest neighbor classifier to the needs of applying CDR to one of the data set below.
Description: [login to view URL]
Example code in Java: [login to view URL]
- Design & Implement a function to read from one of the data sets at:
[login to view URL] (e.g., REALDISP, Image Segmentation and Robot Execution
Failures datasets).
- Incrementally Implement & Debug the algorithm (CDR): first to compute D, then the Discard function and
finally, to implement the whole algorithm.
- Provide a theoretical assessment of the time complexity of CDR as a function of n (the initial number of
features); test your prediction empirically by running your program on sub-sets with different n values.
- Present the program & output file and a written report on the results- especially, theoretical & empirical
time scalability results.
Marks are out of 100% and they are assigned as follows: 35% accurate & efficient Java or C++ program implementation of the CDR algorithm (USB key); 15% a complete output file exhibiting feature reduction for one dataset (USB key); 15% correct theoretical analysis of the order of time complexity of your implementation (paper); 35% correct analysis of the empirical time-performance of your program, with justification for any divergence between it and the theoretical analysis (on paper). Attach a completed & signed statement of originality form to your submission.
We are the leading young professional software development organization having extensive technical expertise and knowledge in developing, managing, optimizing and customizing software’s by implementing these software’s in different demanding programming tools and latest technologies especially in Linux, C++, C #, Java.
We have fully studied your project requirements description and also highlight main points in order to perform your demands which is required to complete the project in a given proposed time frame, as our commitment is a key to our successful journey which also inspired our employers who gave us the full rating on our completed projects as a "Project Completion Rate" which is also shown in our profile. Moreover we are also fully committed to accomplish the task assigned by you with the required state of the art technology to fulfill your requirements as prescribed in this project.
I thinks that this is the best way to utilize our impressive skills under the light of our previous experiences and excellent reviews given by the employers. We wish to render you our services and hopeful not to let you disappoint. We will also be responsive with a positive gesture without demanding any further cost. We are quite optimistic in a bid to receive this project.
Thanks
With Best Regards
Your Well Wisher
Motivated Young Freelancer