Latent semantic indexing (LSI) is an application of numerical method called singular value decomposition (SVD), which discovers latent semantic in documents by creating concepts from existing terms. The application area is not limited to text retrieval, many applications such as image compression are known. We propose usage of SVD as a possible data mining method and lattice size reduction tool. We offer in this paper preliminary experiments to support usability of proposed method.
We are studying the possible usage of k-reduced singular value decomposition (rank-k SVD ) for reduction of concept lattice size. This method is well known in the area of Information Retrieval under the name latent semantic indexing (LSI ), where it has been used for discovery of latent dependencies between terms (or documents). We would like to apply this approach in the area of formal concept analysis (FCA). The main goal of this paper is to provide primary results obtained with this method.
We will first mention FCA and describe the rank- k SVD decomposition and LSI method. In second chapter we will mention our proposed approach and two parameters which help us to tune it together with an example. In third chapter we will show preliminary experiment on small set of objects and attributes from real-life data. In conclusion, we will mention the expected outcome of our research. 1.1
Definition 1. A formal context C := (G, M, I) consists of two sets G and M and relation I between G and M . The elements of G are called the objects and the elements of M are called the attributes of the context. In order to express that an object g is in a relation I with an attribute m, we write gIm or (g, m) ∈ I and read it as “the object g has the attribute m”. The relation I is also called the incidence relation of the context.
Definition 2. for a set A ⊂
G of object we define
A0 = {m ∈ M | gIm f or all g ∈ A} (the set of attributes common to the objects in A). Correspondingly, for a set B of attributes we define
B0 = {g ∈ G | gIm f or all m ∈ B} (the set of objects which have all attributes in B).
Definition 3. 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) Definition 4. The concept lattice B(G, M, I) is a complete lattice in which infimum and supremum are given by: ^ (At, Bt) = t∈T t∈T _ (At, Bt) = \ At, t∈T [ At t∈T
00
[ Bt
t∈T
00
, \ Bt .
t∈T
We refer to [
Singular value decomposition (SVD ) is well known because of its application in
information retrieval – Latent semantic indexing (LSI ) [
Theorem 1 (Singular value decomposition). Let A is an n × m rank-r matrix. Be σ 1 ≥ . . . ≥ σ r eigenvalues of a matrix √AAT . Then there exist orthogonal matrices U = (u1, . . . , ur) and V = (v1, . . . , vr), whose column vectors are orthonormal, and a diagonal matrix Σ = diag(σ 1, . . . , σ r). The 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 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 coordinates 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 rfist k coordinates from singular vectors, which are being used.
The SVD is hard to compute and once computed, it reeflcts only the
decomposition of 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 [
Note: From now on, we will assume rank-k singular value decomposition when speaking about SVD.
As we already mentioned, our goals are the ability to build concept lattice on binary data which may contain noise and the reduction of node count in concept lattice.
The singular value decomposition may be applied on incidence matrix of objects and attributes (features) A. Since rank-k SVD is known to remove noise by ignoring small differences between row and column vectors of A – they will correspond to small singular values, which we drop by the choice of k – it can be used for data mining.
Because the SVD is mainly used on real numbers, we must solve a problem that the resulting decomposition will also provide real numbers, regardless to the fact that the input matrix is binary. The matrices Uk and Vk don’t allow us to create the reduced concept lattice directly, but we can build the reconstructed matrix Ak. It will not contain binary values, so we will have to choose a threshold t discriminating between ones and zeros.
This done, we have two parameters of our method – the reduced dimension k and the threshold t, where generally lower k will result in more uniefid values and less noise (but if used incorrectly it could ignore important attributes to some extent, too) and higher t in less attributes of objects and thus in less nodes in concept lattice.
a1 a2 a3 a4 o1 1 0 1 0 o2 1 1 0 1 o3 0 1 1 0 o4 0 1 0 1 o5 1 1 1 1 o6 0 0 1 1 a) b)
Moreover, we can say that SVD creates equivalence classes of nodes in original lattice, merging them into one node in the modified lattice.
The value of k in information retrieval was experimentally determined as several tens or hundreds (e.g. 50–250), exact value of k for our method is currently not known and has yet to be determined, for example by observing the singular numbers, as their value should drop quickly from some point.
On the other hand we will not encounter the problem with updating the SVD, since the incidence matrix is usually small enough for fast calculation and the lattice has to be reconstructed every time the incidence matrix changes. Example 1. To exemplify the method, suppose there are six objects with four attributes, as shown in figure 2. We calculated SVD with k 3 and 2 and chosen thresholds t1 = 0.1, t2 = 0.6. The results are shown in figures 3 and 4.
As one can see, lower k led to a higher reduction as well as higher threshold values, which was expected. In case of k = 2 the reduction seem to be to high, leading to a concept lattice where only two groups of object and attributes exist. The question, whether this method creates a viable reduction of concept lattice has to yet to be evaluated in the future.
You can also see, that i.e. nodes in example 1 labeled o3 and o6 correspond to one node in reduced lattice in gfiure 3 a).
There are other methods of lattice size reduction like constraining the
concept lattice by attribute dependencies [
We used a data set of Bacterial Taxonomy often used for clustering tests, which was given by Rataj & Schindler. Data are presented for six bacteria species, most having data for more than one strain and 16 phenotypic characters1 (0 – absent, 1 – present). The incidence matrix is shown in table 1. ecoli1 0 ecoli2 0 ecoli3 1 styphi1 0 styphi2 0 styphi3 1 kpneu1 0 kpneu2 0 kpneu3 0 kpneu4 0 kpneu5 0 pvul1 1 pvul2 1 pvul3 1 pmor1 0 pmor2 0 smar 0 1 For full specie names see e.g. http://149.170.199.144/multivar/ca eg.htm#Example2
The original concept lattice is shown in figure 5, whilst reduced ones in gfiures 7 and 6. Some modified lattices, i.e. one with k = 9 and t = 0.5 correspond to original concept lattice.
One can see, that the modiefid lattices are quite smaller than original one, the question whether this reduction is a good one is still open. 4
In our work we have shown new approach to lattice size reduction and creation from data which may contain some noise through the usage of k-reduced singular decomposition. Our method brings some promising results and should be tested on larger data.
We have yet to determine, if the resulting lattice is a suitable one and what are the main properties of this reduction technique. The other problem is a good choice of k and t and decision, if they are fixed values or functions of the highest and lowest values produced by SVD.
The proposed method could lead to the construction of a new technique of lattice traversal, but it has yet to be determined, whether the complexity would not be too high for its usage.
We would like to compare our method with results of Palacky´ University
team, led by Doc. Belohlavek, in the area of attribute dependencies [