Ağaç Çekirdekleri: Ağaç Yapılı Veriler Arasındaki Benzerliğin Ölçülmesi

Bir ağ veya grafik , aralarındaki ilişkiler bağlantılar veya kenarlar ile tanımlanan, düğümler biçimindeki bir tür yapılandırılmış veridir. Bir grafikteki düğümler ve kenarlar, sayısal veya kategorik veya hatta daha karmaşık olabilen çeşitli niteliklere sahip olabilir.

Bugün, ağlar veya grafikler şeklinde büyük miktarda veri mevcuttur. Örneğin, web sayfaları ve köprüleri, sosyal ağları, anlamsal ağları, biyolojik ağları, bilimsel literatür için alıntı ağları vb. ile World Wide Web.

Ağaç , özel bir grafik türüdür ve birçok veri türünü temsil etmek için doğal olarak uygundur. Ağaçların analizi, bilgisayar ve veri biliminde önemli bir alandır. Bu yazımızda ağaçlardaki link yapısının analizine bakacağız. Özellikle, ağaç grafiklerini birbirleriyle karşılaştırmak için bir yöntem olan ağaç çekirdeklerine odaklanacağız ve benzerlikleri veya farklılıkları hakkında ölçülebilir ölçümler elde etmemizi sağlayacağız. Bu, sınıflandırma ve veri analizi gibi birçok modern uygulama için önemli bir süreçtir.

Yapılandırılmış Verilerin Denetimsiz Sınıflandırılması

Sınıflandırma , makine öğrenimi ve veri analizinin önemli bir bileşenidir. Genel olarak, sınıflandırma denetimli veya denetimsiz olabilir. Denetimli sınıflandırmada, sınıflar zaten bilinmektedir ve eğitim verilerinden doğru sınıfların zaten verildiği bir sınıflandırma modeli oluşturulur. Denetimsiz sınıflandırma, aksine, hiçbirinin bilinmediği sınıfları belirlemeye çalışır ve verileri benzerliklerinin bir ölçüsüne göre kategoriler halinde gruplandırır.

Denetimsiz sınıflandırma, benzer ağaç ağlarının gruplarını belirlemek için çizge teorisi ile birleştirilebilir. Ağaç veri yapıları, çeşitli etki alanlarından nesneleri modellemek için kullanılır. Örneğin, doğal dil işlemede (NLP), ayrıştırma ağaçları sıralı, etiketli ağaçlar olarak modellenir. Otomatik akıl yürütmede, arama uzayının, köşeleri arama durumları ile ilişkili bir ağaç olarak temsil edildiği ve kenarların çıkarım adımlarını temsil ettiği arama yoluyla birçok problem çözülür. Ayrıca HTML ve XML belgeleri gibi yarı yapılandırılmış veriler sıralı, etiketli ağaçlar olarak modellenebilir.

Bu alanlar, denetimsiz sınıflandırma teknikleri ile faydalı bir şekilde analiz edilebilir. NLP'de sınıflandırma, bir dizi cümleyi otomatik olarak sorular, komutlar ve ifadeler halinde gruplandırmak için kullanılabilir. Benzer şekilde, benzer web sitelerinin grupları, HTML kaynaklarına sınıflandırma yöntemleri uygulanarak tanımlanabilir. Bu durumların her birinde, tek ihtiyacımız olan, iki ağacın birbirine ne kadar "benzer" olduğunu ölçmenin bir yoludur.

Boyutluluğun Laneti

Çoğu sınıflandırma algoritması, verilerin özellik uzayında lineer cebir kullanılarak analiz edilebilmesi için verinin öznitelik uzayındaki özelliklerinin değerlerini temsil eden vektörleştirilmiş bir forma dönüştürülmesini gerektirir. Ağaçlar gibi yapılandırılmış veya yarı yapılandırılmış verilerde, sonuç vektörlerinin boyutu (yani, özellik uzayındaki özelliklerin sayısı) oldukça yüksek olabilir, çünkü özellik uzayı yapı hakkındaki bilgileri korumalıdır.

Birçok sınıflandırma tekniğinin girdinin boyutuyla etkili bir şekilde ölçeklenemediği düşünüldüğünde, bu önemli bir dezavantaj olabilir. Diğer bir deyişle, girdinin boyutsallığının artmasıyla sınıflandırma güçleri azalmaktadır. Bu sorun, boyutsallığın laneti olarak bilinir.

Performanstaki bu düşüşün nedeni hakkında bir fikir edinmek için, d boyutunda bir X uzayını düşünün. X'in düzgün dağılmış bir dizi nokta içerdiğini varsayalım. X'in boyut sayısı artarsa, aynı yoğunluğu korumak için gerekli noktaların sayısı katlanarak artmalıdır. Başka bir deyişle, girdinin boyutları ne kadar fazlaysa, o verinin seyrek olma olasılığı o kadar fazladır. Genel olarak, seyrek bir veri kümesi, iyi bir sınıflandırıcı oluşturmak için yeterli bilgi vermez çünkü veri öğeleri arasındaki korelasyonlar, algoritmaların algılaması için çok zayıftır.

Yukarıdaki her bir özellik alanı sekiz veri noktası içerir. Tek boyutlu uzayda, solda beş, sağda üç noktadan oluşan bir grup belirlemek kolaydır. Bu noktaları daha fazla sayıda özellik (yani boyutlar) üzerine yaymak, bu grupları bulmayı daha da zorlaştırır. Gerçek uygulamalarda, özellik uzayları kolaylıkla yüzlerce boyuta sahip olabilir.

Etki alanıyla ilgili bilgiler yönetilebilir bir dizi özellik seçmek için etkin bir şekilde kullanılabildiğinde, yapılandırılmış veriler için vektörleştirilmiş bir temsil uygundur. Bu tür bilgiler mevcut olmadığında, vektör uzayında işlemler gerçekleştirmeden yapılandırılmış verileri doğrudan işleyebilen tekniklerin kullanılması arzu edilir.

Çekirdek Yöntemleri

Çekirdek yöntemleri, verileri vektör biçimine dönüştürme ihtiyacını ortadan kaldırır. İhtiyaç duydukları tek bilgi, bir veri setindeki her bir öğe çiftinin benzerliğinin bir ölçümüdür. Bu ölçüme çekirdek , onu belirleme işlevine ise çekirdek işlevi denir. Çekirdek yöntemleri, özellik uzayında doğrusal ilişkiler arar. İşlevsel olarak, özellik uzayındaki iki veri noktasının nokta çarpımını almaya eşdeğerdirler ve gerçekten de özellik tasarımı, çekirdek fonksiyon tasarımında hala yararlı bir adım olabilir. Bununla birlikte, çekirdek yöntemleri, nokta çarpımı bir çekirdek işleviyle değiştirmenin mümkün olduğu gösterilebildiğinden, çekirdek işlevi simetrik, pozitif yarı tanımlı bir işlev olduğu sürece, doğrudan özellik alanı üzerinde çalışmaktan kaçınır. orijinal uzayında.

Çekirdek işlevlerini kullanmanın avantajı, bu nedenle, çok büyük bir özellik uzayının, özellik uzayının boyutuna değil, çekirdek fonksiyonunun karmaşıklığına bağlı bir hesaplama karmaşıklığı ile analiz edilebilmesidir, bu, çekirdek yöntemlerinin lanete maruz kalmaması anlamına gelir. boyutluluk.

n örnekten oluşan sonlu bir veri kümesini düşünürsek, boyutu her zaman n × n olan bir çekirdek matrisi üreterek verilerdeki benzerliklerin tam bir temsilini elde edebiliriz. Bu matris, her bir örneğin boyutundan bağımsızdır. Bu özellik, geniş bir özellik alanına sahip küçük bir örnek veri kümesi analiz edilecek olduğunda kullanışlıdır.

Genel olarak, çekirdek yöntemleri, veri temsili sorusuna farklı bir cevaba dayanmaktadır. Girdi noktalarını bir özellik uzayına eşlemek yerine, veriler bir K çekirdek matrisinde ikili karşılaştırmalar yoluyla temsil edilir ve ilgili tüm analizler çekirdek matrisi üzerinde gerçekleştirilebilir.

Birçok veri madenciliği yöntemi çekirdeklenebilir. Ağaç yapılı veri örneklerini, destek vektör makineleri gibi çekirdek yöntemleriyle sınıflandırmak için, ağaç çekirdeği olarak da adlandırılan geçerli (simetrik pozitif tanımlı) bir çekirdek işlevi k: T × T → R tanımlamak yeterlidir. Pratik olarak yararlı ağaç çekirdeklerinin tasarımında, bunların ağacın boyutu üzerinden polinom zamanında hesaplanabilmeleri ve izomorfik grafikleri saptayabilmeleri gerekir. Bu tür ağaç çekirdeklerine tam ağaç çekirdekleri denir.

Ağaç Çekirdekleri

Şimdi, ağaçların benzerliğini ölçmek için bazı yararlı ağaç çekirdeklerini tanıtalım. Ana fikir, daha sonra ağaç kümelerini sınıflandırmak için kullanılabilecek bir çekirdek matrisi oluşturmak için veri kümesindeki her bir ağaç çifti için çekirdeği hesaplamaktır.

Dize Çekirdeği

İlk olarak, ağaçları dizgelere dönüştürmeye dayalı başka bir çekirdek yöntemini tanıtmamıza yardımcı olacak, dizge çekirdeklerine kısa bir girişle başlayacağız.

Sayı y (s) 'yi bir s dizgisinde bir y alt dizgisinin oluşum sayısı olarak tanımlayalım, | s | dizenin uzunluğunu belirtir. Burada tanımlayacağımız string kernel şu şekilde tanımlanır:

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

Burada F , hem S 1 hem de S 2'de meydana gelen alt dizeler kümesidir ve w s parametresi bir ağırlık parametresi olarak işlev görür (örneğin, önemli alt dizeleri vurgulamak için). Gördüğümüz gibi, bu çekirdek, birçok ortak alt diziyi paylaştığında bir çift diziye daha yüksek bir değer verir.

Ağaçları Dizelere Dönüştürmeye Dayalı Ağaç Çekirdeği

Bir ağaç çekirdeği oluşturmak için bu dize çekirdeğini kullanabiliriz. Bu çekirdeğin arkasındaki fikir, iki ağacı, ağacın yapısını kodlayan sistematik bir şekilde iki dizeye dönüştürmek ve ardından yukarıdaki dize çekirdeğini onlara uygulamaktır.

İki ağacı aşağıdaki gibi iki dizgeye dönüştürüyoruz:

T , hedef ağaçlardan birini göstersin ve etiket(n s ) T içindeki n s düğümünün dize etiketini göstersin. tag(n s ) , n s'de köklenmiş T'nin alt ağacının dize temsilini belirtir. Dolayısıyla, n root , T'nin kök düğümüyse, tag(n root ) , T ağacının tamamının dize temsilidir.

Ardından, string(T) = tag(n root ) , T öğesinin dize temsilini göstersin. string(T) elde etmek için aşağıdaki adımları aşağıdan yukarıya yinelemeli olarak uygulayacağız:

• n s düğümü bir yapraksa, tag(n s ) = “[” + label(n s ) + “]” olsun (burada + dize birleştirme operatörüdür).
• n s düğümü bir yaprak değilse ve c çocuğu varsa n 1 , n 2 , … , nc , sort tag(n 1 ), tag(n 2 ), … , tag(n c ) etiketini elde etmek için sözcüksel sırayla (n 1* ), tag(n 2* ), … , tag(n c* ) ve let tag(n s ) = “[” + label(n s ) + tag(n 1* ) + tag(n 2* ) + … + etiket(n c* ) + “]” .

Aşağıdaki şekil, bu ağaçtan dizgiye dönüştürmenin bir örneğini göstermektedir. Sonuç, "[" gibi bir açılış sınırlayıcı ile başlayan ve kapanış karşılığı olan "]" ile biten, her bir iç içe sınırlayıcı çiftinin belirli bir düğümde köklenmiş bir alt ağaca karşılık geldiği bir dizedir.

Şimdi, iki S 1 ve S 2 dizesini elde etmek için yukarıdaki dönüşümü iki ağaca, T 1 ve T 2 'ye uygulayabiliriz. Buradan, yukarıda açıklanan string çekirdeğini basitçe uygulayabiliriz.

İki dizi S 1 ve S 2 aracılığıyla T 1 ve T 2 arasındaki ağaç çekirdeği şimdi şu şekilde verilebilir:

K ağacı (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 ) w s

Çoğu uygulamada, ağırlık parametresi w | s | , bir alt dizgiyi uzunluğuna göre ağırlıklandırma | s | . w için tipik ağırlıklandırma yöntemleri | s | şunlardır:

• sabit ağırlık ( w | s | = 1 )
• k -spektrum ağırlığı ( w | s | = 1 ise | s | = k ve w | s | = 0 değilse)
• üstel ağırlıklandırma ( w | s | = λ | s | burada 0 ≤ λ ≤ 1 bir azalma oranıdır)

Çekirdeği hesaplamak için, tüm ortak F alt dizilerini belirlemek ve bunların S 1 ve S 2'de kaç kez meydana geldiklerini saymak yeterlidir. Ortak alt dizileri bulmaya yönelik bu ek adım, iyi çalışılmış bir sorundur ve O( | S 1 | + | S 2 | ) , sonek ağaçları veya sonek dizileri kullanılarak gerçekleştirilebilir. Bir düğümün etiketini tanımlamak için gereken maksimum harf sayısının (örneğin bit, bayt veya karakter) sabit olduğunu varsayarsak, dönüştürülen dizelerin uzunlukları | 1 | = O( | T 1 | ) ve | S2 | = O( | T 2 | ) . Bu nedenle, çekirdek işlevini hesaplamanın hesaplama karmaşıklığı, doğrusal olan O( | T 1 | + | T 2 | ) 'dir.

Alt Yollara Dayalı Ağaç Çekirdeği

Yukarıdaki ağaç çekirdeği, ağaçları dizgelere dönüştürmek için yatay veya genişlik öncelikli bir yaklaşım kullandı. Bu yaklaşım oldukça basit olsa da, bu dönüştürme, doğrudan orijinal formlarında ağaçlar üzerinde çalışamayacağı anlamına gelir.

Bu bölüm, ağaçlardaki dikey yapılar üzerinde çalışan ve çekirdeğin doğrudan ağaç üzerinde çalışmasına izin veren bir ağaç çekirdeği tanımlayacaktır.

Kökten yapraklardan birine giden yolun alt bölümüne alt yol denir ve alt yol kümesi , ağaçta bulunan tüm alt yolların kümesidir:

İki ağaç T 1 ve T 2 arasında bir K(T 1 , T 2 ) ağaç çekirdeği tanımlamak istediğimizi varsayalım. Alt yol kümesini kullanarak bu ağaç çekirdeğini şu şekilde tanımlayabiliriz:

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

Burada p sayısı (T) , alt yol p'nin T ağacında meydana gelme sayısıdır, | p | p alt yolundaki düğüm sayısıdır ve P , T 1 ve T 2'deki tüm alt yolların kümesidir . w | p | önceki bölümde tanıtılana benzer ağırlıktır.

Burada, derinlik öncelikli arama kullanarak bu çekirdeğin basit bir uygulamasını sunuyoruz. Bu algoritma ikinci dereceden zamanda çalışsa da, sonek ağaçları veya sonek dizileri veya çok tuşlu hızlı sıralama algoritmasının bir uzantısı kullanılarak ortalama olarak lineerithmik zaman ( O( | T 1 | log | T 2 | ) ) elde edebilen daha verimli algoritmalar mevcuttur:

 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

Bu örnekte w | ağırlıklandırma parametresini kullandık. s | w | p | = 1 . Bu, tüm alt yollara eşit ağırlık verir. Bununla birlikte, k -spektrum ağırlıklandırmasının veya dinamik olarak atanmış bazı ağırlık değerlerinin kullanılmasının uygun olduğu birçok durum vardır.

Madencilik Web Siteleri

Bitirmeden önce, gerçek dünyadaki bir ağaç sınıflandırma uygulamasına kısaca bakalım: web sitelerinin sınıflandırılması. Birçok veri madenciliği bağlamında, bazı verilerin hangi web sitesi "türünden" geldiğini bilmek faydalıdır. Benzer hizmetler için web sayfalarının nasıl yapılandırıldığına ilişkin benzerlikler nedeniyle, farklı web sitelerinden gelen sayfaların ağaçlar kullanılarak oldukça etkili bir şekilde kategorize edilebileceği ortaya çıktı.

Bunu nasıl yaparız? HTML belgeleri, bir ağaca çok benzeyen mantıksal iç içe geçmiş bir yapıya sahiptir. Her belge, içinde ek öğeler bulunan bir kök öğe içerir. Bir HTML etiketindeki iç içe öğeler, mantıksal olarak o etiketin alt düğümlerine eşdeğerdir:

Bir HTML belgesini bir ağaca dönüştürebilecek bazı kodlara bir göz atalım:

 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

Bu, şuna benzeyen bir ağaç veri yapısı üretecektir:

Yukarıdaki uygulama, birkaç yararlı Python kitaplığından yararlanır: karmaşık grafik yapılarıyla çalışmak için NetworkX ve web'den veri çekmek ve belgeleri işlemek için Beautiful Soup.

html_to_dom_tree(soup.find("body")) çağrılması, web sayfasının <body> öğesinde köklenmiş bir NetworkX grafik nesnesi döndürür.

1000 web sitesi ana sayfasındaki grupları bulmak istediğimizi varsayalım. Her ana sayfayı bunun gibi bir ağaca dönüştürerek, örneğin önceki bölümde verilen alt yol ağacı çekirdeğini kullanarak her birini karşılaştırabiliriz. Bu benzerlik ölçümleriyle, örneğin e-ticaret sitelerinin, haber sitelerinin, blogların ve eğitim sitelerinin birbirlerine benzerlikleriyle kolayca tanımlandıklarını bulabiliriz.

Çözüm

Bu makalede, ağaç yapılı veri öğelerini birbiriyle karşılaştırmak için yöntemler tanıttık ve benzerliklerinin ölçülebilir bir ölçümünü elde etmek için çekirdek yöntemlerinin ağaçlara nasıl uygulanacağını gösterdik. Kernel yöntemlerinin, ağaç yapılarıyla çalışırken yaygın bir durum olan yüksek boyutlu uzaylarda çalışırken mükemmel bir seçim olduğu kanıtlanmıştır. Bu teknikler, çekirdek matrisi üzerinde çalışan iyi çalışılmış yöntemleri kullanarak büyük ağaç kümelerinin daha fazla analizi için zemin hazırlar.

Ağaç yapılarına, XML ve HTML belgeleri, kimyasal bileşikler, doğal dil işleme veya belirli kullanıcı davranışları gibi birçok gerçek kelime alanında rastlanır. HTML'den ağaç oluşturma örneğinde gösterildiği gibi, bu teknikler bu alanlarda anlamlı analizler yapmamızı sağlar.