improve              package:subselect              R Documentation

_R_e_s_t_r_i_c_t_e_d _L_o_c_a_l _I_m_p_r_o_v_e_m_e_n_t _s_e_a_r_c_h _f_o_r _a_n _o_p_t_i_m_a_l _k-_v_a_r_i_a_b_l_e _s_u_b_s_e_t

_D_e_s_c_r_i_p_t_i_o_n:

     Given a set of variables,  a Restricted Local Improvement
     algorithm seeks a k-variable subset which is optimal, as a
     surrogate for the whole set, with respect to a given criterion.

_U_s_a_g_e:

     improve( mat, kmin, kmax = kmin, nsol = 1, exclude = NULL,
     include = NULL, setseed = FALSE, criterion = "RM", pcindices="first_k",
     initialsol = NULL, force = FALSE, tolval=10*.Machine$double.eps)

_A_r_g_u_m_e_n_t_s:

     mat: a covariance or correlation matrix of the variables from
          which the k-subset is to be selected.

    kmin: the cardinality of the smallest subset that is wanted.

    kmax: the cardinality of the largest subset that is wanted.

    nsol: the number of different subsets (runs of the algorithm)
          wanted.

 exclude: a vector of variables (referenced by their row/column numbers
          in matrix 'mat') that are to be forcibly excluded from the
          subsets.

 include: a vector of variables (referenced by their row/column numbers
          in matrix 'mat') that are to be forcibly included from the
          subsets.

 setseed: logical variable indicating whether to fix an initial  seed
          for the random number generator, which will be re-used in
          future calls to this function whenever setseed is again set
          to TRUE.

criterion: Character variable, which indicates which criterion is to be
          used in judging the quality of the subsets. Currently, only
          the RM, RV and GCD criteria are supported, and referenced as
          "RM", "RV" or "GCD" (see References, 'rm.coef',  'rv.coef'
          and 'gcd.coef' for further details).

pcindices: either a vector of ranks of Principal Components that are to
          be used for comparison with the k-variable subsets (for the
          GCD criterion only, see 'gcd.coef') or the default text
          'first_k'. The latter will associate PCs 1 to _k_ with each
          cardinality _k_ that has been requested by the user.

initialsol: vector, matrix or 3-d array of initial solutions for the
          restricted local improvement search. If a _single
          cardinality_ is  required, 'initialsol' may be a vector of
          length _k_(accepted even if 'nsol' > 1, in which case it is
          used as the initial solution for all 'nsol' final solutions
          that are requested with a warning that the same initial
          solution necessarily produces the same final solution);  a 1
          x _k_ matrix (as produced by the '$bestsets' output value of
          the algorithm functions 'anneal', 'genetic', or 'improve'),
          or a 1 x _k_ x 1 array (as produced by the '$subsets' output
          value), in which case it will be treated as the above
          k-vector; or an 'nsol' x 'k' matrix, or  'nsol' x 'k' x 1 3-d
          array, in which case each row (dimension 1) will be used  as
          the initial solution for each of the 'nsol' final solutions
          requested. If _more than one cardinality_ is requested,
          'initialsol' can be a  'length(kmin:kmax)' x 'kmax' matrix
          (as produced by the '$bestsets' option of the algorithm
          functions) (even if 'nsol' > 1, in which case each row will
          be replicated to produced the initial solution for all 'nsol'
          final solutions requested in each cardinality, with a warning
          that a single initial solution necessarily produces identical
          final solutions), or a 'nsol' x 'kmax' x 'length(kmin:kmax)'
          3-d array (as produced by the  '$subsets' output option), in
          which case each row (dimension 1) is interpreted as a
          different initial solution.

          If the 'exclude' and/or 'include' options are used,
          'initialsol' must also respect those requirements. 

   force: a logical variable indicating whether, for large data sets
          (currently 'p' > 400) the algorithm should proceed anyways,
          regardless of possible memory problems which may crash the R
          session.

  tolval: the tolerance level for the reciprocal of the 2-norm
          condition number of the correlation/covariance matrix, i.e.,
          for the ratio of the smallest to the largest eigenvalue of
          the input matrix. Matrices with a reciprocal of the condition
          number smaller than 'tolval' will abort the search algorithm.

_D_e_t_a_i_l_s:

     An initial k-variable subset (for k ranging from 'kmin' to 'kmax')
      of a full set of p  variables is randomly selected and the
     variables not belonging to this subset are placed in a queue. The
     possibility of replacing a variable in the current k-subset with a
     variable from the queue is then explored.   More precisely, a
     variable is selected, removed from the queue, and the  k values of
     the criterion which would result from swapping this selected
     variable with each variable in the current subset are computed. If
     the best of these values improves the current criterion value, the
     current subset is updated accordingly. In this case, the variable
     which leaves the subset is added to the queue, but only if it has
     not previously been in the queue (i.e., no variable can enter the
     queue twice). The algorithm proceeds until the queue is emptied.  

     The user may force variables to be included and/or excluded from
     the k-subsets, and may specify initial solutions.

     For each cardinality k, the total number of calls to the procedure
     which computes the criterion  values is O('nsol' x k x p). These
     calls are the dominant computational effort in each iteration of
     the algorithm.  

     In order to improve computation times, the bulk of computations
     are carried out in a Fortran routine. Further details about the
     algorithm can be found in Reference 1 and in the comments to the
     Fortran code (in the 'src' subdirectory for this package). For
     datasets with a very large number of variables (currently p >
     400), it is  necessary to set the 'force' argument to TRUE for the
     function to run, but this may cause a session crash if there is
     not enough memory available.

     The function checks for ill-conditioning of the input matrix
     (specifically, it checks whether the ratio of the input matrix's
     smallest and largest eigenvalues is less than 'tolval'). For an
     ill-conditioned input matrix, execution is aborted. The function
     'trim.matrix' may be used to obtain a well-conditioned input
     matrix.

_V_a_l_u_e:

     A list with five items:

 subsets: An 'nsol' x 'kmax' x length('kmin':'kmax') 3-dimensional
          array, giving for each cardinality (dimension 3) and each
          solution (dimension 1) the list of variables (referenced by
          their row/column numbers in matrix 'mat') in the subset
          (dimension 2). (For cardinalities smaller than 'kmax', the
          extra final positions are set to zero).

  values: An 'nsol' x length('kmin':'kmax') matrix, giving for each
          cardinality (columns), the criterion values of the 'nsol'
          (rows) solutions obtained.

bestvalues: A length('kmin':'kmax') vector giving the best values of
          the criterion obtained for each cardinality.

bestsets: A length('kmin':'kmax') x 'kmax' matrix, giving, for each
          cardinality (rows), the variables (referenced by their
          row/column numbers in matrix 'mat') in the best k-subset that
          was found.

    call: The function call which generated the output.

_R_e_f_e_r_e_n_c_e_s:

     1) Cadima, J., Cerdeira, J. Orestes and Minhoto, M. (2004)
     Computational aspects of algorithms for variable selection in the
     context of principal components. _Computational Statistics & Data
     Analysis_, 47, 225-236.

     2) Cadima, J. and Jolliffe, I.T. (2001). Variable Selection and
     the Interpretation of Principal Subspaces, _Journal of
     Agricultural, Biological and Environmental Statistics_, Vol. 6,
     62-79.

_S_e_e _A_l_s_o:

     'rm.coef', 'rv.coef', 'gcd.coef', 'genetic', 'anneal', 'leaps',
     'trim.matrix'.

_E_x_a_m_p_l_e_s:

     # For illustration of use, a small data set with very few iterations
     # of the algorithm. 
     #

     data(swiss)
     improve(cor(swiss),2,3,nsol=4,criterion="GCD")
     ## $subsets
     ## , , Card.2
     ##
     ##            Var.1 Var.2 Var.3
     ## Solution 1     3     6     0
     ## Solution 2     3     6     0
     ## Solution 3     3     6     0
     ## Solution 4     3     6     0
     ##
     ## , , Card.3
     ##
     ##            Var.1 Var.2 Var.3
     ## Solution 1     4     5     6
     ## Solution 2     4     5     6
     ## Solution 3     4     5     6
     ## Solution 4     4     5     6
     ##
     ##
     ## $values
     ##               card.2   card.3
     ## Solution 1 0.8487026 0.925372
     ## Solution 2 0.8487026 0.925372
     ## Solution 3 0.8487026 0.925372
     ## Solution 4 0.8487026 0.925372
     ##
     ## $bestvalues
     ##    Card.2    Card.3 
     ## 0.8487026 0.9253720 
     ##
     ## $bestsets
     ##        Var.1 Var.2 Var.3
     ## Card.2     3     6     0
     ## Card.3     4     5     6
     ##
     ##$call
     ##improve(cor(swiss), 2, 3, nsol = 4, criterion = "GCD")

     #
     #
     # Forcing the inclusion of variable 1 in the subset
     #

      improve(cor(swiss),2,3,nsol=4,criterion="GCD",include=c(1))

     ## $subsets
     ## , , Card.2
     ##
     ##            Var.1 Var.2 Var.3
     ## Solution 1     1     6     0
     ## Solution 2     1     6     0
     ## Solution 3     1     6     0
     ## Solution 4     1     6     0
     ##
     ## , , Card.3
     ##
     ##            Var.1 Var.2 Var.3
     ## Solution 1     1     5     6
     ## Solution 2     1     5     6
     ## Solution 3     1     5     6
     ## Solution 4     1     5     6
     ##
     ##
     ## $values
     ##               card.2    card.3
     ## Solution 1 0.7284477 0.8048528
     ## Solution 2 0.7284477 0.8048528
     ## Solution 3 0.7284477 0.8048528
     ## Solution 4 0.7284477 0.8048528
     ##
     ## $bestvalues
     ##    Card.2    Card.3 
     ## 0.7284477 0.8048528 
     ##
     ## $bestsets
     ##        Var.1 Var.2 Var.3
     ## Card.2     1     6     0
     ## Card.3     1     5     6
     ##
     ##$call
     ##improve(cor(swiss), 2, 3, nsol = 4, criterion = "GCD", include = c(1))

