Multi-objective optimization with K-medoids clustering for Arabic multi-document summarization

Other Title(s)

تلخيص المقالات العربية متعددة الصادر باستخدام طرق التجميع و خوارزميات التحسين متعددة الأهداف

Dissertant

al-Qaysi, Rana

Thesis advisor

Qurush, Aziz
Ghanim, Wasil

University

Birzeit University

Faculty

Faculty of Engineering and Technology

Department

Department of Computer Science

University Country

Palestine (West Bank)

Degree

Master

Degree Date

2019

Arabic Abstract

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

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

يستخدم النهج المقترح خوارزمية التجميع k-medoids .

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

يتكون النظام المقترح بشكل أساسي من ثلاث خطوات تقييم الجمل، تحديد الموضوعات التي ظهرت في الوثائق، ثم استخدام خوازميات التحسين متعددة الأهداف في تقييم الجمل، تستخدم الميزات الاحصائية و السمات الدلالية لتعكس أهمية كل جملة في المقالة التي تظهر فيها، علاوة على ذلك، يتم استخدام خوارزمية التجميع k-medoids مع طريقة silhouette لتحديد الموضوعات الرئيسية التي تظهر في مجموعة المستندات الأصلية و في النهاية خوازميات التحسين متعددة الأهداف تستخدم لإنشاء ملخص يحتوي على أهم الجمل و أقصى قدر من التغطية و التنوع.

تم تقييم أداء النظام المقترح باستخدام مجموعات البيانات التالية : 2011 TAC و DUC 2002 و لقد تم مقارنة النتائج التجريبية باستخدام مقياس التقييم المعروف ROUGE، و لقد اظهرت النتائج فعالية النظام المفترح مقارنة بالانظمة المشابهة.

فلقد حصل النظام على F-measure بنسبة 8.9 17.7, 35.49, 15.89 لهذه المقاييس على التوالي Rouge-SU4, Rouge-L, Rouge, Rouge مع مجموعة 2011 TAC.

بينما حصل النظام مع بيانات 2002 DUC لنفس المقاييس على النسب التالية : 20447.17 .23.7%, 47.1%

English Abstract

Multi-document summarization is one of the most important applications of Natural Language Processing (NLP).

It aims to create a shorter version from a set of related documents with preserving the main content and overall meanings.

This will eliminate redundancy and preserve the time required to read the whole documents.

Text Summarization (TS) is either abstractive or extractive.

In extractive summarization, the summary is generated by selecting the most important sentences based on statistical and linguistic features.

In contrast, abstractive summary contains novel sentences which don’t appear in the source text.

In this thesis, we propose an extractive Arabic multi-document summarization approach that employs a clustering-based method and an evolutionary multi-objective optimization method.

The proposed approach uses the k-medoids clustering algorithm with a silhouette method to identify the main topics appearing in the original set of documents, while the optimization process tries to select the set of sentences to generate a summary that contains the most important sentences with maximum coverage and minimum redundancy.

The proposed system has mainly three steps: scoring the sentences, identifying the topics that appear in the documents, then multi-objective optimization.

In sentence scoring, both statistical features and semantic features are used to reflect the importance of each sentence in its local document.

Moreover, the k-medoids clustering algorithm with a silhouette method is used to identify the main topics appearing in the original set of documents.

Finally, the evolutionary algorithm is employed to generate a summary that contains the most important sentences with maximum coverage and diversity.

The performance of the proposed system is evaluated using TAC 2011 and DUC 2002 datasets.

The experimental results are compared using ROUGE evaluation measure, which shows the effectiveness of our system compared to other peer systems.

With TAC 2011, our system outperforms other peer systems with all ROUGE metrics, and we achieve an F-measure of 38.9%, 17.7%, 35.4%, and 15.8% for Rouge-1, Rouge-2, Rouge-L, and Rouge-SU4 respectively.

Moreover, our system with DUC 2002 dataset achieves an F-measure of 47.1%, 23.7%, 47.1%, 20.4% for Rouge-1, Rouge-2, Rouge-L, and Rouge-SU4 respectively.

Main Subjects

Information Technology and Computer Science

Topics

• Algorithms
• Arab world
• Computational linguistics
• Essays
• Natural language

No. of Pages

72

Table of Contents

• APA
• MLA
• AMA

Language

English

Data Type

Arab Theses

Record ID

BIM-957351