1.  PENDAHULUAN

NER adalah komponen dari ekstraksi informasi yang berfungsi untuk mengenali entitas nama (nama orang, lokasi,organisasi), ekspresi waktu (tanggal, waktu, durasi) dan ekspresi bilangan (uang, persen, numerik, kardinal) [1] pada kumpulan teks. Ekstraksi informasi merupakan bagian dari Natural Language Processing (NLP). Sistem ekstraksi informasi adalah sebuah proses penemuan informasi dari kumpulan dokumen atau teks berbahasa alami sebagai masukannya dan menghasilkan informasi yang berguna berupa informasi yang terstruktur dengan format tertentu. Ekstraksi informasi yang utuh harus melewati lima tahapan yaitu named entity recognition, coreference resolution, template element construction, template relation construction dan scenario template production [2].

NER yang dilakukan oleh manusia bukan hal sulit, karena banyak named entity adalah kata benda dan diawali dengan huruf kapital sehingga mudah dikenali, tetapi menjadi sulit jika akan dilakukan otomatisasi dengan menggunakan mesin. Penggunaan kamus sering kali mempermudah proses pengenalan, tetapi named entity bukan sesuatu yang statis yang akan berkembang jumlahnya sehingga dengan menggunakan kamus statis akan memiliki keterbatasan. Masalah yang sering kali muncul dalam identifikasi named entity adalah adanya semantic ambiguity [3].

NER diimplementasikan dalam banyak bidang, antara lain dalam machine translation, question-answering machine system, indexing pada information retrieval, klasifikasi dan juga dalam automatic summarization. Beberapa pendekatan yang dipakai dalam NER antara lain Rule Based, Machine Learning Based yang memanfaatkan Hidden Markov Model[4], Maximum Entropy[5], Decision Tree[6], Support Vector Machine[7], Conditional Random Fields[8] dan pendekatan Hybrid[9]. Tujuan yang diharapkan dari proses dalam NER adalah untuk melakukan ekstraksi dan klasifikasi nama ke dalam beberapa kategori dengan mengacu kepada makna yang tepat.

2.  METODE-METODE NER

METODE RULE-BASED

Grisman pada tahun 1995 mengembangkan rule-based NER dengan memanfaatkan kamus data yang terdiri dari nama negara, kota, perusahaan dan beberapa nama-nama sejenis[10]. Dengan menggunakan pendekatan rule-based pengenalan entitas dilakukan dengan mendefinisikan aturan mengenai pola-pola posisi kata anggota entitas pada sebuah frase atau kalimat. Kendala implementasi dari metode ini berada pada kemampuan definisi pola yang biasanya dilakukan oleh ahli bahasa. Rule-based NER juga memiliki ketergantungan yang besar dengan bahasa yang digunakan. Sementara itu tahun 1996, sebuah penelitian yang menggunakan pendekatan rule-based dilakukan dengan menambahkan gazetteer seperti nama organisasi, nama lokasi, title dan nama organisasi[11].

Secara umum sistem NER yang menggunakan pendekatan rule based memiliki komponen part of speech(POS) tagger, syntaks kalimat atau frase dan orthografik seperti pola kapitalisasi kata yang digabungkan dengan kamus data[12]. Pada kalimat: “Presiden Suharto memerintahkan pengamanan seluruh wilayah Kalimantan yang berpotensi diduduki oleh Malaysia.” Pada contoh tersebut sebuah kata benda nama diri (proper noun) mengikuti kata President, dan yang berupa kata yang didahului dengan huruf kapital.

Penelitian yang dilakukan oleh Appel dkk[13,14], menggunakan metode yang diberi nama FASTUS dengan memanfaatkan rule yang disusun secara manual. Proses yang dilakukan terdiri atas Recognizing Phrases, Recognizing Patterns dan Merging incidents, sementara[15] menggunakan tambahan gazetteer dan yellow pages.

 

METODE MACHINE LEARNING

Metode machine learning dalam NER digunakan untuk melakukan klasifikasi dan menggunakan model klasifikasi statistik untuk mengenali named-entity. Pada metode ini, sistem mencari patern/pola dan hubungannya pada sebuah text untuk membuat model dengan pendekatan statistik dan allgoritma machine learning. Sistem tersebut digunakan untuk mengidentifikasi dan mengklasifikasi kata benda ke dalam beberapa kelas seperti orang, lokasi, waktu[3].

Pendekatan machine learning dapat dikelompokkan ke dalam model supervised dan unsupervised. Supervised learning menggunakan pendekatan pembelajaran dengan menggunakan data yang sudah diberi label untuk menghasilkan feature dalam klasifikasi. Model ini akan menghasilkan performance yang bagus jika sistem di training dengan menggunakan data label yang berkualitas dan dalam jumlah data yang besar. Beberapa metode yang menggunakan pendekatan supervised seperti penelitian yang dilakukan oleh Bikel et. al., dengan menggunakan Hiden markov Model [16], sementara Borthwick et. al., menggunakan metode maximum entropy [17,18]. Penelitian lain menggunakan Decision Tree Model diajukan oleh Bechet et. al. [19], sementara  Wu et. al., menggunakan Support Vector Machine untuk NER[20].

Pada pendekatan unsupervised learning pembelajaran dilakukan tanpa menggunakan feedback dengan tujuan menghasilkan dan membangun representasi dari data. Representasi tersebut dapat digunakan untuk kompresi data, klasifikasi, pengambilan keputusan dan beberapa tujuan lain. Implementasi model unsupervised biasanya tidak dilakukan dengan mandiri, tetapi digabungkan dengan metode-metode lain. Pada penelitian yang dilakukan oleh Collins dkk[21] menggunakan metode unsupervised untuk NER dengan klasifikasi dengan menggunakan data pelatihan tanpa label. Keunggunaan metode ini karena patern dibangun dari proses pembelajaran maka model yang diihasilkan menjadi tidak terlalu bergantung kepada bahasa yang digunakan sehingga dapat di-port ke dalam bahasa yang berbeda[16].

Pendekatan lain yang bisa digunakan adalah Hybrid NER yang menggabungkan metode rule-based dan machine learning dengan mengambil keunggulan dari masing-masing metode yang digunakan. Penggabungan ini dilakukan oleh Mikheev dkk[22], Sirihari dkk[23] yang menggabungkan antara HMM, Maxent dan rule yang dibangun secara manual. Hasil yang diperoleh cukup baik jika dibandingkan masing-masingnya, tetapi kendala yang dihadapi masih ada pada rule yang dikembangkan secara manual.

 

                Hidden Markov Model (HMM) merupakan pengembangan model statistik dari model Markov. Model ini dikembangkan pertama kali oleh Andreyevich Markov, seorang ilmun Rusia pada awal abad 20. Model ini dipandang sebagai proses bivariatite parametric dalam waktu diskrit. Proses yang terjadi dalam HMM merupakan finite-state yang homogen dari Markov Model dan tidak dapat diamati. Proses kedua merupakan aliran variabel acak kondisional yang diberikan oleh Merkov Model. Pada saat apapun, distribusi untuk setiap variabel acak dipengaruhi oleh nilai Markov Model pada waktu tersebut saja, Oleh karena itu, HMM merupakan bagian dari statistik parametrik[24].

Dalam Markov Model biasa, setiap keadaaan dapat terlihat langsung oleh pengamat. Oleh karena itu, kemungkinan dari transisi antar kondisi menjadi satu-satunya parameter teramati. Dalam HMM, keadaan tidak terliha secara langsung, tetapi output yang tergantung terhadap keadaan tersebut terlihat. Setiap kondisi memiliki distribusi kemungkinan disetiap output yang mungkin. Oleh karena itu, urutan langkah yang dibuat oleh HMM memberikan suatu informasi tentang urutan dari keadaan. Sifat hidden menunjuk kepada kondisi langkah yang dilewai model, bukan kepada parameter dari model tersebut.

HMM dalam NER berfungsi untuk menggabungkan peluang gabungan ke pasangan observasi dan urutan label. Parameter dilatih untuk memaksimalkan kemungkinan gabungan dari himpunan pelatihan. Secara teoritis konsep yang ada dalam HMM mudah untuk diimplementasikan ke dalam kasus NER. Dari sifat HMM itu sendiri memunculkan kelemahan dimana harus semua urutan pasangan observasi harus sudah dimunculkan, sehingga menyebabkan kondisi bahwa label sekarang sangat bergantung kepada label sebelumnya. Disamping itu, HMM membutuhkan parameter dan data yang besar untuk mendapatkan performance yang baik. Pada beberapa kondisi, peluang kecil dari sebuah hasil observasi belum tentu merupakan kejadian yang tidak mungkin terjadi, hanya selalu memiliki peluang terpilih yang kecil.

                Metode maximum entropy menggunakan statistika dalam prosesnya untuk mencari distribusi p(a|b) yang akan memberikan nilai entropy maksimum. Pada [25],  maximum entropy didefinsikan sebagai rata-rata nilai informasi yang maksimum untuk suatu himpunan kejadian X dengan distribusi nilai probabilitas yang seragam. Yang dimaksud dengan distribusi nilai probabilitas seragam adalah distribusi yang menggunakan faktor ketidakpastian yang minimum atau dapat disebut sebagai distribusi yang memakai asumsi paling sedikit. Dengan menggunakan asusmsi yang minimal, maka distribusi yang didapatkan merupakan distribusi yang paling mendekati kenyataan. Pencarian distribusi probabilitas yang paling memberikan nilai entropy yang maksimum dilakukan dengan tujuan mendapatkan distribusi probabilitas terbaik yang mendekati kenyataan.

Dalam melakukan proses klasifikasi, penggunaan maximum entropy mirip dengan pendekatan Naïve Bayes, dimana dengan menggunakan metode ini akan dicari nilai conditional probability p(a|b) dari suatu kelas a jika diketahui dokumen b, untuk suatu himpunan kelas A={a1, a2, a3,…, ap} dan B={b1, b2, b3,…, bq}. Penentuan kelas a dari dokumen b akan dilihat dengan mencari nilai probabilitas p(a|b) yang maksimum dari distribusi probabilitas dengan entropy maksimum.

Dokumen pelatihan yang dimasukkan ke dalam sistem akan digunakan untuk menciptakan suatu model melalui proses yang disebut Generalized Iterative Scaling(GIS). Resolusi koreferensi pada Bahasa Inggris dengan menggunakan metode maximum entropy pernah dilakukan oleh Denis dan Baldridge. Untuk Bahasa Indonesia, Markus membandingkan metode ini dengan metode association rules dalam penelitian untuk mengenali named entity [26].

.

Untuk sejumlah fitur dan data pelatihan yang digunakan dalam penelitian, dihitung conditional probability untuk suatu keadaan (y|x) sebagai

Algoritma Generalized Iterative Scaling (GIS) digunakan untuk mencari nilai α untuk suatu fitur.

 

 

                Maximum Entropy Markov Model(MEMM) merupakan sebuah kodisional probabilistik sequence model yang mendasarkan pada prinsip maksimum entropy dimana state yang paling tidak diketahui secara pasti  dihubungkan pada Markov chain. Setiap state asal memiliki model eksponensial yang menjadikan feature yang diobservasi sebagai input dan output sebagai sebuah distribusi diantara kemungkinan state berikutnya. Keunggulan dari MEMM ini adalah kemampuan untuk menyelesaikan persoalan representasi multi feature dan longterm dependency yang menjadi masalah pada HMM.

                Metode decision tree pernah digunakan dalam menyelesaikan masalah resolusi koreferensi dalam Bahasa Inggris. Metode ini menggunakan struktur data tree dalam pegambilan keputusan. Tree dibangun dengan menggunakan algoritma C4.5 dengan menggunakan prinsip information gain, yaitu berapa banyak informasi yang benar yang dapat diperoleh dari dokumen pelatihan untuk suatu ciri tertentu. Dalam information gain ini dikenal adanya istilah entropy, yang merupakan derajat ketidakpastian dari suatu kondisi[26].

Entropy dituliskan dengan rumus:

 

H(p) = -p log2 p -(1-p)log2(1-p)

 

Sedangkan rumus dari information gain sendiri adalah sebagai berikut:

 

I = 1 –ΣH(p)

 

                Conditional Random Field (CRF) merupakan varian dari model diskriptif probabilistik yang memiliki kelebihan dari MEMM tanpa ada persoalan bias label. CRF menggunakan model undirected graph yang digunakan untuk menghitung conditional probability dari nilai pada node output yang dihasilkan untuk dijadikan sebagai node input bagi node yang lain.

Sebagai bagian dari proses yang menggunakan metode pembelajaran, secara umum menggunakan pola atau patern untuk dapat mengindentifikasi adanya named entity pada sebuah text. Salah satu yang dapat digunakan untuk mengekstrak patern yang ada pada sekumpulan text dengan menggunakan metode sequetial patern mining(SPM). Metode ini bertujuan mencari keterhubungn antar beberapa kejadian dari sequential event dan mencari urut-urutan kejadian pada sebuah sequential event. Pada pengolahan text, sequential event adalah aliran streams text yang ada pada sebuah kalimat dikaitkan dengan struktur dan pola kalimatnya.

SPM pertama kali dikemukan oleh [27]. Pendekatan yang bisa digunakan dalam penyelesaian persoalan tersebut antara lain dengan menggunakan algoritma kelompok Apriori (AprioriAll, AprioriSome, DynamicSome) dalam [28], Generalized Sequential Patern[29], SAPDE[30], Freespan [31], PrefixSpan [32], MEMISP [33] dan SPIRIT [34] yang menggabungkan dengan kemampuan regular ekspression.

Sementara itu pendekatan Hybrid menggabungkan dari model rule-based dengan machine learning. Beberapa penelitian yang dilakukan pada bahasa Inggris dan bahasa-bahasa Eropa lain menunjukkan akurasi yang cukup bagus seperti berikut :

• MaxEnt + Rule : Borthwick[5] – 92% f-measure
• MaxEnt + Rule: Edinburgh Univ.–93.39% f-measure
• MaxEnt +HMM + Rule: Srihari et al.[24]–5% f-measure

3.  PENDEKATAN NER PADA BAHASA INDONESIA

Penggunaan named entity recognition pada Bahasa Indonesia memiliki masalah dan kompleksitas yang secara umum sama dengan yang ada pada bahasa Inggris terutama jika menggunakan pendekatan machine learning. Perbedaan mendasar ada pada saat digunakan metode rule-based untuk penyelesaian ataupun menggunakan pendekatan hybrid model antara rule-based dan machine learning.

Persoalan yang sering dihadapi dalam NER anatara lain adalah tidak adanya konsistensi dari penggunaan huruf kapital, misal sebuah kata ada yang ditulis dalam huruf kapital semua maupun tanpa menggunakan huruf kapital. Hal ini menjadi masalah bagi metode-metode yang secara umum susah dibahas di atas.

Pendekatan yang diusulkan menggunakan  sequential patern mining dan natural language processing. Metode ini mengadaptasi penelitian yang dilakukan oleh [35]. Ide dasar dari usulan ini adalah menemukan linguistic patern dari data yang dimiliki untuk enghasilkan patern yang dapat digunakan untuk mengektrak patern dari sekumpulan text. Pendekatan ini akan menggunakan unsupervised learning sehingga tidak membutuhkan data berlabel untuk proses pembelajaran.

Tahapan proses dari metode yang diusulkan adalah sebagai berikut :

1. Penyiapan data untuk sequential patern mining: Pada langkah ini disiapkan kalimat-kalimat yang memiliki named entity di dalamnya untuk dapat digenerate paternnya pada setiap kemunculan entitas. Untuk menghindari banyaknya patern yang dihasilkan maka proses ekstraksi atern hanya dibatasi pada 5 kata sebelum dan sesudah kemunculan entiti.
2. Sequential Patern Mining: Pada langkah ini akan diterapkan algoritma dalam [36] yang ada pada data pembelajaran untuk menghasilkan patern yang dikehendaki.
3. Patern Maching dan Ekstrak Kandidat: Dataset untuk pengujian disiapkan untuk dilakukan pengujian kesuaian dengan patern yang dihasilkan. Hasilnya akan diurutkan sesuai dengan tingkat confidence dan supportnya.
4. Candidate Prunning: Pada tahap ini candidate entiti yang dihasilkan pada tahap sebelumnya akan disesuaikan dengan menggunakan Part of Speech Tagger(POS) untuk memastikan bahwa tipe entitas yang muncul sesuai dengan struktur yang dilakukan oleh POS. Proses ini dilakukan untuk meningkatkan akurasi dari named entity yang dihasilkan.

4.  KESIMPULAN

Dari review yang dilakukan pada beberapa metode dalam penyelesaian NER dapat diambil kesimpulan sebagai berikut :

1. Secara garis besar metode penyelesaian NER dapat dikelompokkan ke dalam metode rule based, machine learning dan hybrid.
2. Dalam metode machine learning, beberapa pendekatan yang banyak digunakan adalah HMM, Maximum Entropy, MEMM, Decision Tree dan CRF.
3. Metode hybrid yang memiliki capaian bagus antara lain maximum entropy hybrid dengan rule dan maximum entropy hybrid dengan HMM dan rule.
4. Sebagai metode usulan penyelesaian NER pada Bahasa Indonesai diusulkan penggunaan tahapan penyiapan data untuk sequential patern mining, sequential patern mining, patern maching dan ektrak kandidat serta diakhiri dengan candidate prunning.

 

DAFTAR PUSTAKA

1. Chincor, N., Brown, E., Ferro, L., dan Robinson, P., 1999, Named Entity Task Definition, Version 1.4 The MITRE Corporation and SAIC.
2. Chincor, N., Brown, E., Ferro, L., dan Robinson, P., 1998, MUC-7 Information Extraction Task Definition, The MITRE Corporation and SAIC.
3. Mansouri, L. S. Affendey, A Mamat, Named Entity Recognition Approaches, IJCSNS International Journal of Computer Science and Network Security, VOL.8 No.2, February 2008
4. Daniel M. Bikel, Scott Miller, Richard Schwartz and Ralph Weischedel. 1997 “Nymble: a highperformance learning name-finder” in the proceedings of the fifth conference on Applied natural language processing, pages 194-201, San Francisco, CA, USA Morgan Kaufmann Publishers Inc.
5. Andrew Borthwick. 1999. “Maximum Entropy Approach to Named Entity Recognition” Ph.D. thesis, New York University.
6. Hideki Isozaki. 2001. “Japanese named entity recognition based on a simple rule generator and decision tree learning” in the proceedings of the Association for Computational Linguistics, pages 306-313. India.
7. Takeuchi K. and Collier N. 2002. “Use of Support Vector Machines in extended named entity recognition” in the proceedings of the sixth Conference on Natural Language Learning (CoNLL-2002), Taipei, Taiwan, China.
8. John D. Lafferty, Andrew McCallum, and Fernando C. N. Pereira. 2001. “Conditional Random Fields:Probabilistic Models for Segmenting and Labeling Sequence Data” in the proceedings of International Conference on Machine Learning, pages 282-289, Williams College, Williamstown, MA, USA.
9. D Kaur, V Gupta, A Survey of Named Entity Recognition in English and othe Indian Language, IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 6, November 2010 ISSN (Online): 1694-0814
10. Grishman. 1995. “The NYU system for MUC-6 or Where’s the Syntax” in the proceedings of Sixth Message Understanding Conference (MUC-6) , pages 167-195, Fairfax, Virginia.
11. Wakao T., Gaizauskas R. and Wilks Y. 1996. “Evaluation of an algorithm for the Recognition and Classification of Proper Names”, in the proceedings of COLING-96.
12. Budi, S. Bressan, "Association Rules Mining for Name Entity Recognition", Proceedings of the Fourth International Conference on Web Information Systems Engineering, 2003.
13. Appelt, and et. al., “SRI International FASTUS system MUC-6 test results and analysis”, Proceedings of the MUC-6, NIST, Morgan-Kaufmann Publisher, Columbia, 1995.
14. Appelt, and et. al., “FASTUS: A finite state processor for information extraction from real-world text”, Proceedings of IJCAI, 1993.
15. Iwanska, M. Croll, T. Yoon, and M. Adams, “Wayne state university: Description of the UNO processing system as used for MUC-6”, In Proc. of the MUC-6, NIST, Morgan-Kaufmann Publishers, Columbia, 1995.
16. M. Bikel, S. Miller, R. Schwartz, R, Weischedel, "a High-Performance Learning Name-finder", fifth conference on applied natural language processing, PP 194-201, 1998.
17. Borthwick, J. Sterling, E, Agichtein, and R. Grishman, “Exploiting diverse knowledge sources via maximum entropy in named entity recognition”, Proceedings of the Sixth workshop on Very Large Corpora, Montreal, Canada, 1998.
18. Borthwick, J. Sterling, E. Agichtein and R. Grishman, "NYU: Description of the MENE Named Entity System as Used in MUC-7", In Proceedings of the Seventh Message Understanding Conference (MUC-7), 1998.
19. Bechet, A. Nasr and F. Genet, "Tagging Unknown Proper Names Using Decision Trees", In proceedings of the 38th Annual Meeting of the Association for Computational Linguistics, 2000.
20. C. Wu, T.K. Fan, Y.S. Lee, S.J Yen, “Extracting Named Entities Using Support Vector Machines", Spring-Verlag, Berlin Heidelberg, 2006.
21. Collins, Michael and Y. Singer. "Unsupervised models for named entity classification", In proceedings of the Joint SIGDAT Conference on Empirical Methods in Natural Language Processing and Very Large Corpora, 1999.
22. Mikheev, C. Grover, M. Moens, "Description OF THE LTG SYSTEM FOR MUC-7", In Proceedings of the seventh Message Understanding Conference (MUC-7), 1998
23. Sirhari, C. Niu, W. Li, "A Hybrid Approach for Named Entity and Sub-Type Tagging" Proceedings of the sixth conference on Applied natural language processing ,Acm Pp. 247 - 254 , 2000.
24. Charles L. Wayne. 1991., “A snapshot of two DARPA speech and Natural Language Programs” in the proceedings of workshop on Speech and Natural Languages, pages 103-404, Pacific Grove, California. Association for Computational Linguistics.
25. MacKay, DJC (2003) Information theory, inference and learning algorithms, Cambridge University Press.
26. Chris Manning and Hinrich Schütze, 1999, Foundations of Statistical Natural Language Processing, MIT Press. Cambridge.
27. Agrawal, R. and Srikant, R. 1994. Fast algorithms for mining association rules. In Proc. 20th Int. Conf. Very Large Data Bases, VLDB, J. B. Bocca, M. Jarke, and C. Zaniolo, Eds. Morgan Kaufmann.
28. Agrawal, R. and Srikant, R. 1995. Mining sequential patterns. In Eleventh International Conference on Data Engineering, P. S. Yu and A. S. P. Chen, Eds. IEEE Computer Society Press, Taipei, Taiwan.
29. Srikant, R. and Agrawal, R. 1996. Mining sequential patterns: Generalizations and performance improvements. In Proc. 5th Int. Conf. Extending Database Technology, EDBT, P. M. G. Apers, M. Bouzeghoub, and G. Gardarin, Eds. Vol. 1057. Springer-Verlag.
30. Zaki, M. J. 2001. SPADE: An e±cient algorithm for mining frequent sequences. Machine Learning 42.
31. Han, J. and Kamber, M. 2000. Data Mining Concepts and Techniques. Morgan Kanufmann.
32. Pei, J., Han, J., Pinto, H., Chen, Q., Dayal, U., and Hsu, M. C. 2001. Pre¯xspan: Mining sequential patterns e±ciently by pre¯x-projected pattern growth. Int. Conf. on Data Engineering.
33. Lin, M.-Y. and Lee, S.-Y. 2002. Fast discovery of sequential patterns by memory indexing. In Proc. of 2002 DaWaK.
34. Garofalakis, M. N., Rastogi, R., and Shim, K. 1999. Spirit: Sequential pattern mining with regular expression constraints. In VLDB'99, Proceedings of 25th International Conference on Very Large Data Bases, September 7-10, 1999, Edinburgh, Scotland, UK, M. P. Atkinson, M. E. Orlowska, P. Valduriez, S. B. Zdonik, and M. L. Brodie, Eds. Morgan Kaufmann
35. X Ding, 2011,” Opinion and Entity Mining on Web Content”, Disertation on University of Illionois Chicago, USA
36. Jiawei Han and Micheline Kamber., 2006, Data Mining: Concepts and Techniques, 2nd ed. Morgan Kaufmann Publishers, March