Simple Entity Extraction from News Article in Bahasa Indonesia

Tulisan kali ini membahas cara mengekstrak informasi dari teks berita menggunakan python. Entitas yang dimaksud adalah entitas berupa tempat, orang, organisasi atau entitas lain yang diketahui dalam basis pengetahuan. Basis pengetahuan yang dipakai dalam tulisan ini adalah dbpedia bahasa Indonesia. Sebetulnya DBPedia sudah menyediakan layanan semacam ini yaitu Spotlight namun sayangnya belum tersedia dalam bahasa Indonesia.

DBPedia merupakan bentuk terstruktur dari Wikipedia. Istilah terstruktur di sini dimaksudkan adalah bentuk yang memiliki susunan baku yaitu tripel (subjek, predikat, objek) yang digunakan dalam RDF (resource definition format) sebagai komponen dasar web semantik. Antarmuka SPARQL digunakan untuk mengakses informasi yang ada dalam dbpedia.

Dalam melakukan proses ekstraksi entitas, program yang akan dibahas akan menggunakan layanan web untuk melakukan pengolahan bahasa alami. Layanan web yang akan digunakan adalah pebahasa yang dipasang di AppEngine. Fungsi yang digunakan dalam layanan web tsb adalah pelabelan (tagging) kelas kata (part of speech).

perlu dicatat bahwa cara yang dibahas di tulisan ini merupakan salah satu cara yang cukup sederhana. Hal yang ingin ditunjukkan di sini adalah bagaimana mengkombinasikan beberapa layanan web untuk menjalankan fungsi baru yang juga bisa dijadikan layanan web(mashup). Program ini dibuat dalam python namun sebetulnya tidak banyak kebergantungan sehingga memungkinkan ditranslasi dalam javascript sehingga dapat dijalankan di dalam peramban. Mungkin lain kesempatan saya akan buat translasinya.

Adapun tahapan dalam melakukan ekstraksi entitas dalam tulisan ini antara lain :

1. preproses

   dalam tahapan praproses, teks didekomposisi menjadi kalimat dan kalimat didekomposisi menjadi kata dan tanda baca. Selanjutnya setiap kata dan tanda baca akan diberi tanda (tag) sesuai dengan kelas kata tsb. Misalkan jika suatu kata adalah kata kerja maka kata tersebut akan diberi tanda VBI/VBT.

2. ekstraksi kata benda

   Tahapan selanjutnya adalah memilih kelompok kata yang merupakan kata benda (noun). Dalam proses sebelumnya, kata benda ditandai dengan tanda NN atau NNP. Deretan kata yang merupakan kata benda digabung menjadi satu kelompok kata.

3. penyaringan kandidat

   Hasil ekstraksi kata benda di tahapan sebelumnya masih menghasilkan kata-kata yang bersifat umum. Sedangkan entitas yang ingin diekstrak merupakan kata yang khusus merujuk ke nama benda tertentu (misal nama orang, nama tempat, dsb.). Oleh sebab itu hasil kandidat dalam tahap sebelumnya masih perlu disaring lebih lanjut. Penyaringan dilakukan menggunakan asumsi bahwa penulisan entitas dalam berita biasanya ditulis dengan huruf kapital di huruf pertama. Selain itu hasil dari tahapan sebelumnya bisa jadi menghasilkan kata yang terlalu panjang dan sebetulnya terdiri dari beberapa entitas sekaligus. Hal ini tidak diatasi sepenuhnya dan hanya diproses dengan asumsi adanya petunjuk dari kemunculan salah satu entitas di dalam gabungan ini yang berdiri sendiri pada kalimat yang lain.

4. look-up dalam basis data

   Setelah kandidat entitas diseleksi, Selanjutnya dilakukan kueri dalam basis pengetahuan. Properti yang dijadikan acuan adalah rdfs:label dan dalam kueri ini digunakan penyaringan melalui filter regex yang tersedia dalam SPARQL. kueri yang digunakan adalah sbb:

   SELECT DISTINCT ?ent, ?lbl WHERE { 
   ?ent rdfs:label ?lbl. 
   FILTER(regex(?lbl, "%s", "i"))
   } 
   LIMIT 10

   %s dalam kueri di atas akan diganti dengan nama entitas dari daftar kandidat entitas. Silakan coba kueri tersebut di dbpedia.

5. disambiguasi

   Hasil kueri pada tahapan sebelumnya bisa kosong, beberapa entitas yang merujuk ke objek yang sama, atau beberapa entitas yang namanya mirip. Kasus kosong dapat diabaikan dengan menghapus kandidat entitas. Kasus beberapa objek yang sama dapat dengan mudah dipilih salah satu. Sedangkan jika hasil kueri menghasilkan beberapa entitas yang namanya mirip maka perlu dilakukan pemilihan diantara hasil tsb. Pemilihan yang cukup sederhana dilakukan dengan menggunakan perbandingan string yang salah satu contohnya adalah edit distance/levenshtein. Alternatif entitas lalu diurutkan berdasarkan kemiripan (nilai jarak perbedaan kecil ke besar). Terakhir dilakukan pemeriksaan, apakah perbedaannya lebih besar dari panjang string asal? Jika ya maka bisa jadi kedua entitas tersebut tidak sama.

Percobaan dilakukan dengan contoh teks dari situs berita kompas.

Sumber artikel: http://internasional.kompas.com/read/2014/02/20/2108578/PM.Yingluck.Shinawatra.Bantah.Lakukan.Korupsi

Perdana Menteri Thailand Yingluck Shinawatra mengeluarkan pernyataan berisi sanggahan dakwaan korupsi terkait penerapkan skema pembelian beras dari para petani.

Yingluck yang berusaha menghindari pengunjuk rasa yang mengepung gedung-gedung pemerintah dalam beberapa hari terakhir, mengatakan ia bertanggung jawab atas kebijakan itu.

Tetapi ia mengatakan tidak bertanggung jawab atas pelaksanaan skema subsidi beras itu. Para petani juga ikut melakukan unjuk rasa menuntut pembayaran pemerintah yang tertunda.

Komisi antikorupsi mengangkat dakwaan itu di tengah tuntutan pengunjuk rasa agar pemerintah mengundurkan diri.

Sementara itu, penentang Yingluck, sebagian besar di Bangkok dan Thailand selatan, mengatakan pemerintah dikontrol oleh abang Yingluck, Thaksin Shinawatra, perdana menteri yang digulingkan. Thaksin mendapatkan dukungan kuat di daerah pedesaan Thailand utara.

Pengunjuk rasa antipemerintah melanjutkan demonstrasi menuntut Yingluck mundur dengan memblokade kantor-kantor bisnis keluarganya, kata wartawan BBC di Bangkok, Jonathan Head.

Yingluck sendiri menuduh komisi antikorupsi terburu-buru melakukan penyelidikan dan mengeluarkan dakwaan dengan apa yang ia katakan berpihak kepada mereka yang ingin menggulingkan pemerintah.

Anggota partai Yingluck lain menuduh badan-badan negara juga berpihak.

Wartawan BBC Jonathan Head melaporkan para penentang percaya dengan terus melakukan tekanan dan mengangkat kasus hukum, Yingluck pada akhirnya akan mengundurkan diri dan menyerahkan kekuasaan kepada pemimpin sementara.

dari teks ini didapatkan beberapa entitas:

{
  "Yingluck": [
    "http://id.dbpedia.org/resource/Yingluck_Shinawatra", 
    "http://id.dbpedia.org/resource/Yingluck_shinawatra"
  ], 
  "Bangkok": [
    "http://id.dbpedia.org/resource/Bangkok", 
    "http://id.dbpedia.org/resource/Kategori:Bangkok"
  ], 
  "Yingluck Shinawatra": [
    "http://id.dbpedia.org/resource/Yingluck_Shinawatra", 
    "http://id.dbpedia.org/resource/Yingluck_shinawatra"
  ], 
  "Thaksin Shinawatra": [
    "http://id.dbpedia.org/resource/Thaksin_Shinawatra", 
    "http://id.dbpedia.org/resource/Thaksin_shinawatra", 
    "http://data.nytimes.com/N58340366665839459753"
  ], 
  "Thailand selatan": [
    "http://id.dbpedia.org/resource/Krisis_Thailand_Selatan", 
    "http://id.dbpedia.org/resource/Krisis_thailand_selatan"
  ]
}

Kode lebih lengkap ada di gist berikut:

	"""
	author: Peb Ruswono Aryan
	date: 20.02.2014
	Simple Entity Resolution
	read a text file (news) and resolve entities mentioned in the text
	uses:
	- external Part-of-Speech Tagger API (REST)
	- Entity knowledge base over SPARQL with Regex filter
	"""
	import json
	import requests
	import sys
	def levenshtein(a,b):
	"""Calculates the Levenshtein distance between a and b.
	http://hetland.org/coding/python/levenshtein.py"""
	n, m = len(a), len(b)
	if n > m:
	# Make sure n <= m, to use O(min(n,m)) space
	a,b = b,a
	n,m = m,n
	current = range(n+1)
	for i in range(1,m+1):
	previous, current = current, [i]+[0]*n
	for j in range(1,n+1):
	add, delete = previous[j]+1, current[j-1]+1
	change = previous[j-1]
	if a[j-1] != b[i-1]:
	change = change + 1
	current[j] = min(add, delete, change)
	return current[n]
	def run_sparql(host, query, format="application/json", filename=""):
	params={
	"query": query,
	"debug": "on",
	"timeout": "",
	"format": format,
	}
	r = requests.post(host, params=params)
	if r.status_code==requests.codes.ok:
	return r.json()
	else:
	raise Exception("SPARQL Error")
	def remote_tag(url, txt):
	params={
	"teks": txt,
	"task": "postag"
	}
	r = requests.post(url, data=params)
	if r.status_code==requests.codes.ok:
	return r.text.split("\n")
	else:
	print r.status_code
	return r.content
	if __name__ == "__main__":
	NLP = "http://nlp.pebbie.net&quot;
	ENDPOINT = "http://id.dbpedia.org/sparql&quot;
	if len(sys.argv)>1:
	#read from file
	with open(sys.argv[1]) as f: txt = f.read()
	#use web service to do pos tagging
	sent = remote_tag(NLP+'/handler', txt)
	#extract nouns & proper nouns
	c_entities = []
	buffer = []
	stat = "non_ent"
	for s in sent:
	tmp = [tuple(term.split("/")) for term in s.split(" ")]
	for lex, tag in tmp:
	if stat == "non_ent":
	if tag in ["NN", "NNP"]:
	buffer.append(lex)
	stat = "ent"
	elif stat == "ent":
	if tag in ["NN", "NNP"]:
	buffer.append(lex)
	else:
	chunk = " ".join(buffer)
	if chunk not in c_entities:
	c_entities.append(chunk)
	buffer = []
	stat = "non_ent"
	first_capital = lambda s: len(s)>1 and s[0]==s[0].upper()
	#first filtering based on capitalized first character
	cap_filter = True
	if cap_filter:
	output = []
	for ent in c_entities:
	if any([first_capital(w) for w in ent.split()]):
	output.append(ent)
	c_entities = output
	#print c_entities
	#print
	#second filtering based on subword split ["A B C D", "C", "C D"] -> ["A B", "C D", "C"]
	sub_filter = True
	if sub_filter:
	output = []
	is_sub = {}
	for ent in c_entities:
	sub = [e for e in c_entities if e != ent and ent in e]
	if len(sub)==0 and ent not in output:
	output.append(ent)
	else:
	is_sub[ent] = sub
	for ent, sub in is_sub.items():
	for esub in sub:
	if esub in output:
	output.remove(esub)
	epos = esub.index(ent)
	first = esub[:epos]
	rest = esub[epos:]
	if first not in output:
	if first_capital(first) or not cap_filter:
	output.append(first)
	if rest not in output:
	if first_capital(rest) or not cap_filter:
	output.append(rest)
	c_entities = output
	#print c_entities
	#resolve to knowledge base via SPARQL (e.g. dbpedia)
	output = {}
	for entity in c_entities:
	try:
	result = run_sparql(ENDPOINT, """Select distinct ?ent, ?lbl where { ?ent rdfs:label ?lbl. filter(regex(?lbl, "%s", "i"))} LIMIT 10""" % entity)
	candidate = []
	print "resolving \"%s\"..." % entity
	#print result["results"]["bindings"]
	for cand in result["results"]["bindings"]:
	cand_pair = (cand["ent"]["value"], cand["lbl"]["value"])
	if cand_pair not in candidate: candidate.append(cand_pair)
	if len(candidate)>0:
	output[entity] = candidate
	finally:
	pass
	c_entities = output
	#choose best match using string matching (e.g. levenshtein)
	output = {}
	for entity, candidates in c_entities.items():
	ename = entity.lower().replace("_","").replace(" ","")
	#prepare candidates
	tmp = {}
	for iri, label in candidates:
	kname = label.lower().replace("_","").replace(" ","")
	if kname not in tmp:
	tmp[kname] = [iri]
	else:
	tmp[kname].append(iri)
	if len(tmp.keys())==1:
	#accept if there's only one alternative
	output[entity] = tmp.values()[0]
	else:
	#sort ascending by distance
	sorted_candidates = sorted([(kname, levenshtein(kname, ename)) for kname in tmp.keys()], key=lambda x:x[1])
	#accept if computed distance is less than original string length
	if sorted_candidates[0][1] <= len(entity):
	output[entity] = tmp[sorted_candidates[0][0]]
	c_entities = output
	print json.dumps(c_entities, indent=2)

view raw entity_resolution.py hosted with ❤ by GitHub