Geri Dön

Multi̇-document summarization using distortion-rate ratio

Bozulum-hız oranına göre çoklu metin özetinin çıkarılması

PDF İndir

  1. Tez No: 353807
  2. Yazar: ULUKBEK ATTOKUROV
  3. Danışmanlar: PROF. DR. ULUĞ BAYAZIT
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2014
  8. Dil: İngilizce
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 97

Özet

Günümüzde internet ortamında verilerin büyük oranda artması bilgi erişimini zorlaştırmaktadır. Internete erişimi olan herkes metin, görsel ya da işitsel dosyalar yükleyebilir, blog ya da web sitesi oluşturabilir. Dolayısıyla çeşitli türden dokümanlar internet aracılığıyla sanal dünyaya yayınlanmakta ve bilgi kapsitesini arttırmaktadır. Örneğin, Google arama motorunun son iki yılda endekslediği web sitelerinin sayısı 30 milyarı aşmış durumdadır. Büyük miktarda verilerin arasından gerekli olanlarını bulmak ve en uygununu seçmek zordur. Bazen belli bir konu üzerinde belge araması yaptığımızda arama motorları milyonlarca sonuç üretebilmektedir. İnsanın fizyolojik kapasitesi ve zamanı sınırlı olduğundan milyonlarca dokümanlar üzerinden geçmesi ve uygun olanını seçmesi imkansız ya da zaman alıcıdır. Yukarıda anlattığımız sorunların üstesinden gelmenin bir yolu doküman özetinin çıkarılmasından geçmektedir. Sanal ortamda bulunan dokümanların büyük bir kısmı metin olduğundan metin özetinin çıkarılması çok sık olarak kullanılan ve araştırılan konulardan bir tanesidir. Metin özeti orijinal dokümanda anlatılan esas konuları kapsar ve onunla ilgili detayları içerir. Metin özeti orijinal dokümanın kullanıcının bilgi ihtiyaçlarını karşılayıp karşılamadığını kısa sürede belirlemesine yardımcı olur. Tek dokümanın özetini çıkarma yönteminde giriş olarak bir doküman kullanılır. Çoklu doküman özetlemesinde birden fazla dokümanın özeti çıkarılır. Özetleme sistemleri genel ve sorguya dayalı olarak da ikiye ayrılır. Genel özetler orijinal dokümanla ilgili esas konuları ve onlarla ilgili detayları içerir. Sorguya dayalı özetler ise aranan sorguya uygun bilgileri içerir. Kullanıcı sorgusu özetin oluşturulmasında izlenmesi gereken esas kural olarak kullanılır. Özetleme sistemleri çıkarımsal ya da soyutlayıcı özetleme sistemleri olarak sınıflandırılır. Çıkarımsal özetlemede önemli bilgi kapsayan cümleler seçilerek özet oluşturulur ve cümleler üzerinde hiç bir değişiklik yapılmadan özetleme yapılır. Soyutlayıcı özetleme sistemlerinde ise mevcut sistemler üzerinde değişiklik yapılır ya da yeni cümleler oluşturulur. Bu yüzden soyutlayıcı özetleme sistemleri çıkarımsal özetleme sistemlerine göre karmaşık işlemler gerektirir. Çoklu metin özetleme sistemlerinde esas amaç bilgi tekrarlanmasının önlenmesidir. Giriş olarak kullanılan dokümanlar aynı konu hakkında yazıldığından benzer metin birimleri(cümleler, paragraflar vb.) doküman kümesi boyunca sık olarak kullanılırlar. Tekrarlanan metin birimleri önemli konuları belirlediği gibi özetlerde eklendikleri zaman bilgi tekrarına yol açarlar. Böyle durumların önlenmesı için benzer metin birimlerinin belirlenmesi ve onların özette çok sayıda tekrarlanmasının önlenmesi gerekir. Bilgi tekrarının önlenmesi için bir kaç yöntem geliştirilmesine rağmen bu alanda araştırmalar günümüzde de devam etmektedir. Aynı problem bu bitirme çalışmasında da ele alınmıştır. Bu çalışmada ağaç budama algoritmasının(Optımal Tree Prunıng algorıthm) HAC(Hierarchical Agglomerative Clustering) algoritması ile beraber kullanımı araştırılmıştır. HAC algoritması tekrarlanan metin birimlerinin ayıklanmasında ve ağaç budama algoritması tekrarlanan metin birimlerinin özet metinde azaltılmasında kullanılmıştır. Orijinal dokümanlar cümlelere ayrıştırıldıktan sonra cümleler HAC algoritması aracılığıyla demetlere atanır. Benzer cümleler aynı demette yer alır. HAC algoritması ağaç yapısında demetler oluşturduğundan cümleler ağacın yapraklarında yer alır. Her bir düğümde temsilci cümleler saklanır. Her bir düğüm için temsilci cümle atanır ve temsilci cümle alt ağacın yapraklarında yer alan cümleleri temsil eder. Ağacın kök düğümünde tüm cümleleri temsil eden temsilci cümle saklanır. Tekrarlanan metin birimlerinin elimine edilmesi için ağaç budama algoritması kullanılır. Ağaç budama algoritmasının kullanılması için bozulum(distortion) ve hız(rate) parametrelerinin belirlenmesi gerekir. Bir cümle temsilci cümle ile temsil edildiği zaman bilgi kaybına uğradığından bozulum ortaya çıkar. Bozulum bir cümle temsilci cümle ile temsil edildiği zaman ortaya çıkan bilgi kaybı oranını gösterir. Hız ise özeti oluşturmak için kullanılan cümle, kelime ya da harf sayısını gösterir. İki vektör arasındaki aralık bozulum ölçütü olarak kullanılabilir. İki vektör arasındaki aralığı ölçmek için benzerlik katsayıları kullanılabilir. Kosinüs benzerlik katsayısı en yaygın olarak kullanılan benzerlik katsayılarından bir tanesidir. Kosinüs katsayısı hesaplamaları kolaylaştırdığı gibi bazı problemleri de ortaya çıkarır. Kosinüs katsayısı iki vektörde de yer alan benzer kelimelerin sayısı ve sırasına göre iki vektörün benzerliğini değerlendirir. Dolayısıyla cümlelerin anlamsal benzerliği göz ardı edilir. Gizli Anlamsal Analiz metodu kelimeler ya da cümleler arasındaki ilişkilerin belirlenmesi için kullanılabilir. Bu yöntem kelimelerin beraber kullanılma istatistiklerine dayanmaktadır. Benzer konuların anlatılmasında benzer kelimeler ve belli kalıplar kullanılır. Benzer kelimelerin ve kalıpların belirlenmesi metin parçası içindeki anlamsal ilişkilerin belirlenmesine yardımcı olur. Kelimelerin başka kelimeler ile olan ilişkilerine ya da kalıplar içerisinde kullanımına bakılarak ağırlıklandırılması metin birimlerinin benzerliklerinin belirlenmesinde önemli rol oynar. Ağaç budama algoritması bozulumu minimize eden ve hızı azaltan alt ağaçları elimine eder. Ağacın yaprak düğümlerinden kök düğümüne doğru ilerledikçe bozulum da artış izlenir ama veri sayısı azalır. Yaprak düğümlerinde bozulum sıfıra eşitken ağacın kök düğümünde en büyük değerine ulaşır. Bu yüzden mevcut alt ağaçların içinden bozulum ve veri sayısı oranını minimize eden alt ağaç budanır. Özetleme 4 aşamadan oluşmaktadır. Birinci aşamada metin ön işlemesi yapılır, metin cümlelere ayrıştırılır ve cümleler vektör olarak gösterilir. Kelimenin kökünün bulunmasından kelime - cümle matrisinin oluşturulmasına kadar olan işlemler bu aşamada yapılır. Ikinci aşamada ise tekrarlanan metin birimlerini belirlemek için cümlelerin demetlenmesi yapılır ve benzer cümleler aynı demetlere atanır. HAC algoritması ağaç yapısında veri yapısı ürettiğinden cümleler HAC ağacında saklanır. Bir birine benzeyen cümleler aynı alt ağacın yaprak düğümlerinde yer alır. Benzerlik ölçütü olarak kosinüs benzerlik katsayısı kullanılır. Aynı cümlelerün benzerlik katsayısı bire eşittir, ama birbirine tamamen benzemeyen cümlelerin benzerlik katsayı derecesi sıfıra eşittir. Üçüncü aşamada ise tekrarlanan metin birimleri elimine edilir. Bir önceki aşamada elde edilen ağaç üzerinde ağaç budama işlemi gerçekleştirilir. Her bir budama iterasyonunda bozulum ve veri sayısı parametrelerine göre alt ağaçlar budanır. Alt ağaçlar benzer cümleleri kapsadığından budama sonucu benzer cümleler temsilci cümleyle değiştirilmiş olur. Dolayısıyla bilgi tekrarlanması problemi giderilmiş olur. Budama işlemi cümle sayısına ya da bozulum değerinme göre durdurulabilir. Iterasyonun durdurulması için hangi parametrenin kullanılacağı sistemin özelliklerine göre ayarlanır. Dördüncü aşamada ise özet oluşturulur. Özet oluşturmak için bir önceki aşama sonrası elde edilen alt ağaç kullanılır. Alt ağacın yaprak düğümlerinde yer alan cümleler kullanılarak özet oluşturulur. Özet ise yaprak düğümlerde yer alan cümlelerin hepsinden oluşturulabilir ya da cümle seçme algoritmalarından yararlanılarak cümlelerden bazıları seçilebilir. Sistem performansı ROUGE paketi kullanılarak değerlendirilmiştir. ROUGE paketi model ve sistem özetlerini birbirine karşılaştırır. Sistemin performansı DUC-2002 veri seti kullanılarak test edilmiştir. DUC-2002 veri seti Data Understanding Conferance isimli konferans için hazırlanmıştır. Veri seti konferansa gönderilen sistemlerin test edilmesi için kullanılmıştır. Veri seti 59 dokümandan oluşmuş ve dokümanlar 4 sınıfa atanmıştır. Her bir doküman seti 200 ve 400 kelimeden oluşan soyut ve çıkarımsal örnek özetleri de içermektedir. Örnek özetler konferans tarafından hazırlanmıştır. Çıkarımsal özetler 400 kelimelik uzunluktaki özetle, soyut özet ise 200 kelimelik özetle karşılaştırılmıştır. Örnek özette bulunan cümlelerden çok sayıda kapsayan ve sistem tarafından üretilen özet başarılı özet olarak kabul edilmiştir. Önerilen sistemin değerlendirilmesinde iki test senaryosu izlenmiştir. Birinci senaryoda 200 kelimelik soyut özet kullanılmıştır. Sistem tarafından üretilen özet(aday özet) 200 kelimeden oluşan örnek özetle karşılaştırılmıştır. Sistemin performansını değerlendirmek için Rouge-1 Precision, Rouge-1 Recall, Rouge-1 F1 ölçütleri kullanılmıştır. Rouge-1 kullanıldığında iki özet(aday ve örnek özetler) kelime bazında değerlendirilmiş olur. Rouge-1 Recall değeri aday özetin örnek özette bulunan kelimeleri ne kadar içerdiğini gösterir. Bu yüzden Rouge -1 Recall değeri aday özet ile örnek özet arasındaki benzerlik oranını gösterir. İkinci senaryoda ise 400 kelimelik örnek özet kullanılmıştır. Sistem performansı aday ve örnek özette bulunan cümleler bazında değerlendirilmiştir. Sentence Recall ve Sentence Precision ölçütleri aracılığı ile sistem performansı ya da özet içeriği değerlendirilmiştir. Sentence Recall aday özette bulunan örnek özet cümleleri sayısının toplam örnek özet cümle sayısına göre oranını gösterir. Sentence Presicion ise aday özette bulunan örnek özet cümlelerinin toplam özet cümle sayısına göre oranını belirler. DUC-2002 konferansında en iyi sonuç gösteren sistemlere göre önerilen sistem performansının daha başarılı olduğu tespit edilmiştir. Bir sonraki araştırmada ise önerilen sistem soyut özetlerin oluşturulması için kullanılacaktır.

Özet (Çeviri)

The present thesis investigates distortion-rate ratio in the context of multi-document summarization. The multi-document summarization is considered as a data compression task. Optimal Tree Pruning algorithm introduced by Breiman et al. and extended by Chou et al. is adapted to multi-document summarization. The main issue in the multi-document task is redundancy. The input documents discuss the similar topics and thus contain repeated information about them. To avoid the inclusion of the repeated information in the summary, the redundant information have to be detected and eliminated. Hierarchical Agglomerative Clustering algorithm is used to detect the redundancy in the documents. This algorithm is chosen, since it yields a binary tree that is used in the optimal tree pruning algorithm. Optimal tree pruning algorithm is employed to reduce the redundancy. An optimal tree that trades off distortion and rate is produced after the pruning. Distortion reflects the semantic loss in the meaning of a sentence if the sentence is represented by another sentence. Thus distortion is adopted as distance between an original sentence and a sentence that represents it. Rate means the amount of information used to present an initial document in a condensed form. Hence, rate is defined to be the number of the sentences included in the document. l function, which is the ratio of distortion and rate, is used to determine a sub-tree to be pruned off. A sub-tree yielding the minimal l value is eliminated, since l value evaluates increase in distortion for decrease in rate. In each iteration of the pruning, a sub-tree with the minimal l value is eliminated. The iteration may be stopped when the sufficient number of the sentences are left in the leaf nodes of the tree. In addition, the iteration can be stopped if distortion reaches to a predetermined threshold or the l value exceeds an optimal value. After pruning step, sentence selection algorithms can be employed to include appropriate sentences in the summary. The proposed system is tested using DUC-2002 data set and evaluated using ROUGE package. The performance of the system is compared with the best systems of DUC-2002 and with the extract based summaries provided by DUC-2002.

Benzer Tezler

  1. Tez No

    371824

    Multi-document summarization using dependency grammars

    Bağımsal dilbilgisi kullanarak çoklu doküman özetleme

    ŞAZİYE BETÜL BİLGİN

    Yüksek Lisans

    İngilizce

    İngilizce

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. ARZUCAN ÖZGÜR TÜRKMEN

  2. Tez No

    442543

    Özgün paragraf tabanlı çıkarım tekniği kullanarak otomatik çoklu doküman özetleme

    Automatic multi-document summarization using original paragraph based extraction technique

    METİN TURAN

    Doktora

    Türkçe

    Türkçe

    2015

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYıldız Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. AHMET COŞKUN SÖNMEZ

  3. Tez No

    252925

    Language independent multi document summarization using latent semantic indexing/clustering techniques

    Saklı anlam indeksleme ve kümeleme teknikleri ile dilden bağımsız çoklu doküman özetleme

    SUAT ALİM

    Yüksek Lisans

    İngilizce

    İngilizce

    2009

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolÇankaya Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ABDÜL KADİR GÖRÜR

  4. Tez No

    470041

    Enhancing feature selection with contextual relatedness filtering using Wikipedia

    Wikipedia yolu ile bağlamsal ilişki filtrelemesi kullanarak geliştirilmiş özellik seçme

    MELİH BAYDAR

    Yüksek Lisans

    İngilizce

    İngilizce

    2017

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı

    PROF. FAZLI CAN

  5. Tez No

    459415

    Machine learning methods in natural language processing

    Doğal dil işlemede makine öğrenmesi yöntemleri

    BETÜL GÜVENÇ

    Yüksek Lisans

    İngilizce

    İngilizce

    2016

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi Üniversitesi

    Hesaplamalı Bilimler ve Mühendislik Ana Bilim Dalı

    YRD. DOÇ. DR. FATİH ECEVİT

Geri Dön