High complexity of lattice construction algorithms and uneasy way of visualising lattices are two important problems connected with the formal concept analysis. Algorithm complexity plays significant role when computing all concepts from a huge incidence matrix. In this paper we try to modify an incidence matrix using matrix decomposition, creating a new matrix with fewer dimensions as an input for some known algorithms for lattice construction. Results are presented by visualising neural network. Neural network is responsive for reducing result dimension to two dimensional space and we are able to present result as a picture that we are able to analyse.
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) [
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 [
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 2 G is related to I with the attribute m 2 M , we record it as gIm or (g; m) 2 I and read it as the object g has the attribute m. I is also defined as the context incidence relation.
For a set A G of object we define
A0 = fm 2 M j gIm f or all g 2 Ag (the set of attributes common to the objects in A). Correspondingly, for a set B of attributes we define
B0 = fg 2 G j gIm f or all m 2 Bg (the set of objects which have all attributes in B).
A formal concept of the context (G; M; I) is a pair (A; B) with A G, B M , A0 = B and B0 = A. We call A the extent and B the intent of the concept (A; B). B(G; M; I) denotes the set of all concepts of context (G; M; I).
The concept lattice B(G; M; I) is a complete lattice in which infimum and supremum are given by: ^ (At; Bt) = t2T t2T _ (At; Bt) = \ At; t2T [ At t2T
00
[ Bt
t2T
t2T
We refer to [
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 [
Vma=l, a(nvd1;a: :d:i;avgro)n,awlmhoastreixcolu=mndivaegc(to r01s; :a:re:;0 orrth).o nT.k ohre.- . 2y . 4Tk d decomposition A = U V T is called singular value decomposition of matrix A and numbers 1; : : : ; r are singular values of the matrix A. Columns of U (or V ) are called left (or right) singular vectors of matrix A.
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 A
A = U V T = (UkU0) k 0 0 0
VkT V0T We call Ak = Uk kVkT a k-reduced singular value decomposition (rank-k SVD).
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 Ak is the one, that minimises
Cw;j )2. jjAk Ajj2F = P(Ai;j
i;j
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 Ak.
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.
The unified distance matrix (U-matrix) makes the 2D
visualization of multi-variate data possible using SOM’s
codevectors as data source [
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. 3.2
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. 3.3
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 incidence matrix and was used in SVD, NMF and FCA computations. 3.4
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). 3.5
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.