Jawaban Tugas 7

Penggunaan Analisa Struktur Link pada Image Retrieval System
Senatha Cahya Christaneka, 201114398 (2005)

Beberapa penelitian pada Web Search telah mendemonstrasikan bahwa analisa struktur link sangat efektif dalam mendapatkan authoritative web pages (web page yang mengandung informasi dengan kualitas tinggi terhadap suatu topik). Informasi seperti bagaimana page berhubungan dengan page lainnya biasanya digunakan untuk menyusun algoritma searching dan dapat meningkatkan kemampuan search engine untuk merangking page berkualitas. Pembahasan Tugas Akhir ini akan menganalisa image retrieval system yang menggunakan analisa struktur hyperlink. Dasar pemikiran utama dari sistem ini adalah bahwa suatu page p akan menampilkan (atau menghubungkan ke) suatu image apabila pembuat page mempertimbangkan image tersebut akan memberikan nilai tambah kepada viewer dari page tersebut. Dengan kata lain dapat diasumsikan bahwa image yang terdapat di suatu authoritative page pada topik t merupakan kandidat yang bagus untuk image berkualitas pada topik tersebut. Gambar 1 menunjukkan contoh output image yang dihasilkan pada query ‘Tennis Player’, ‘Formula One Grand Prix’, dan ‘Frank Lampard’. Beberapa kelebihan dari image retrieval system ini adalah sebagai berikut :

1. Tidak memerlukan analisa image
2. Tidak diperlukan perubahan format query. Query yang digunakan untuk mendapatkan web page juga akan digunakan untuk mendapatkan image
3. Tidak bergantung pada nama file dan image caption yang diberikan oleh pembuat page. Hal ini memungkinkan untuk mendapatkan image yang sesuai dengan query walaupun image tersebut memiliki nama yang tidak berhubungan, seperti ‘image1‘


Secara umum input dari sistem ini berupa keyword atau kata kunci pencarian dan output dari sistem adalah image yang relevan dengan keyword tersebut. Selain itu sistem juga akan memberikan informasi tambahan tentang image tersebut, seperti urlcasal image tersebut dan ukuran image. Arsitektur sistem berupa diagram urutan proses yang dilakukan dapat dilihat pada gambar 2. Image yang terdapat pada halaman web yang relevan dengan suatu topik merupakan kandidat yang bagus untuk menjadi image berkualitas tentang topik tersebut. Oleh karena itu untuk dapat mendapatkan image yang berkualitas terhadap suatu topik sebelumnya harus didapatkan terlebih dahulu page yang relevan dengan topik tersebut. Query yang merupakan input dari user akan diteruskan ke Google untuk mendapatkan Authoritative Page melalui Google API. Authoritative page hasil dari Google API tersebut disebut sebagai root set. Proses selanjutnya adalah memperluas root set menjadi base set dengan menambahkan page yang ditunjuk (outlink) dan page yang menunjuk (inlink) page pada root set. Inlink akan didapatkan menggunakan GoogleAPI dan outlink didapatkan melalui proses parsing. Pada saat parsing juga akan didapatkan image yang terkandung pada page tersebut. Hasil dari proses ini adalah database topical page-image collection yang berisi page-page base set beserta dengan relasi antar page dan image yang terkandung didalamnya.


Proses ranking image digunakan untuk mendapatkan image dengan tingkat relevansi terbesar terhadap suatu query. Proses utama dari tahap ini adalah perhitungan nilai rangking image menggunakan metode analisa struktur link. Namun, pada tahap ini juga terdapat beberapa komponen tambahan yang berperan menilai tingkat relevansi suatu image terhadap query, yaitu proses filtering non-authoritative image berdasarkan nama file, perhitungan similarity nama file image, dan proses filtering non-authoritative berdasarkan size dari image. Terdapat tiga metode yang digunakan untuk menghitung nilai ranking image yang telah didapatkan melalui proses sebelumnya. Semua metode yang digunakan pada proses perhitungan image ini berdasarkan pada algoritma analisa struktur link, jadi tidak dilakukan analisa content dari image untuk menentukan ranking suatu image. Metode yang pertama adalah metode in-degree rank, metode yang kedua adalah metode HITS, dan metode yang ketiga adalah cocitation. Metode yang pertama menghitung ranking image dengan cara menghitung jumlah page yang menunjuk page tempat image tersebut berasal. Metode HITS menghitung ranking image dengan cara menghitung nilai hub dan authority page yang memuat page tersebut terlebih dahulu. Ranking image dengan metode ini merupakan nilai authority dari page tempat image tersebut berasal. Metode cocitation akan menghitung ranking image dengan memanfaatkan matriks cocitation. Matriks cocitation akan menunjukkan kemiripan topik antar image berdasarkan relasi antar image tersebut.
Pada image retrieval system, validasi dan evaluasi hasil sulit dilakukan, bahkan pada document-based information retrieval biasa karena sejauh ini belum ada semacam benchmark yang dapat digunakan untuk mengukur performansi sistem. Pendekatan yang digunakan untuk menguji performa sistem ini adalah dengan menggunakan pendekatan precision measurement. Pendekatan ini dilakukan dengan cara mengukur presisi image-image yang dihasilkan. Presisi image diukur dengan cara melihat berapa banyak image yang relevan dengan query dibandingkan dengan jumlah output yang dihasilkan. Masalah berikutnya yang dihadapi adalah kesulitan dalam menentukan apakah suatu image itu relevan atau tidak terhadap query user. Apabila image yang dihasilkan dapat secara jelas menggambarkan bahwa image tersebut relevan atau tidak terhadap query maka tidak akan sulit untuk menghakimi image tersebut. Namun, suatu image dapat saja dianggap relevan oleh seorang user, tetapi user lainnya juga dapat mengatakan bahwa image tersebut tidak relevan. Image ini disebut dengan image yang ambigu. Contoh image yang ambigu terhadap query ‘Car Picture’ dan ‘Frank Lampard’ dapat dilihat pada gambar 3.
Gambar 4 menunjukkan tampilan web yang digunakan untuk menampilkan image yang didapatkan. Sistem ini telah diuji coba pada 7 buah query dengan spesifikasi yang berbeda-beda. Dari hasil uji coba dapat disimpulkan hal-hal sebagai berikut :

1. Sistem ini mampu menghasilkan image yang tidak menggambarkan query user tetapi masih berhubungan erat dengan query. Image-image Desi Bebek, Untung Angsa, dan Gober Bebek dapat muncul pada hasil dari query ‘Donald Duck’ karena hubungan semua karakter tersebut dengan query sangat dekat.
2. Penggunaan metode ranking InDegree dan HITS dapat menghasilkan beberapa output image yang berasal dari satu web page yang sama. Hal ini disebabkan karena ranking image pada metode ini merupakan ranking page tempat image tersebut berasal. Jadi beberapa image pada satu halaman web dapat memiliki nilai ranking yang sama besar.
3. Penggunaan analisa struktur link tidak melakukan analisa image sama sekali jadi algoritma ini tidak akan mampu mengatasi query yang mengandung spesifikasi image seperti warna, orientasi, dan beberapa fitur spesifik lainnya. Image-image yang relevan dengan query ‘Jaguar Car’ dapat dihasilkan oleh sistem, tetapi sistem tidak akan dapat menghasilkan image ‘Red Jaguar Car’.
4. Outlink yang diambil sangat berpengaruh terhadap tingkat presisi sistem karena pada suatu web page juga terdapat link menuju page lain yang tidak memiliki kemiripan topik (non-informative link). Semakin banyak non-informative link yang dapat difilter maka semakin tinggi pula tingkat presisi sistem.