نواة الشجرة: قياس التشابه بين البيانات المهيكلة بالشجرة

الشبكة أو الرسم البياني هو نوع من البيانات المهيكلة في شكل عقد ، مع وصف العلاقات بينها بواسطة روابط أو حواف . قد تحتوي العقد والحواف في الرسم البياني على العديد من السمات التي قد تكون رقمية أو فئوية أو حتى أكثر تعقيدًا.

اليوم ، تتوفر كمية هائلة من البيانات في شكل شبكات أو رسوم بيانية. على سبيل المثال ، شبكة الويب العالمية ، بصفحات الويب والارتباطات التشعبية الخاصة بها ، والشبكات الاجتماعية ، والشبكات الدلالية ، والشبكات البيولوجية ، وشبكات الاستشهاد بالأدب العلمي ، وما إلى ذلك.

الشجرة هي نوع خاص من الرسم البياني ، وهي مناسبة بشكل طبيعي لتمثيل العديد من أنواع البيانات. يعد تحليل الأشجار مجالًا مهمًا في علوم الكمبيوتر والبيانات. في هذه المقالة ، سنلقي نظرة على تحليل بنية الارتباط في الأشجار. على وجه الخصوص ، سوف نركز على نواة الشجرة ، وهي طريقة لمقارنة الرسوم البيانية الشجرية مع بعضها البعض ، مما يسمح لنا بالحصول على قياسات قابلة للقياس الكمي لأوجه التشابه أو الاختلافات بينهما. هذه عملية مهمة للعديد من التطبيقات الحديثة مثل التصنيف وتحليل البيانات.

التصنيف غير الخاضع للرقابة للبيانات المهيكلة

التصنيف عنصر مهم في التعلم الآلي وتحليل البيانات. بشكل عام ، يمكن أن يكون التصنيف إما خاضعًا للإشراف أو غير خاضع للإشراف . في التصنيف الخاضع للإشراف ، تكون الفصول الدراسية معروفة بالفعل ، ويتم إنشاء نموذج تصنيف من بيانات التدريب التي يتم فيها تقديم الفصول الصحيحة بالفعل. على النقيض من ذلك ، يحاول التصنيف غير الخاضع للإشراف تحديد الفئات التي لا يُعرف أي منها ، وتجميع البيانات في فئات بناءً على بعض مقاييس التشابه بينها.

يمكن دمج التصنيف غير الخاضع للإشراف مع نظرية الرسم البياني لتحديد مجموعات شبكات الأشجار المتشابهة. يتم استخدام هياكل بيانات الشجرة لنمذجة الكائنات من عدة مجالات. في معالجة اللغة الطبيعية (NLP) ، على سبيل المثال ، يتم نمذجة أشجار التحليل على أنها أشجار مرتبة ومسمى. في الاستدلال الآلي ، يتم حل العديد من المشكلات عن طريق البحث ، حيث يتم تمثيل مساحة البحث كشجرة ترتبط رؤوسها بحالات البحث ، وتمثل الحواف خطوات الاستدلال. أيضًا ، يمكن نمذجة البيانات شبه المنظمة ، مثل مستندات HTML و XML ، كأشجار مرتبة ومسمى.

يمكن تحليل هذه المجالات بشكل مفيد من خلال تقنيات التصنيف غير الخاضعة للرقابة. في البرمجة اللغوية العصبية ، يمكن استخدام التصنيف لتجميع مجموعة من الجمل تلقائيًا في أسئلة وأوامر وبيانات. وبالمثل ، يمكن تحديد مجموعات مواقع الويب المتشابهة من خلال تطبيق أساليب التصنيف على مصدر HTML الخاص بهم. في كل حالة من هذه الحالات ، كل ما نحتاجه هو طريقة لقياس مدى "تشابه" شجرتين مع بعضهما البعض.

لعنة الأبعاد

تتطلب معظم خوارزميات التصنيف تحويل البيانات إلى نموذج متجه ، يمثل قيم ميزات البيانات في مساحة الميزة ، بحيث يمكن تحليل البيانات في مساحة الميزة باستخدام الجبر الخطي. في البيانات المهيكلة أو شبه المنظمة ، مثل الأشجار ، قد تكون أبعاد المتجهات الناتجة (أي عدد الميزات في مساحة الميزة) عالية جدًا ، نظرًا لأن مساحة الميزة يجب أن تحافظ على معلومات حول الهيكل.

قد يكون هذا عيبًا كبيرًا ، مع الأخذ في الاعتبار أن العديد من تقنيات التصنيف غير قادرة على التوسع بشكل فعال مع أبعاد المدخلات. بمعنى آخر ، تتناقص قوة تصنيفها مع زيادة أبعاد المدخلات. تُعرف هذه المشكلة بلعنة الأبعاد.

للحصول على فكرة عن سبب هذا التدهور في الأداء ، ضع في اعتبارك مساحة X من البعد d . افترض أن X تحتوي على مجموعة من النقاط موزعة بشكل موحد. إذا زاد عدد أبعاد X ، يجب أن يزداد عدد النقاط اللازمة للحفاظ على نفس الكثافة أضعافًا مضاعفة. بمعنى آخر ، كلما زادت أبعاد الإدخال ، زاد احتمال أن تكون هذه البيانات متناثرة. بشكل عام ، لا تعطي مجموعة البيانات المتفرقة معلومات كافية لبناء مصنف جيد لأن الارتباطات بين عناصر البيانات ضعيفة جدًا بحيث لا تكتشفها الخوارزميات.

تحتوي كل مساحة ميزة أعلاه على ثماني نقاط بيانات. في الفضاء أحادي البعد ، من السهل تحديد مجموعة من خمس نقاط على اليسار وثلاث على اليمين. إن تمديد هذه النقاط على عدد أكبر من الميزات (أي الأبعاد) يجعل العثور على هذه المجموعات أكثر صعوبة. في التطبيقات الحقيقية ، يمكن أن تحتوي مساحات الميزات بسهولة على مئات الأبعاد.

يعد التمثيل المتجه للبيانات المنظمة مناسبًا عندما يمكن استخدام المعلومات حول المجال بشكل فعال لتحديد مجموعة يمكن إدارتها من الميزات. عندما لا تتوفر مثل هذه المعلومات ، فمن المستحسن الاستفادة من التقنيات التي يمكنها التعامل مع البيانات المنظمة مباشرة ، دون إجراء عمليات في مساحة المتجه.

طرق Kernel

تتجنب أساليب Kernel الحاجة إلى تحويل البيانات إلى شكل متجه. المعلومات الوحيدة التي يحتاجونها هي قياس التشابه بين كل زوج من العناصر في مجموعة البيانات. يسمى هذا القياس بـ kernel ، وتسمى وظيفة تحديده وظيفة kernel . تبحث طرق Kernel عن العلاقات الخطية في مساحة المعالم. من الناحية الوظيفية ، فهي مكافئة لأخذ المنتج النقطي لنقطتي بيانات في مساحة الميزة ، وقد يظل تصميم الميزات بالفعل خطوة مفيدة في تصميم وظيفة kernel. ومع ذلك ، تتجنب طرق طرق kernel العمل مباشرة على مساحة الميزة حيث يمكن إثبات أنه من الممكن استبدال المنتج النقطي بوظيفة kernel ، طالما أن وظيفة kernel هي دالة متماثلة وإيجابية شبه محددة يمكن أن تأخذ كمدخلات للبيانات في مساحتها الأصلية.

تتمثل ميزة استخدام وظائف kernel في أنه يمكن تحليل مساحة ميزة ضخمة مع تعقيد حسابي لا يعتمد على حجم مساحة الميزة ، ولكن على مدى تعقيد وظيفة kernel ، مما يعني أن طرق kernel لا تعاني من اللعنة من الأبعاد.

إذا أخذنا في الاعتبار مجموعة بيانات محدودة تتكون من n أمثلة ، فيمكننا الحصول على تمثيل كامل لأوجه التشابه داخل البيانات عن طريق إنشاء مصفوفة النواة التي يكون حجمها دائمًا n × n . هذه المصفوفة مستقلة عن حجم كل مثال على حدة. هذه الخاصية مفيدة عند تحليل مجموعة بيانات صغيرة من الأمثلة ذات مساحة المعلم الكبيرة.

بشكل عام ، تعتمد طرق kernel على إجابة مختلفة لمسألة تمثيل البيانات. بدلاً من تعيين نقاط الإدخال في مساحة ميزة ، يتم تمثيل البيانات عبر مقارنات زوجية في مصفوفة النواة K ، ويمكن إجراء جميع التحليلات ذات الصلة عبر مصفوفة النواة.

يمكن تحويل العديد من طرق التنقيب عن البيانات إلى النواة. لتصنيف مثيلات البيانات المبنية على شجرة باستخدام طرق kernel ، مثل آلات المتجهات الداعمة ، يكفي تحديد دالة نواة صالحة (محددة إيجابية متماثلة) k: T × T → R ، يشار إليها أيضًا باسم نواة الشجرة . في تصميم حبات شجرة مفيدة عمليًا ، قد يتطلب المرء أن تكون قابلة للحساب في وقت متعدد الحدود على حجم الشجرة ، وأن تكون قادرًا على اكتشاف الرسوم البيانية المتشابهة. تسمى حبات الأشجار هذه حبات الأشجار الكاملة .

نواة الشجرة

الآن ، دعنا نقدم بعض حبات الأشجار المفيدة لقياس تشابه الأشجار. الفكرة الرئيسية هي حساب النواة لكل زوج من الأشجار في مجموعة البيانات من أجل بناء مصفوفة النواة ، والتي يمكن استخدامها بعد ذلك لتصنيف مجموعات الأشجار.

سلسلة نواة

أولاً ، سنبدأ بمقدمة قصيرة لنواة السلسلة ، والتي ستساعدنا على تقديم طريقة نواة أخرى تعتمد على تحويل الأشجار إلى سلاسل.

دعنا نحدد عدد y (s) على أنه عدد تكرارات السلسلة الفرعية y في سلسلة s ، مع | الصورة | تدل على طول السلسلة. يتم تعريف نواة السلسلة التي سنصفها هنا على أنها:

سلسلة K (S 1 ، S 2 ) = Σ s∈F num s (S 1 ) num s (S 2 ) w s

حيث F هي مجموعة السلاسل الفرعية التي تحدث في كل من S 1 و S 2 ، وتعمل المعلمة w كمعامل وزن (على سبيل المثال ، للتأكيد على سلاسل فرعية مهمة). كما نرى ، تعطي هذه النواة قيمة أعلى لزوج من السلاسل عندما تشترك في العديد من السلاسل الفرعية المشتركة.

نواة الشجرة على أساس تحويل الأشجار إلى سلاسل

يمكننا استخدام نواة السلسلة لبناء نواة شجرة. الفكرة وراء هذه النواة هي تحويل شجرتين إلى خيطين بطريقة منهجية ترميز بنية الشجرة ، ثم تطبيق نواة السلسلة أعلاه عليها.

نقوم بتحويل الشجرتين إلى خيطين على النحو التالي:

دع T يشير إلى إحدى الأشجار المستهدفة ، وقم بتسمية (n ) تسمية سلسلة العقدة n s في T. تشير العلامة (n s ) إلى تمثيل السلسلة للشجرة الفرعية لـ T المتجذر عند n s . لذلك إذا كانت n root هي العقدة الجذرية لـ T ، فإن العلامة (n root ) هي تمثيل السلسلة للشجرة T بأكملها.

بعد ذلك ، دع السلسلة (T) = العلامة (n root ) تشير إلى تمثيل سلسلة T. سنطبق بشكل متكرر الخطوات التالية بطريقة تصاعدية للحصول على سلسلة (T) :

• إذا كانت العقدة n s عبارة عن ورقة ، فدع العلامة (n s ) = "[" + التسمية (n s ) + "]" (حيث + هنا هو عامل سلسلة السلسلة).
• إذا لم تكن العقدة n s ورقة ولديها c أطفال n 1 ، n 2 ،…، n c ، علامة التصنيف (n 1 )، علامة (n 2 )،…، علامة (n c ) بترتيب معجمي للحصول على علامة (ن 1 * ) ، علامة (ن 2 * ) ، ... ، علامة (ن ج * ) ، وترك العلامة (ن س ) = "[" + تسمية (ن س ) + علامة (ن 1 * ) + علامة (ن 2 * ) +… ​​+ علامة (ن ج * ) + "]" .

يوضح الشكل أدناه مثالاً على هذا التحويل من شجرة إلى سلسلة. والنتيجة هي سلسلة تبدأ بمحدد فتح مثل "[" وتنتهي بنظيره المغلق ، "]" ، مع كل زوج متداخل من المحددات المطابقة لشجرة فرعية متجذرة في عقدة معينة.

يمكننا الآن تطبيق التحويل أعلاه على شجرتين ، T 1 و T 2 ، للحصول على سلسلتين S 1 و S 2 . من هناك ، يمكننا ببساطة تطبيق نواة السلسلة الموصوفة أعلاه.

يمكن الآن إعطاء نواة الشجرة بين T 1 و T 2 عبر سلسلتين S 1 و S 2 على النحو التالي:

شجرة K (T 1 ، T 2 ) = سلسلة K (سلسلة (T 1 ) ، سلسلة (T 2 )) = سلسلة K (S 1 ، S 2 ) = Σ s∈F num s (S 1 ) num s (S 2 ) ث

في معظم التطبيقات ، تصبح معلمة الوزن w | الصورة | ، ترجيح سلسلة فرعية بناءً على طولها | الصورة | . طرق الترجيح النموذجية لـ w | الصورة | نكون:

• وزن ثابت ( ث | ث | = 1 )
• وزن الطيف ك ( w | s | = 1 if | s | = k و w | s | = 0 خلاف ذلك)
• الترجيح الأسي ( w | s | = λ | s | حيث 0 λ ≤ 1 معدل اضمحلال)

لحساب النواة ، يكفي تحديد كل السلاسل الفرعية الشائعة F ، وإحصاء عدد مرات ظهورها في S 1 و S 2 . هذه الخطوة الإضافية لإيجاد السلاسل الفرعية المشتركة هي مشكلة مدروسة جيدًا ، ويمكن إنجازها في O ( | S 1 | + | S 2 | ) ، باستخدام أشجار لاحقة أو مصفوفات لاحقة. إذا افترضنا أن الحد الأقصى لعدد الأحرف (بتات أو بايت أو أحرف ، على سبيل المثال) اللازمة لوصف تسمية العقدة ثابت ، فإن أطوال السلاسل المحولة هي | ق 1 | = O ( | T 1 | ) و | ق 2 | = O ( | T 2 | ) . لذا ، فإن التعقيد الحسابي لحساب دالة النواة هو O ( | T 1 | + | T 2 | ) ، وهو خطي.

نواة الشجرة على أساس المسارات الفرعية

استخدمت نواة الشجرة أعلاه نهجًا أفقيًا أو عرضًا أولًا لتحويل الأشجار إلى سلاسل. في حين أن هذا الأسلوب بسيط للغاية ، فإن هذا التحويل يعني أنه لا يمكن أن يعمل على الأشجار مباشرة في شكلها الأصلي.

سيحدد هذا القسم نواة الشجرة التي تعمل على الهياكل الرأسية للأشجار ، مما يسمح للنواة بالعمل على الشجرة مباشرة.

يسمى القسم الفرعي للمسار من الجذر إلى أحد الأوراق مسارًا فرعيًا ، ومجموعة المسار الفرعي هي مجموعة جميع المسارات الفرعية المضمنة في الشجرة:

لنفترض أننا نريد تعريف نواة الشجرة K (T 1 ، T 2 ) بين شجرتين T 1 و T 2 . باستخدام مجموعة المسار الفرعي ، يمكننا تعريف نواة الشجرة هذه على النحو التالي:

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

حيث num p (T) هو عدد مرات حدوث المسار الفرعي p في الشجرة T ، | ص | هو عدد العقد في المسار الفرعي p ، و P هي مجموعة كل المسارات الفرعية في T 1 و T 2 . ث | ص | هو الوزن ، مشابهًا للوزن الذي تم تقديمه في القسم السابق.

هنا ، نقدم تنفيذًا بسيطًا لهذه النواة باستخدام بحث عميق أولاً. على الرغم من أن هذه الخوارزمية تعمل في الوقت التربيعي ، إلا أن هناك خوارزميات أكثر فاعلية باستخدام أشجار لاحقة أو مصفوفات لاحقة ، أو امتدادًا لخوارزمية الفرز السريع متعدد المسارات ، والتي يمكنها تحقيق الوقت الخطي ( O ( | T 1 | log | T 2 | ) ) في المتوسط:

 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

في هذا المثال ، استخدمنا معامل الترجيح w | الصورة | ث | ص | = 1 . هذا يعطي كل المسارات الفرعية ترجيحًا متساويًا. ومع ذلك ، هناك العديد من الحالات التي يكون فيها استخدام ترجيح k -spectrum ، أو بعض قيم الوزن المحددة ديناميكيًا ، مناسبًا.

مواقع التعدين

قبل أن نختتم ، دعنا نلقي نظرة سريعة على أحد التطبيقات الواقعية لتصنيف الأشجار: تصنيف مواقع الويب. في العديد من سياقات التنقيب عن البيانات ، من المفيد معرفة "نوع" موقع الويب الذي تأتي منه بعض البيانات. اتضح أنه يمكن تصنيف الصفحات من مواقع الويب المختلفة بشكل فعال للغاية باستخدام الأشجار بسبب أوجه التشابه في كيفية تنظيم صفحات الويب للخدمات المماثلة.

كيف نفعل ذلك؟ تحتوي مستندات HTML على بنية متداخلة منطقية تشبه إلى حد كبير الشجرة. يحتوي كل مستند على عنصر جذر واحد ، مع عناصر إضافية متداخلة بداخله. العناصر المتداخلة في علامة HTML مكافئة منطقيًا للعقد الفرعية لتلك العلامة:

دعنا نلقي نظرة على بعض التعليمات البرمجية التي يمكنها تحويل مستند HTML إلى شجرة:

 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

سينتج عن ذلك بنية بيانات شجرية قد تبدو كالتالي:

يستخدم التطبيق أعلاه اثنين من مكتبات Python المفيدة: NetworkX ، للعمل مع هياكل الرسوم البيانية المعقدة ، و Beautiful Soup ، لسحب البيانات من الويب ومعالجة المستندات.

سيؤدي استدعاء html_to_dom_tree(soup.find("body")) إلى إرجاع كائن رسم بياني لـ NetworkX متجذر في عنصر <body> بصفحة الويب.

لنفترض أننا نريد العثور على مجموعات في مجموعة من 1000 صفحة رئيسية لموقع الويب. من خلال تحويل كل صفحة رئيسية إلى شجرة مثل هذه ، يمكننا مقارنة كل منها ، على سبيل المثال باستخدام نواة شجرة المسار الفرعي الواردة في القسم السابق. باستخدام قياسات التشابه هذه ، يمكننا أن نجد ، على سبيل المثال ، مواقع التجارة الإلكترونية والمواقع الإخبارية والمدونات والمواقع التعليمية يمكن التعرف عليها بسهولة من خلال تشابهها مع بعضها البعض.

خاتمة

في هذه المقالة ، قدمنا ​​طرقًا لمقارنة عناصر البيانات المهيكلة بالشجرة ببعضها البعض ، وأظهرنا كيفية تطبيق طرق kernel على الأشجار للحصول على قياس قابل للقياس الكمي لتشابهها. أثبتت طرق Kernel أنها اختيار ممتاز عند العمل في مساحات عالية الأبعاد ، وهو موقف شائع عند العمل مع هياكل الأشجار. مهدت هذه التقنيات الطريق لمزيد من التحليل لمجموعات كبيرة من الأشجار ، باستخدام طرق مدروسة جيدًا تعمل على مصفوفة النواة.

تتم مصادفة هياكل الشجرة في العديد من مناطق الكلمات الحقيقية مثل مستندات XML و HTML أو المركبات الكيميائية أو معالجة اللغة الطبيعية أو أنواع معينة من سلوك المستخدمين. كما هو موضح في مثال إنشاء الأشجار من HTML ، تمكننا هذه التقنيات من إجراء تحليل هادف في هذه المجالات.