A multidimensional scaling approach for representing XML documents

ABSTRACT

It has been shown that storing documents having similar structures together can reduce the fragmentation problem and improve query efficiency. Unlike the flat text document, the Web document has no standard vectorial representation, which is required in most existing classification algorithms. In this paper, we propose a vectorization method for XML documents by using multidimensional scaling (MDS) so that Web documents can be fed into an existing classification algorithm. The classical MDS embeds data points into an Euclidean space if the similarity matrix constructed by the data points is semidefinite. The semidefniteness condition, however, may not hold due to the inference technique used in practice. We will find a semi-definite matrix which is the closest to the distance matrix in the Euclidean space. Based on recent developments on strongly semismooth matrix valued functions, we solve the nearest semi-definite matrix problem with a Newton-type method. Experimental studies show that the classification accuracy can be improved.

REFERENCES

• 1: Stephen Boyd , Lin Xiao, Least-Squares Covariance Matrix Adjustment, SIAM Journal on Matrix Analysis and Applications, v.27 n.2, p.532-546, 2005 [doi>10.1137/040609902]
• 2: Christopher J. C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, v.2 n.2, p.121-167, June 1998 [doi>10.1023/A:1009715923555]
• 3: C. Burges, Geometric methods for feature extraction and dimensional reduction. In L. Rokach and O. Maimon (Eds.), Data mining and knowledge discovery handbook: A complete guide for practition- ers and researchers. Kluwer Academic Publishers, 2005
• 4: Cox, T., and Cox, M. Multidimensional scaling. London: Chapman & Hall, 1994
• 5: E. Rodney Canfield , Guangming Xing, Approximate XML document matching, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico [doi>10.1145/1066677.1066857]
• 6: Weimin Chen, New algorithm for ordered tree-to-tree correction problem, Journal of Algorithms, v.40 n.2, p.135-158, August 2001 [doi>10.1006/jagm.2001.1170]
• 7: Chih-Chung Chang and Chih-Jen Lin, LIBSVM: a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/cjlin/libsvm.
• 8: F. H. Clarke, Optimization and Nonsmooth Analysis, John Wiley & Sons, New York, 1983.
• 9: Minos Garofalakis , Aristides Gionis , Rajeev Rastogi , S. Seshadri , Kyuseok Shim, XTRACT: a system for extracting document type descriptors from XML documents, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.165-176, May 15-18, 2000, Dallas, Texas, United States
• 10: N. J. Higham, Computing the nearest correlation matrix - a problem from finance, IMA J. Numer. Analysis 22 (2002), pp. 329--343.
• 11: Thorsten Joachims, Text Categorization with Suport Vector Machines: Learning with Many Relevant Features, Proceedings of the 10th European Conference on Machine Learning, p.137-142, April 21-23, 1998
• 12: Jérôme Malick, A Dual Approach to Semidefinite Least-Squares Problems, SIAM Journal on Matrix Analysis and Applications, v.26 n.1, p.272-284, 2005 [doi>10.1137/S0895479802413856]
• 13: M. Murata Hedge Automata: A Formal Model for XML Schemata, http://www.xml.gr.jp/relax/hedge_nice.html
• 14: Gene Myers, Approximately matching context-free languages, Information Processing Letters, v.54 n.2, p.85-92, April 28, 1995 [doi>10.1016/0020-0190(95)00007-Y]
• 15: A. Nierman and H. V. Jagadish, Evaluating structural similarity in XML documents, WebDB 2002, Madison, Wisconsin, June 2002.
• 16: Houduo Qi , Defeng Sun, A Quadratically Convergent Newton Method for Computing the Nearest Correlation Matrix, SIAM Journal on Matrix Analysis and Applications, v.28 n.2, p.360-385, 2006 [doi>10.1137/050624509]
• 17: R. T. Rockafellar, Conjugate Duality and Optimization, SIAM, Philadelphia, 1974.
• 18: Fabrizio Sebastiani, Machine learning in automated text categorization, ACM Computing Surveys (CSUR), v.34 n.1, p.1-47, March 2002 [doi>10.1145/505282.505283]
• 19: Schölkopf, B., K. Tsuda and J. P. Vert, Kernel Methods in Computational Biology, MIT Press, Cambridge, MA, USA (2004).
• 20: D. Shasha and K. Zhang, Approximate Tree Pattern Matching, Chapter 14 Pattern Matching Algorithms (eds. Apostolico, A. and Galil, Z.), Oxford University Press, June 1997.
• 21: J. F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optimization Methos and Software, vol. 11--12, 625--653.
• 22: Jian-Tao Sun , Ben-Yu Zhang , Zheng Chen , Yu-Chang Lu , Chun-Yi Shi , Wei-Ying Ma, GE-CKO: A Method to Optimize Composite Kernels for Web Page Classification, Proceedings of the 2004 IEEE/WIC/ACM International Conference on Web Intelligence, p.299-305, September 20-24, 2004 [doi>10.1109/WI.2004.74]
• 23: V. de Silva and J. B. Tenenbaum, Global versus local methods in nonlinear dimensionality reduction, in Advances in Neural Information Processing Systems 15, S. T. S. Becker and K. Obermayer, Eds. Cambridge, MA: MIT Press, 2003, pp. 705--712.
• 24: John Shawe-Taylor , Nello Cristianini, Kernel Methods for Pattern Analysis, Cambridge University Press, New York, NY, 2004
• 25: Wang Lian , David Wai-lok Cheung , Nikos Mamoulis , Siu-Ming Yiu, An Efficient and Scalable Algorithm for Clustering XML Documents by Structure, IEEE Transactions on Knowledge and Data Engineering, v.16 n.1, p.82-96, January 2004 [doi>10.1109/TKDE.2004.1264824]
• 26: XML Document Mining Challenge, http://xmlmining.lip6.fr/.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms

Keywords:
classification, matrices, multidimensional scaling, semidefinite programming