We are dealing with uses of matrix decompositions for reduction of concept lattice. These methods are well known in the area of information retrieval under the name Latent Semantic Indexing (LSI) or Latent Semantic Analysis (LSA). LSI and LSA have been used for discovery of latent dependencies between terms (or documents) [1], [6]. We would like to apply this approach in the area of formal concept analysis (FCA). In this paper, we want to present decomposition's results with neural network [5]. First, we will introduce basic terms of Formal Concept Analysis (FCA) [3] and then we will describe the rank-k singe value decomposition (SVD) [8]. Singular Value Decomposition is one of the various matrix decomposition techniques arising from numerical linear algebra. SVD reduces both the column space and the row space of the term-document matrix to lower dimensional spaces [4]. After using SVD on input matrix we can build lattices and visualise them using neural networks [5] and u-matrix [9]. Numerous studies suggest that graphical representation and display of results can improve information retrieval performance [10]. Once having visualisation we can analyze result of matrix reduction.
In the following paragraphs we would like to introduce important basic terms of formal concept analysis, singu-Proceedings of the Spring Young Researcher's Colloquium on Database and Information Systems, Moscow, Russia, 2007 lar value decomposition, self organized maps and unified distrance matrix.
Formal Concept Analysis was first introduced by Rudolf Wille in 1980. FCA is based on the philosophical understanding of the world in terms of objects and attributes. It is assumed that a relation exists to connect objects to the attributes they possess. Formal context and formal concept are the fundamental notions of Formal Concept Analysis [3].
A formal context C = (G, M, I) consists of two sets; G and M , with I in relation to G and M . The elements of G are defined as objects and the elements of M are defined as attributes of the context. In order to express that an object g ∈ G is related to I with the attribute m ∈ M , we record it as gIm or (g, m) ∈ I and read it as the object g has the attribute m. I is also defined as the context incidence relation. The concept lattice B(G, M, I) is a complete lattice in which infimum and supremum are given by:
We refer to [3].
Singular value decomposition (SVD) is well known because of its application in information retrieval as LSI. SVD is especially suitable in its variant for sparse matrices [7]. Now we have a decomposition of the original matrix A. It is not needed to say, that the left and right singular vectors are not sparse. We have at most r nonzero singular numbers, where rank r is the smaller of the two matrix dimensions. However, we would not conserve much memory by storing the term-by-document matrix this way. Luckily, because the singular values usually fall quickly, we can take only k greatest singular values and corresponding singular vector co-ordinates and create a k-reduced singular decomposition of A.
Let us have k, 0 < k < r and singular value decomposition of
In information retrieval, if every document is relevant to only one topic, we obtain a latent semantics -semantically related words and documents will have similar vectors in the reduced space. For an illustration of rank-k SVD see figure 1, the grey areas determine first k coordinates from singular vectors, which are being used.
Theorem 2: (Eckart-Young) Among all m × n matrices C of rank at most k A k is the one, that minimises
Because rank-k SVD is the best rank-k approximation of original matrix A, any other decomposition will increase the sum of squares of matrix A − A k .
The SVD is hard to compute and once computed, it reflects only the decomposition of the original matrix. The recalculation of SVD is expensive, so it is impossible to recalculate SVD every time new rows or columns are inserted. The SVD-Updating is a partial solution, but since the error increases slightly with inserted rows and columns when updates occur frequently, the recalculation of SVD may be needed.
Note: From now on, we will assume rank-k singular value decomposition when speaking about SVD.
Kohonen Self-Organizing Map (SOM) [5] is a competitive artificial neural network. They are used to clasify and cluster data set according to similarity [2]. SOM artifical network is structured in two layers. The first one represents the input data, the second one is a neuron's grid, usually bidimensional, full connected. Each input is connected to all output neurons. Output neurons are arranged in low dimensional (usually 2D or 3D) grid. Attached to every neuron there is a weight vector with the same dimensionality as the input vectors. The number of input dimensions is usually a lot higher than the output grid dimension. SOMs are mainly used for dimensionality reduction rather than expansion.
The unified distance matrix (U-matrix) makes the 2D visualization of multi-variate data possible using SOM's codevectors as data source [9]. This is achieved by using topological relations property among neurons after the learning process. U-matrix contains the distances from each unit center to all of its neighbours. By U-matrix we can detect topological relations among neurons and infer about the input data structure. High values in the Umatrix represent a frontier region between clusters, and low values represent a high degree of similarities among neurons on that region, clusters. This can be a visual task when we use some color schema.
Data from the Ostrava Mass Transit Authority was used in this experiment. We can describe data in a graph. Rows represent tram stops, columns represent tram lines. Let 1 represent a tram stopping at a tram stop in the appropriate row and column crossing, otherwise zero. This data was chosen because we can easily see if the SVD is working. Many tram lines share the same tram stops. These parts of tram lines should be minimized with SVD and it should also be visible after using SVD.
Our experiment included several steps. The first step was to read and transform data into adjacency matrix. After transforming and computing (using SVD) three new matrixes were obtained as results from SVD A = U ΣV T . After choosing rank-k, a new matrix was computed. Lattices were build from both original matrix and matrix computed by SVD. Concepts of lattices acted as the source for SOMs learning phase. Having learned SOMs, visualisation as done using U-matrix technique.
Data was obtained from tram timetables. The first ten tram lines and their tram stops were chosen. The transformed matrix had 92 rows and 10 columns. Transformation was simple. If a tram stops at a particular tram stop, the number 1 appeared in the appropriate row and column crossing, otherwise zero. The matrix is also an
SVD computations were made by SVDLIBC-fix software. This software is free and is written in C language. An incidence matrix acts as the input. Software can compute all three matrixes -U and Σ and V T . k-rank was chosen k = 4. Matrixes were U (92x10), Σ(10x10) and V T (10x10).
Data from the Ostrava Mass Transit Authority was used in this experiment. We can describe data in a graph. Rows represent tram stops, columns represent tram lines. Let ones represent a tram stopping at the tram stop in the appropriate row and column crossing, otherwise zero.
First SOM was learned by giving these initial data. Second SOM was learned by giving data after applying SVD on initial data. There were two SOM networks according to type of input data.
Next part of research was about visualising SOM network via unified distance matrix (U-matrix) algorithm. Euclidean metric was used for computing distances between nodes. We got two greyscale pictures (figure 2, figure 3) that we are able to analyze, especialy number and form of visible clusters.
There are two u-matrix visualisations. Figure 2 matches concepts of lattice built from the original matrix, figure 3 matches concepts of lattice built from the original matrix changed with SVD. The number of differencies between rows in tables was decreased by SVD computation. Thus you can see smaller number of clusters. There is no doubt method was successful in reducing number of concepts.