proximus: Proximus

Description Usage Arguments Details Value Warning Note Author(s) References See Also Examples

View source: R/proximus.r

Description

Cluster the rows of a logical matrix using the Proximus algorithm. The compression rate of the algorithm can be influenced by the choice of the maximum cluster radius and the minimum cluster size.

Usage

1
2
proximus(x, max.radius = 2, min.size = 1, min.retry = 10,
         max.iter = 16, debug = FALSE)

Arguments

x

a logical matrix.

max.radius

the maximum number of bits a member in a row set may deviate from its dominant pattern.

min.size

the minimum split size of a row set.

min.retry

number of retries to split a pure rank-one approximation (translates into a resampling rate).

max.iter

the maximum number of iterations for finding a local rank-one approximation.

debug

optional debugging output.

Details

The intended area of application is the compression of high-dimensional binary data into representative patterns. For instance, purchase incidence (market basket data) or term-document matrices may be preprocessed by Proximus for later association rule mining.

The algorithm is of a recursive partitioning type. Specifically, at each step a binary split is attempted using a local rank-one approximation of the current submatrix (row set). That is a specialization of principal components to binary data which represents a matrix as the outer product of two binary vectors. The node expansion stops if a submatrix is pure, i.e., the column (presence set) vector indicates all the rows and the Hamming distances from the row (dominant attribute set) pattern vector, or the size of the row set, are less than or equal the specified threshold. In the case the rank-one approximation does not result in a split but the radius constraint is violated, the matrix is split using a random row and the radius constraint.

The debug option can be used to gain some insight into how the algorithm proceeds: a right angle bracket indicates a split and the return to a recursion level is indicated by a left one. Leafs in the recursion tree are indicated by an asterisk and retries by a plus sign. The number of retries is bounded by the size of the current set divided by min.retry. Double angle brackets indicate a random split (see above). The numbers between square brackets indicate the current set size, the size of the presence (sub)set, and its radius. The adjoining numbers indicate the depth of the recursion and the count of retries. Finally, a count of the leaf nodes found so far is shown to the right of an asterisk.

Value

An object of class proximus with the following components:

nr

the number of rows of the data matrix.

nc

the number of columns of the data matrix.

a

a list containing the approximations (patterns).

a$x

a vector of row (presence set) indexes.

a$y

a vector of column (dominant attribute set) indexes.

a$n

the number of ones in the approximated submatrix.

a$c

the absolute error reduction by the approximation.

max.radius

see arguments.

min.size

see arguments.

rownames

rownames of the data matrix.

colnames

colnames of the data matrix.

Warning

Deep recursions may exhaust your computer.

Note

The size of a set need not be equal or greater than the user defined threshold.

Author(s)

Christian Buchta

References

M. Koyut├╝rk, A. Graham, and N. Ramakrishnan. Compression, Clustering, and Pattern Discovery in Very High-Dimensional Discrete-Attribute Data Sets. IEEE Transactions On Knowledge and Data Engineering, Vol. 17, No. 4, (April) 2005.

See Also

summary.proximus for summaries, fitted for obtaining the approximated matrix and the pattern labels of the samples, and lmplot for plotting logical matrices.

Examples

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
x <- matrix(sample(c(FALSE, TRUE), 200, rep=TRUE), ncol=10)
pr <- proximus(x, max.radius=8)
summary(pr)
### example from paper
x <- rlbmat()
pr <- proximus(x, max.radius=8, debug=TRUE)
op <- par(mfrow=c(1,2), pty="s")
lmplot(x, main="Data")
box()
lmplot(fitted(pr)$x, main="Approximation")
box()
par(op)

Example output

Loading required package: grid
Loading required package: proxy

Attaching package: 'proxy'

The following objects are masked from 'package:stats':

    as.dist, dist

The following object is masked from 'package:base':

    as.matrix

approximates 20 x 10 matrix
total Error: 0.17 
total Fnorm: 5.9 
total  Jsim: 0.91 
total Valid: 4 
Pattern Summary:
  Size Length Radius Error Fnorm Jsim Valid
1   12      7      5  0.21   5.0 0.70  TRUE
4    5      5      3  0.14   2.6 0.72  TRUE
2    2      5      2  0.15   1.7 0.70  TRUE
3    1      4      0  0.00   0.0 1.00  TRUE
Non-Zero: 1040
Sparsity: 0.25
  0 [80,20,8] 1 >
  1 [20,20,8] 1 * 1
  1 [60,20,7] 1 >
  2 [20,20,7] 1 * 2
  2 [40,20,6] 1 >
  3 [20,20,6] 1 * 3
  3 [20,20,6] 1 * 4
  2 <
  1 <
  0 <

cba documentation built on May 2, 2019, 1:39 p.m.

Related to proximus in cba...