Các Hạt Graph từ Độ Phân Tán Jensen-Shannon

Journal of Mathematical Imaging and Vision - Tập 47 - Trang 60-69 - 2012
Lu Bai1, Edwin R. Hancock1
1Department of Computer Science, Deramore Lane, University of York, Heslington, UK

Tóm tắt

Các đại diện dựa trên đồ thị đã được chứng minh là mạnh mẽ trong thị giác máy tính. Thách thức phát sinh với khối lượng lớn dữ liệu đồ thị là tính toán khoảng cách chỉnh sửa tốn kém về mặt tính toán. Các hạt đồ thị có thể được sử dụng để xây dựng các thuật toán hiệu quả nhằm xử lý dữ liệu có độ chiều cao, và đã được chứng minh là một cách tinh tế để vượt qua nút cổ chai tính toán này. Trong bài báo này, chúng tôi điều tra xem độ phân tán Jensen-Shannon có thể được sử dụng như một phương tiện để thiết lập một hạt đồ thị hay không. Hạt Jensen-Shannon là một hạt lý thuyết thông tin không mở rộng, và được định nghĩa bằng cách sử dụng độ entropy và thông tin tương hỗ được tính toán từ các phân phối xác suất dựa trên các cấu trúc đang được so sánh. Để thiết lập một hạt đồ thị Jensen-Shannon, chúng tôi khám phá hai phương pháp khác nhau. Phương pháp đầu tiên dựa trên độ entropy von Neumann liên quan đến một đồ thị. Phương pháp thứ hai sử dụng độ entropy Shannon liên quan đến vector trạng thái xác suất cho một chuyển động ngẫu nhiên ở trạng thái ổn định trên một đồ thị. Chúng tôi so sánh hai hạt đồ thị thu được cho vấn đề phân cụm đồ thị. Chúng tôi sử dụng phân tích thành phần chính theo hạt (kPCA) để nhúng đồ thị vào một không gian đặc trưng. Các kết quả thực nghiệm cho thấy phương pháp này mang lại kết quả phân loại tốt trên các đồ thị được trích xuất từ cả cơ sở dữ liệu nhận dạng đối tượng và từ một ứng dụng trong sinh thông tin.

Từ khóa

#đồ thị #hạt đồ thị #độ phân tán Jensen-Shannon #phân cụm đồ thị #phân tích thành phần chính theo hạt

Tài liệu tham khảo

Anand, K., Bianconi, G., Severini, S.: Shannon and von Neumann entropy of random networks with heterogeneous expected degree. Phys. Rev. E 83, 036109 (2011)

Borgwardt, K.M., Kriegel, H.P.: Shortest-path kernels on graphs. In: Proceedings of IEEE International Conference on Data Mining, pp. 74–81 (2005)

Braunstein, S., Ghosh, S., Severini, S.: The Laplacian of a graph as a density matrix: a basic combinatorial approach to separability of mixed states. Ann. Comb. 10, 291–317 (2006)

Chung, F.R.K.: Spectral Graph Theory. American Mathematical Society, Providence (1997)

Desobry, F., Davy, M., Fitzgerald, W.: Density kernels on unordered sets for kernel-based signal processing. In: Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 417–420 (2003)

Emms, D., Wilson, R.C., Hancock, E.R.: Graph matching using the interference of continuous-time quantum walks. Pattern Recognit. 42, 985–1002 (2009)

Emms, D., Wilson, R.C., Hancock, E.R.: Graph matching using the interference of discrete-time quantum walks. Image Vis. Comput. 27, 934–949 (2009)

Feldman, D., Crutchfield, J.: Measures of statistical complexity: why? Phys. Lett. A 238, 244,252 (1998)

Ferrer, M., Valveny, E., Serratosa, F., Riesen, K., Bunke, H.: Generalized median graph computation by means of graph embedding in vector spaces. Pattern Recognit. 43, 1642–1655 (2010)

Gärtner, T.: A survey of kernels for structured data. ACM Special Interest Group on Knowledge Discovery and Data Mining 5(1), 49–58 (2003)

Gell–Mann, M., Tsallis, C.: Nonextensive Entropy: Interdisciplinary Application. Oxford University Press, London (2004)

Godsil, C., Royle, G.: Algebraic Graph Theory. Springer, New York (2001)

Han, L., Hancock, E.R., Wilson, R.C.: Characterizing graphs using approximate von Neumann entropy. In: Proceedings of the Iberian Conference on Pattern Recognition and Image Analysis, pp. 484–491 (2011)

Havrda, M., Charát, F.: Quantification method of classification processes: concept of structural α-entropy. Kybernetika 3, 30–35 (1967)

Jebara, T., Kondor, R.I., Howard, A.: Probability product kernels. J. Mach. Learn. Res. 5, 819–844 (2004)

Kashima, H., Tsuda, K., Inokuchi, A.: Marginalized kernels between labeled graphs. In: Proceedings of International Conference on Machine Learning, pp. 321–328 (2003)

Ketkar, N.S., Holder, L.B., Cook, D.J.: Faster computation of the direct product kernel for graph classification. In: Proceedings of the IEEE Symposium on Computational Intelligence and Data Mining, pp. 267–274 (2009)

Kondor, R.I., Lafferty, J.D.: Diffusion kernels on graphs and other discrete input spaces. In: Proceedings of International Conference on Machine Learning, pp. 315–322 (2002)

Lafferty, J.D., Lebanon, G.: Diffusion kernels on statistical manifolds. J. Mach. Learn. Res. 6, 129–163 (2005)

Lamberti, P., Majtey, A., Borras, A., Casas, M., Plastino, A.: Metric character of the quantum Jensen-Shannon divergence. Phys. Rev. A 77, 052311 (2008)

Majtey, A., Borrás, A., Casas, M., Lamberti, P., Plastino, A.: Jensen-Shannon divergence as a measure of the degree of entanglement. Int. J. Quantum Inf. 6, 715–720 (2008)

Majtey, A., Lamberti, P., Prato, D.: Jensen-Shannon divergence as a measure of distinguishability between mixed quantum states. Phys. Rev. A 72, 052310 (2005)

Martins, A.F.T., Smith, N.A., Xing, E.P., Aguiar, P.M.Q., Figueiredo, M.A.T.: Nonextensive information theoretic kernels on measures. J. Mach. Learn. Res., 935–975 (2009)

Passerini, F., Severini, S.: Quantifying complexity in networks: the von Neumann entropy. Int. J. Agent Technol. Syst. 1, 58–67 (2009)

Qiu, H., Hancock, E.R.: Clustering and embedding using commute times. IEEE Trans. Pattern Anal. Mach. Intell. 29, 1873–1890 (2007)

Ren, P., Aleksić, T., Emms, D., Wilson, R.C., Hancock, E.R.: Quantum walks, Ihara zeta functions and cospectrality in regular graphs. Quantum Inf. Process. 10, 405–417 (2011)

Ren, P., Wilson, R.C., Hancock, E.R.: Graph characteristics from the Ihara zeta function. In: Proceedings of Joint IAPR International Workshops on Structural and Syntactic Pattern Recognition (SSPR) and Statistical Techniques in Pattern Recognition (SPR), pp. 257–266 (2008)

Robles-Kelly, A., Hancock, E.R.: A Riemannian approach to graph embedding. Pattern Recognit. 40, 1042–1056 (2007)

Schölkopf, B., Smola, A.: Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, Cambridge (2002)

Schölkopf, B., Smola, A., Müller, K.: Kernel principal component analysis. Artif. Neural Netw., 583–588 (1997)

Suau, P., Escolano, F.: Bayesian optimization of the scale saliency filter. Image Vis. Comput. 26, 1207–1218 (2008)

Taylor, J.S., Cristianini, N.: Kernel Methods for Pattern Analysis. Cambridge University Press, Cambridge (2004)

Torsello, A., Hancock, E.R.: Graph embedding using tree edit-union. Pattern Recognit. 40, 1393–1405 (2007)

Torsello, A., Robles-Kelly, A., Hancock, E.R.: Discovering shape classes using tree edit-distance and pairwise clustering. Int. J. Comput. Vis. 72, 259–285 (2007)

Wilson, R.C., Hancock, E.R., Luo, B.: Pattern vectors from algebraic graph theory. IEEE Trans. Pattern Anal. Mach. Intell. 27, 1112–1124 (2005)

Xiao, B., Hancock, E.R., Wilson, R.C.: Graph characteristics from the heat kernel trace. Pattern Recognit. 42, 2589–2606 (2009)

Thông tin
Thông tin xuất bản

Journal of Mathematical Imaging and Vision

Tập 47

60-69

Thông tin tác giả