liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Algorithms in data mining: reduced rank regression and classification by tensor methods
Linköping University, Department of Mathematics, Scientific Computing. Linköping University, The Institute of Technology.ORCID iD: 0000-0002-1542-2690
2005 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

In many fields of science, engineering, and economics large amounts of data are stored and there is a need to analyze these data in order to extract information for various purposes. Data mining is a general concept involving different tools for performing this kind of analysis. The development of mathematical models and efficient algorithms is of key importance. In this thesis, which consists of three appended manuscripts, we discuss algorithms for reduced rank regression and for classification in the context of tensor theory.

The first two manuscripts deal with the reduced rank regression problem, which is encountered in the field of state-space subspace system identification. More specifically the problem is

where A and B are given matrices and we want to find X under a certain rank condition that minimizes the determinant. This problem is not properly stated since it involves implicit assumptions on A and B so that (B - XA)(B - XA)T is never singular. This deficiency of the determinant criterion is fixed by generalizing the minimization criterion to rank reduction and volume minimization of the objective matrix. The volume of a matrix is defined as the product of its nonzero singular values. We give an algorithm that solves the generalized problem and identify properties of the input and output signals causing singularity on the objective matrix.

Classification problems occur in many applications. The task is to determine the label or class of an unknown object. The third appended manuscript concerns with classification of hand written digits in the context of tensors or multidimensional data arrays. Tensor theory is also an area that attracts more and more attention because of the multidimensional structure of the collected data in a various applications. Two classification algorithms are given based on the higher order singular value decomposition (HOSVD). The main algorithm makes a data reduction using HOSVD of 98%- 99% prior the construction of the class models. The models are computed as a set of orthonormal bases spanning the dominant subspaces for the different classes. An unknown digit is expressed as a linear combination of the basis vectors. The amount of computations is fairly low and the performance reasonably good, 5% in error rate.

Place, publisher, year, edition, pages
Linköping: Linköpings universitet , 2005. , 65 p.
Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1214
National Category
Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-30272Local ID: 15789ISBN: 91-85457-81-7 (print)OAI: oai:DiVA.org:liu-30272DiVA: diva2:251094
Available from: 2009-10-09 Created: 2009-10-09 Last updated: 2013-11-06
List of papers
1. Dimensionality reduction and volume minimization - generalization of the determinant minimization criterion for reduced rank regression problems
Open this publication in new window or tab >>Dimensionality reduction and volume minimization - generalization of the determinant minimization criterion for reduced rank regression problems
2006 (English)In: Linear Algebra and its Applications, ISSN 0024-3795, Vol. 418, no 1, 201-214 p.Article in journal (Refereed) Published
Abstract [en]

In this article we propose a generalization of the determinant minimization criterion. The problem of minimizing the determinant of a matrix expression has implicit assumptions that the objective matrix is always nonsingular. In case of singular objective matrix the determinant would be zero and the minimization problem would be meaningless. To be able to handle all possible cases we generalize the determinant criterion to rank reduction and volume minimization of the objective matrix. The generalized minimization criterion is used to solve the following ordinary reduced rank regression problem:

minrank(X)=kdet(B-XA)(B-XA)T,

where A and B are known and X is to be determined. This problem is often encountered in the system identification context.

Keyword
Volume; Minimization criterion; Determinant; Rank deficient matrix
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-13190 (URN)10.1016/j.laa.2006.01.032 (DOI)
Available from: 2008-04-29 Created: 2008-04-29 Last updated: 2013-11-06
2. Rank Reduction and Volume Minimization Approach to State-Space Subspace System Identification
Open this publication in new window or tab >>Rank Reduction and Volume Minimization Approach to State-Space Subspace System Identification
2006 (English)In: Signal Processing, ISSN 0165-1684, E-ISSN 1872-7557, Vol. 86, no 11, 3275-3285 p.Article in journal (Refereed) Published
Abstract [en]

In this paper we consider the reduced rank regression problem

solved by maximum-likelihood-inspired state-space subspace system identification algorithms. We conclude that the determinant criterion is, due to potential rank-deficiencies, not general enough to handle all problem instances. The main part of the paper analyzes the structure of the reduced rank minimization problem and identifies signal properties in terms of geometrical concepts. A more general minimization criterion is considered, rank reduction followed by volume minimization. A numerically sound algorithm for minimizing this criterion is presented and validated on both simulated and experimental data.

Place, publisher, year, edition, pages
Elsevier, 2006
Keyword
Reduced rank regression, System identification, General algorithm, Determinant minimization criterion, Rank reduction, Volume minimization
National Category
Mathematics Control Engineering
Identifiers
urn:nbn:se:liu:diva-13191 (URN)10.1016/j.sigpro.2006.01.008 (DOI)
Available from: 2008-04-29 Created: 2008-04-29 Last updated: 2013-11-06
3. Handwritten digit classification using higher order singular value decomposition
Open this publication in new window or tab >>Handwritten digit classification using higher order singular value decomposition
2007 (English)In: Pattern Recognition, ISSN 0031-3203, Vol. 40, no 3, 993-1003 p.Article in journal (Refereed) Published
Abstract [en]

In this paper we present two algorithms for handwritten digit classification based on the higher order singular value decomposition (HOSVD). The first algorithm uses HOSVD for construction of the class models and achieves classification results with error rate lower than 6%. The second algorithm uses the HOSVD for tensor approximation simultaneously in two modes. Classification results for the second algorithm are almost down at 5% even though the approximation reduces the original training data with more than 98% before the construction of the class models. The actual classification in the test phase for both algorithms is conducted by solving a series least squares problems. Considering computational amount for the test presented the second algorithm is twice as efficient as the first one.

Keyword
Handwritten digit classification, Tensors, Higher order singular value decomposition, Tensor approximation, Least squares
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-13192 (URN)10.1016/j.patcog.2006.08.004 (DOI)
Available from: 2008-04-29 Created: 2008-04-29 Last updated: 2013-11-06

Open Access in DiVA

No full text

Authority records BETA

Savas, Berkant

Search in DiVA

By author/editor
Savas, Berkant
By organisation
Scientific ComputingThe Institute of Technology
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 849 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf