Managing genetic algorithm parameters to improve SegGen a thematic segmentation algorithm

Abstract

Son yıllarda kullanılabilir metin veritabanı sayısında ciddi bir artış meydana gelmiştir. Buna bağlı olarak, bilgi edinme alanında etkili araştırma yöntemlerine duyulan ihtiyaç da artmıştır. Ayrıca ilgili bilgiye erişimde etkinlik ve kullanıcıların bilgi ihtiyacına doyurucu yanıtlar verilmesi günümüzde arama sistemi seçiminde önem kazanmaktadır. Anlamsal bölümleme, yazılı metni Salton?un yaptığı tanımda geçen kriterlere göre anlamlı homojen parçacıklara ayırma süreci olarak tanımlanabilir. Bu tanıma göre bir metnin anlamsal olarak bölümlenmesi onu parçalara ayırmak demektir. Bu işlemde bölümlerin iç bütünlüğü ve birbirine komşu bölümler arasındaki farklılıklar hat safhadadır. Bu tanıma göre otomatik metin bölümlenmesi, bu kriterlere uygun bir belge içerisinde sınırları belirleyerek belli başlı tematik ayrımların tayin edilmesi şeklinde anlaşılabilir. SegGen, SPEA'nın bir varyantı üzerine şekillendirilmiş bir anlamsal bölümleme algoritmasıdır. Bu algoritma ile hedeflenen, Salton'un bölümleme tanımına dair iki kriterin optimize edilmesidir. Kriterler ise bir bölümün ait olduğu metnin kendi içinde maksimum bütünlüğe sahip olması ve komşu bölümlerle arasında minimum benzerlik olması şeklindedir. Bu tez çalışmasında, elde edilen popülasyonların niteliğinin evrimine göre genetik algoritma parametrelerinin ayarlanması suretiyle SegGen yaklaşımı üzerinde uygulanan birtakım gelişmeler anlatılmaktadır. Parametre ayarları iki farklı nedene dayandırılmış ve uygulanmıştır. Birinci nedene göre; popülasyonun niteliğine ilişkin genel kriterlere göre değerlendirme yapılabileceğinden elde edilen popülasyonların genel niteliği, süreç ilerledikçe artar ve parametrelere değer koymak ve arama sürecinde gücü artırırken çeşitlilik faktörlerini azaltan yeni operatörler tanımlamak mantıklı görünmeye başlar. Diğer nedene göre ise; popülasyonlar içerisindeki öğeler makul metin bölümleri olduğundan mevcut bölümler içerisindeki cümlelere, optimizasyonu söz konusu iki kriterde gömülü cümleler arasındaki benzerliklerin analizi açısından, bağlı bulundukları sınırlara olan uzaklıklarına göre değer yüklemek gerekir.

Due to the remarkable increase in the number of available text databases in last decades, the need for efficient searching methods has become a major challenge for information retrieval. Thematic segmentation can be defined as the process of separating written texts into meaningful homogeneous units according to the criteria stated in Salton?s definition which states that thematic segmentation of a text is its splitting into segments such that the internal cohesion of segments and the dissimilarity between adjacent segments are maximum. SegGen is a linear thematic segmentation algorithm grounded on a variant of the SPEA and aims at optimizing the two criteria of the Salton's definition of segments: a segment is a part of text whose internal cohesion and dissimilarity with its adjacent segments are maximal. This thesis describes improvements that have been implemented in the approach taken by SegGen by tuning the genetic algorithm parameters according with the evolution of the quality of the generated populations. Two kinds of reasons originate the tuning of the parameters. The first one rests on autonomous search, which consists in modifying the parameters and operators of the genetic algorithm along with the increasing quality of the generated population through the generations. The second one is also to consider the increasing of quality of the population as the process evolves, but to do so considering that the nature of the coding of individuals which in this case are segmentation instances represented by binary vectors corresponding to the positions of the boundaries of the segmentations.