cluster-density-reducing unsupervised feature selection algorithm

(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: [url removed, login to view]

Example code in Java: [url removed, login to view]

- Design & Implement a function to read from one of the data sets at:

[url removed, login to view] (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.

工程 Java

项目ID： #6687856

关于项目