Kernel Pohon: Mengukur Kesamaan Di Antara Data Terstruktur Pohon

Jaringan atau grafik adalah jenis data terstruktur dalam bentuk simpul , dengan hubungan di antara mereka dijelaskan oleh tautan, atau tepi . Node dan edge dalam graf mungkin memiliki beberapa atribut yang mungkin numerik atau kategorikal, atau bahkan lebih kompleks.

Saat ini, sejumlah besar data tersedia dalam bentuk jaringan atau grafik. Misalnya, World Wide Web, dengan halaman web dan hyperlinknya, jaringan sosial, jaringan semantik, jaringan biologis, jaringan kutipan untuk literatur ilmiah, dan sebagainya.

Pohon adalah jenis grafik khusus, dan secara alami cocok untuk mewakili banyak jenis data. Analisis pohon merupakan bidang penting dalam ilmu komputer dan data. Pada artikel ini, kita akan melihat analisis struktur tautan di pohon. Secara khusus, kami akan fokus pada kernel pohon, sebuah metode untuk membandingkan grafik pohon satu sama lain, memungkinkan kami untuk mendapatkan pengukuran kuantitatif persamaan atau perbedaan mereka. Ini merupakan proses penting untuk banyak aplikasi modern seperti klasifikasi dan analisis data.

Klasifikasi Data Terstruktur Tanpa Pengawasan

Klasifikasi merupakan komponen penting machine learning dan analisis data. Secara umum, klasifikasi dapat diawasi atau tidak diawasi . Dalam klasifikasi terbimbing, kelas sudah diketahui, dan model klasifikasi dibangun dari data pelatihan di mana kelas yang benar sudah diberikan. Klasifikasi yang tidak diawasi, sebaliknya, mencoba mengidentifikasi kelas yang tidak ada yang diketahui, mengelompokkan data ke dalam kategori berdasarkan beberapa ukuran kesamaannya.

Klasifikasi tak terawasi dapat dikombinasikan dengan teori graf untuk mengidentifikasi kelompok jaringan pohon yang serupa. Struktur data pohon digunakan untuk memodelkan objek dari beberapa domain. Dalam pemrosesan bahasa alami (NLP), misalnya, pohon parse dimodelkan sebagai pohon berlabel yang dipesan. Dalam penalaran otomatis, banyak masalah diselesaikan dengan pencarian, di mana ruang pencarian direpresentasikan sebagai pohon yang simpulnya terkait dengan status pencarian, dan tepi mewakili langkah-langkah inferensi. Juga, data semi terstruktur, seperti dokumen HTML dan XML, dapat dimodelkan sebagai pohon berlabel yang dipesan.

Domain-domain ini dapat dianalisis dengan berguna melalui teknik klasifikasi tanpa pengawasan. Dalam NLP, klasifikasi dapat digunakan untuk secara otomatis mengelompokkan serangkaian kalimat menjadi pertanyaan, perintah, dan pernyataan. Demikian juga, kelompok situs web serupa dapat diidentifikasi dengan menerapkan metode klasifikasi ke sumber HTML mereka. Dalam setiap kasus ini, yang kita butuhkan hanyalah cara untuk mengukur seberapa "mirip" dua pohon satu sama lain.

Kutukan Dimensi

Sebagian besar algoritma klasifikasi mengharuskan data ditransformasikan ke dalam bentuk vektor, yang mewakili nilai-nilai fitur data dalam ruang fitur , sehingga data dapat dianalisis dalam ruang fitur menggunakan aljabar linier. Dalam data terstruktur atau semi terstruktur, seperti pohon, dimensi vektor yang dihasilkan (yaitu, jumlah fitur dalam ruang fitur) mungkin cukup tinggi, karena ruang fitur harus menyimpan informasi tentang struktur.

Ini mungkin merupakan kelemahan yang signifikan, mengingat banyak teknik klasifikasi tidak dapat menskalakan secara efektif dengan dimensi input. Dengan kata lain, kekuatan klasifikasi mereka berkurang dengan peningkatan dimensi input. Masalah ini dikenal sebagai kutukan dimensi.

Untuk mendapatkan gambaran tentang alasan penurunan kinerja ini, pertimbangkan ruang X berdimensi d . Misalkan X berisi sekumpulan titik yang berdistribusi seragam. Jika jumlah dimensi X bertambah, jumlah titik yang diperlukan untuk menjaga kerapatan yang sama harus meningkat secara eksponensial. Dengan kata lain, semakin banyak dimensi input, semakin besar kemungkinan data tersebut jarang. Secara umum, kumpulan data yang jarang tidak memberikan informasi yang cukup untuk membangun pengklasifikasi yang baik karena korelasi antara elemen data terlalu lemah untuk dideteksi oleh algoritma.

Setiap ruang fitur di atas berisi delapan titik data. Pada ruang satu dimensi, mudah untuk mengidentifikasi sekelompok lima titik di sebelah kiri, dan tiga di sebelah kanan. Membentangkan titik-titik ini pada jumlah fitur yang lebih tinggi (yaitu dimensi) membuatnya lebih sulit untuk menemukan grup-grup ini. Dalam aplikasi nyata, ruang fitur dapat dengan mudah memiliki ratusan dimensi.

Representasi vektor untuk data terstruktur sesuai ketika informasi tentang domain dapat digunakan secara efektif untuk memilih serangkaian fitur yang dapat dikelola. Ketika informasi tersebut tidak tersedia, sebaiknya menggunakan teknik yang dapat menangani data terstruktur secara langsung, tanpa melakukan operasi di ruang vektor.

Metode Kernel

Metode kernel menghindari kebutuhan untuk mengubah data ke dalam bentuk vektor. Satu-satunya informasi yang mereka butuhkan adalah pengukuran kesamaan setiap pasangan item dalam kumpulan data. Pengukuran ini disebut kernel , dan fungsi untuk menentukannya disebut fungsi kernel . Metode kernel mencari hubungan linier dalam ruang fitur. Secara fungsional, mereka setara dengan mengambil produk titik dari dua titik data di ruang fitur, dan memang desain fitur mungkin masih merupakan langkah yang berguna dalam desain fungsi kernel. Namun, metode metode kernel menghindari operasi langsung pada ruang fitur karena dapat ditunjukkan bahwa produk titik dapat diganti dengan fungsi kernel, selama fungsi kernel adalah simetris, fungsi semidefinite positif yang dapat mengambil data sebagai input. di ruang aslinya.

Keuntungan menggunakan fungsi kernel adalah bahwa ruang fitur yang besar dapat dianalisis dengan kompleksitas komputasi tidak tergantung pada ukuran ruang fitur, tetapi pada kompleksitas fungsi kernel, yang berarti bahwa metode kernel tidak mengalami kutukan. dari dimensi.

Jika kita menganggap dataset terbatas yang terdiri dari n contoh, kita bisa mendapatkan representasi lengkap kesamaan dalam data dengan menghasilkan matriks kernel yang ukurannya selalu n × n . Matriks ini tidak tergantung pada ukuran setiap contoh individu. Properti ini berguna ketika kumpulan data kecil dari contoh dengan ruang fitur yang besar akan dianalisis.

Secara umum, metode kernel didasarkan pada jawaban yang berbeda untuk pertanyaan tentang representasi data. Alih-alih memetakan titik input ke dalam ruang fitur, data direpresentasikan melalui perbandingan berpasangan dalam matriks kernel K , dan semua analisis yang relevan dapat dilakukan pada matriks kernel.

Banyak metode penambangan data dapat dikernelisasi. Untuk mengklasifikasikan contoh data terstruktur pohon dengan metode kernel, seperti dengan mesin vektor pendukung, cukup mendefinisikan fungsi kernel yang valid (simetris positif pasti) k : T × T → R , juga disebut sebagai kernel pohon . Dalam desain kernel pohon yang praktis berguna, seseorang akan membutuhkannya untuk dapat dihitung dalam waktu polinomial di atas ukuran pohon, dan untuk dapat mendeteksi grafik isomorfik. Kernel pohon seperti itu disebut kernel pohon lengkap .

Kernel Pohon

Sekarang, mari kita perkenalkan beberapa kernel pohon yang berguna untuk mengukur kesamaan pohon. Ide utamanya adalah menghitung kernel untuk setiap pasangan pohon dalam kumpulan data untuk membangun matriks kernel, yang kemudian dapat digunakan untuk mengklasifikasikan kumpulan pohon.

Kernel String

Pertama, kita akan mulai dengan pengenalan singkat tentang kernel string, yang akan membantu kita memperkenalkan metode kernel lain yang didasarkan pada konversi pohon menjadi string.

Mari kita definisikan num y (s) sebagai jumlah kemunculan substring y dalam string s , dengan | s | menunjukkan panjang tali. Kernel string yang akan kami jelaskan di sini didefinisikan sebagai:

K string (S 1 , S 2 ) = s∈F num s ( S 1 )num s (S 2 )w s

Di mana F adalah himpunan substring yang muncul di S 1 dan S 2 , dan parameter w s berfungsi sebagai parameter bobot (misalnya, untuk menekankan substring penting). Seperti yang bisa kita lihat, kernel ini memberikan nilai yang lebih tinggi pada sepasang string ketika mereka berbagi banyak substring yang sama.

Kernel Pohon Berdasarkan Mengubah Pohon menjadi String

Kita dapat menggunakan kernel string ini untuk membangun kernel pohon. Ide di balik kernel ini adalah untuk mengubah dua pohon menjadi dua string secara sistematis yang mengkodekan struktur pohon, dan kemudian menerapkan kernel string di atas ke mereka.

Kami mengubah dua pohon menjadi dua string sebagai berikut:

Biarkan T menyatakan salah satu pohon target, dan beri label(n s ) label string dari simpul n s di T . tag(n s ) menunjukkan representasi string dari subpohon T yang berakar pada n s . Jadi jika n root adalah simpul akar dari T , tag(n root ) adalah representasi string dari seluruh pohon T .

Selanjutnya, biarkan string(T) = tag(n root ) menunjukkan representasi string dari T . Kami akan menerapkan langkah-langkah berikut secara rekursif secara bottom-up untuk mendapatkan string(T) :

• Jika simpul n s adalah daun, misalkan tag(n s ) = “[” + label(n s ) + “]” (di mana + di sini adalah operator rangkaian string).
• Jika simpul n s bukan daun dan memiliki c anak n 1 , n 2 , … , n c , sort tag(n 1 ), tag(n 2 ), … , tag(n c ) secara leksikal untuk mendapatkan tag (n 1* ), tag(n 2* ), … , tag(n c* ) , dan biarkan tag(n s ) = “[” + label(n s ) + tag(n 1* ) + tag(n 2* ) + … + tag(n c* ) + “]” .

Gambar di bawah, menunjukkan contoh konversi pohon ke string ini. Hasilnya adalah string yang dimulai dengan pembatas pembuka seperti “[” dan diakhiri dengan pasangan penutupnya, “]”, dengan setiap pasangan pembatas bersarang yang sesuai dengan subpohon yang berakar pada node tertentu.

Sekarang kita dapat menerapkan konversi di atas ke dua pohon, T 1 dan T 2 , untuk mendapatkan dua string S 1 dan S 2 . Dari sana, kita cukup menerapkan kernel string yang dijelaskan di atas.

Kernel pohon antara T 1 dan T 2 melalui dua string S 1 dan S 2 sekarang dapat diberikan sebagai:

K pohon (T 1 , T 2 ) = K string ( string(T 1 ), string(T 2 ) ) = K string (S 1 , S 2 ) = s∈F num s ( S 1 )num s (S 2 )

Di sebagian besar aplikasi, parameter bobot menjadi w | s | , pembobotan substring berdasarkan panjangnya | s | . Metode pembobotan tipikal untuk w | s | adalah:

• pembobotan konstan ( w | s | = 1 )
• pembobotan spektrum k ( w | s | = 1 jika | s | = k , dan w | s | = 0 jika tidak)
• pembobotan eksponensial ( w | s | = | s | di mana 0 λ 1 adalah laju peluruhan)

Untuk menghitung kernel, cukup menentukan semua substring umum F , dan menghitung berapa kali mereka muncul di S 1 dan S 2 . Langkah tambahan untuk menemukan substring umum ini adalah masalah yang dipelajari dengan baik, dan dapat diselesaikan dalam O( | S 1 | + | S 2 | ) , menggunakan pohon sufiks atau larik sufiks. Jika kita berasumsi bahwa jumlah maksimum huruf (bit, byte, atau karakter, misalnya) yang diperlukan untuk menggambarkan label node adalah konstan, panjang string yang dikonversi adalah | S 1 | = O( | T 1 | ) dan | S 2 | = O( | T2 | ) . Jadi, kompleksitas komputasi dari menghitung fungsi kernel adalah O( | T 1 | + | T 2 | ) , yang linier.

Kernel Pohon Berdasarkan Subpaths

Kernel pohon di atas menggunakan pendekatan horizontal, atau lebar-pertama, untuk mengubah pohon menjadi string. Meskipun pendekatan ini cukup sederhana, konversi ini berarti tidak dapat beroperasi pada pohon secara langsung dalam bentuk aslinya.

Bagian ini akan mendefinisikan kernel pohon yang beroperasi pada struktur vertikal di pohon, yang memungkinkan kernel untuk beroperasi pada pohon secara langsung.

Sebuah subbagian dari sebuah jalan dari akar ke salah satu daun disebut subpath , dan himpunan subpath adalah himpunan dari semua subpath yang termasuk dalam pohon:

Mari kita asumsikan bahwa kita ingin mendefinisikan kernel pohon K(T 1 , T 2 ) antara dua pohon T 1 dan T 2 . Dengan menggunakan set subpath, kita dapat mendefinisikan kernel pohon ini sebagai:

K(T 1 , T 2 ) = p∈P num p (T 1 )num p (T 2 )w | p |

Dimana num p (T) adalah berapa kali subpath p muncul di pohon T , | p | adalah jumlah node di subpath p , dan P adalah himpunan semua subpath di T 1 dan T 2 . w | p | adalah bobotnya, mirip dengan yang diperkenalkan di bagian sebelumnya.

Di sini, kami menyajikan implementasi sederhana dari kernel ini menggunakan pencarian depth-first. Meskipun algoritme ini berjalan dalam waktu kuadrat, ada algoritme yang lebih efisien menggunakan pohon sufiks atau larik sufiks, atau perpanjangan dari algoritme quicksort multikey, yang dapat mencapai waktu linierithmic ( O( | T 1 | log | T 2 | ) ) rata-rata:

 subpath_track = {} def generate_subpaths(path, l): if l == len(path): if tuple(path) not in subpath_track: subpath_track[tuple(path)] = 1 else: subpath_track[tuple(path)] += 1 else: index = 0 while l+index-1 < len(path): if tuple(path[index: l+index]) not in subpath_track: subpath_track[tuple(path[index: l+index])] = 1 else: subpath_track[tuple(path[index: l+index])] += 1 index += 1 generate_subpaths(path, l+1) def get_subpaths(graph, root, track, path): track[root] = True if graph.degree(root) == 1: generate_subpaths(path, 1) else: for node in graph.neighbors(root): if node not in track: get_subpaths(graph, node, track, path + [node, ]) def kernel_subpath(t1, t2, common_track): kernel_v = 0 for p in subpath_track: kernel_v += common_track[t1][p]*common_track[t2][p] return kernel_v

Dalam contoh ini, kami menggunakan parameter pembobotan w | s | w | p | = 1 . Ini memberikan semua subpath bobot yang sama. Namun, ada banyak kasus ketika menggunakan pembobotan k -spektrum, atau beberapa nilai pembobotan yang ditetapkan secara dinamis, adalah tepat.

Situs Pertambangan

Sebelum kita mengakhiri, mari kita lihat secara singkat satu aplikasi klasifikasi pohon di dunia nyata: kategorisasi situs web. Dalam banyak konteks penambangan data, sangat bermanfaat untuk mengetahui “jenis” situs web apa yang berasal dari beberapa data. Ternyata halaman dari situs web yang berbeda dapat dikategorikan cukup efektif menggunakan pohon karena kesamaan dalam struktur halaman web untuk layanan serupa.

Bagaimana kita melakukannya? Dokumen HTML memiliki struktur bersarang logis, yang sangat mirip dengan pohon. Setiap dokumen berisi satu elemen root, dengan elemen tambahan bersarang di dalamnya. Elemen bersarang dalam tag HTML secara logis setara dengan node turunan dari tag tersebut:

Mari kita lihat beberapa kode yang dapat mengubah dokumen HTML menjadi pohon:

 def html_to_dom_tree(root): node_id = 1 q = deque() graph = nx.Graph() q.appendleft({'element': root, "root_id": node_id}) while len(q): node = q.pop() if node and node['element'].name == "body": graph.add_node(node_id, element=node['element'].name) node_id += 1 root_id = node['root_id'] labels[root_id] = node['element'].name for t in node['element'].contents: if t and t.name: graph.add_node(node_id, element=t.name) graph.add_edge(root_id, node_id) q.appendleft({"element": t, "root_id": node_id}) node_id += 1 return graph

Ini akan menghasilkan struktur data pohon yang mungkin terlihat seperti ini:

Implementasi di atas menggunakan beberapa pustaka Python yang berguna: NetworkX, untuk bekerja dengan struktur grafik yang kompleks, dan Beautiful Soup, untuk menarik data dari web dan memanipulasi dokumen.

Memanggil html_to_dom_tree(soup.find("body")) akan mengembalikan objek grafik NetworkX yang di-root pada elemen <body> halaman web.

Katakanlah kita ingin menemukan grup dalam satu set 1.000 halaman beranda situs web. Dengan mengonversi setiap beranda menjadi pohon seperti ini, kita dapat membandingkan masing-masing, misalnya dengan menggunakan kernel pohon subpath yang diberikan di bagian sebelumnya. Dengan pengukuran kesamaan ini, kita dapat menemukan bahwa, misalnya, situs e-niaga, situs berita, blog, dan situs pendidikan mudah dikenali dari kesamaannya satu sama lain.

Kesimpulan

Dalam artikel ini, kami memperkenalkan metode untuk membandingkan elemen data terstruktur pohon satu sama lain, dan menunjukkan cara menerapkan metode kernel ke pohon untuk mendapatkan pengukuran kuantitatif kesamaannya. Metode kernel telah terbukti menjadi pilihan yang sangat baik saat beroperasi di ruang berdimensi tinggi, situasi umum saat bekerja dengan struktur pohon. Teknik-teknik ini mengatur panggung untuk analisis lebih lanjut dari kumpulan pohon besar, menggunakan metode yang dipelajari dengan baik yang beroperasi di atas matriks kernel.

Struktur pohon ditemukan di banyak area kata nyata seperti dokumen XML dan HTML, senyawa kimia, pemrosesan bahasa alami, atau jenis perilaku pengguna tertentu. Seperti yang ditunjukkan dalam contoh membangun pohon dari HTML, teknik ini memberdayakan kita untuk melakukan analisis yang berarti dalam domain ini.