Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0987.62045
Garcke, J.; Griebel, M.; Thess, M.
Data mining with sparse grids. (English)
[J] Computing 67, No.3, 225-253 (2001). ISSN 0010-485X; ISSN 1436-5057/e

Summary: We present a new approach to the classification problem arising in data mining. It is based on the regularization network approach, but in contrast to other methods which employ ansatz functions associated to data points, we use basis functions coming from a grid in the usually high-dimensional feature space for the minimization process. To cope with the curse of dimensionality we employ sparse grids. Thus, only $O( h_n^{-1} n^{d-1})$ instead of $O(h_n^{-d})$ grid points and unknowns are involved. Here $d$ denotes the dimension of the feature space and $h_n=2^{-n}$ gives the mesh size. To be precise, we suggest to use the sparse grid combination technique where the classification problem is discretized and solved on a certain sequence of conventional grids with uniform mesh sizes in each coordinate direction. The sparse grid solution is then obtained from the solutions on these different grids by linear combination.\par In contrast to other sparse grid techniques, the combination method is simpler to use and can be parallelized in a natural and straightforward way. We describe the sparse grid combination technique for the classification problem in terms of the regularization network approach. We then give implementational details and discuss the complexity of the algorithm. It turns out that the method scales only linearly with the number of instances, i.e., the amount of data to be classified. Finally we report on the quality of the classifier built by our new method. Here we consider standard test problems from the UCI repository and problems with huge synthetical data sets in up to 9 dimensions. It turns out that our new method achieves correctness rates which are competitive to that of the best existing methods.

MSC 2000:: *62H30 Statistical classification, etc.
68T10 Pattern recognition
65D10 Smoothing

Keywords: approximation; classification; data mining; sparse grids; combination technique

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]