Clustering in Concept Etraction在概念提取的聚类.pptVIP

Technical Report of Web Mining Group Presented by: Mohsen Kamyar Ferdowsi University of Mashhad, WTLab Main Approach in Concept Extraction Problems Clustering Methods and LSI Ideas and Our Works Experimental Results Main approach in Concept Extraction (we will say it CE) is using LSI. LSI is a collection of one Matrix Algorithm and some Probabilistic Analyses on it for using on Term-Document Matrix. At first we should create Term-Document matrix (using measures like TFiDF for indicating the importance of a term in a particular document), then give it to SVD (Singular Value Decomposition) algorithm and finally choose the first K columns as concepts. Singular Value Decomposition is an algorithm for Matrix (we assume that matrix M is m×n) Decomposition to 3 matrices like U, S and V, such that S is an orthogonal matrix of singular values, U is eigenvectors of the Matrix MMT (Term correlation matrix) and V is eigenvectors of the Matrix MTM (Document Correlation Matrix). S is sorted descending. Therefore the first k elements of it or the first k columns of U or the first k rows of V are the most important values. Steps of SVD can be explained as below: 1- Select first column of matrix M1, we name it u1 2- Calculate the length of u1 and add it to first element. 3- Then set B1=|u1|2/2 4- Then set U1=I-B1-1 u1u1T 5- Then set M2=U1M1 6- Do it for first row and then repeat for other rows and columns In general for ith column or row, in step 2 we should first set all elements before ith element equal to zero, then calculate the length and add the result to ith element. Main Approach in Concept Extraction Problems Clustering Methods and LSI Ideas and Our Works Experimental Results We can list the main problems of LSI as below This method is based on the sum of square of distances (Σ(si-ti)2), so it is useful for data that has Gaussian (Normal) Distribution. But Term-Document Matrix has Poisson Distribution. This method is very slow (its computation complexity is n3m and nm) Pois