تشخیص موجودیت‌های نام‌دار در متن

`**به نام یگانه نام‌دار عالم**
# چکیده
موجودیت‌های نام‌دار در زبان به مجموعه‌ای از اسامی مانند نام افراد،  سازمان‌ها، مکان‌ها،  و... می‌باشد. شناسایی موجودیت‌های نام‌دار در متن  مسئله پیدا کردن این موجودیت‌ها از متن خام و همچنین شناسایی نوع موجودیت  است.

برای مثال: آدولف بورن، طراح، کاریکاتوریست و نقاش در شهر بودجویس از جمهوری چک به دنیا آمد.

> آدولف B-PERSON بورن I-PERSON ، کاریکاتوریست و نقاش در شهر بودجویس B-LOCATION از جمهوری B-LOCATION چک I-LOCATION به دنیا آمد .

در این پژوهش روش‌های تضحیص خودکار موجودیت‌های نام‌دار در متن معرفی  شده و یکی از آن‌ها برای زبان فارسی پیاده‌سازی و آزمایش خواهد شد.

#  مقدمه

**مسئله چیست؟**
موجودیت‌های نام‌دار عبارتند از کلماتی که در جهان واقع مصداق و عینیت دارند. به طور مثال میتوانند یک شخص مثل ابوعلی سینا باشد و یا نام یک مکان مثل شهر تهران.
به طور دقیق‌تر:
> به کلمه و یا عبارتی گفته می‌شود که برای ارجاع به نمونه‌های یک مقوله‌ی مشخص مانند شخص، شرکت یا مؤسسه، تاریخ، بیماری، گونه‌ای باکتری و سایر بکار می رود. [4]

اما مسئله این است که موجودیت‌های نام‌دار از یک سند الکترونیکی به صورت خودکار توسط ماشین بیرون کشیده شوند و در دسته‌های معنایی موردنظر و مربوط به خودشان قرار داده شوند. البته این که سیستم چه نوع موجودیتی را تشخیص دهد و یا به بیان دیگر دسته‌های معنایی مورد نظرش چه باشند بستگی به زمینه کاربردی سیستم دارد.

**چه کاربردهایی دارد؟**
حجم فراوان اطلاعات موجود در اسناد الکترونیکی بر روی صفحات وب می‌تواند پاسخگوی بسیاری از سوالاتی که در هر زمینه‌ای پرسیده می‌شوند باشد. تشخیص و گروه‌بندی موجودیت‌های نام‌دار با کمک به تسریع و دقیق‌تر کردن جستجوهای معنادار، ترجمه ی خودکار مفاهیم متن، کشف ارجاعات در متن و بسیاری دیگر از زمینه‌های مربوط به پردازش زبان‌های طبیعی، ما را در ارزیابی اطلاعات و یافتن پاسخ سؤالات پرسیده شده یاری می رساند.[4]

#  کارهای مرتبط
در دیگر کارهای انجام شده در این زمینه؛بیشتر روش‌های آماری به عنوان روش اصلی استفاده شده‌اند و روش‌های دیگر به صورت مکمل و جهت بهبود نتیجه بکار رفته‌اند. در ذیل به معرفی مختصر این روش‌ها می‌پردازیم.

**روش‌های آماری:**
در این روش هدف تخمین‌زدن احتمال وقوع a  با محتوای b است ((P(a,b) . که محتوا در مسائل مربوط به پردازش زبان طبیعی کلمات است که بستگی به نوع مسئله می‌تواند یک کلمه یا عبارتی چندکلمه‌ای باشد.
ابتدا با متن هایی که به وسیله‌ی انسان به شیوه‌ی شروع – داخل – خارج برچسب‌گذاری شده‌اند، ماشین را آموزش می‌دهیم. با یادگیری از طریق این داده‌ها ماشین به تشخیص خودکار موجودیت‌های نام‌دار در متن می‌پردازد.

مثالی از یک جمله برچسب‌زده شده توسط روش شروع-داخل-خارج:

    American Airlines, a unit of AMR Corp., immediately matched the move, spokesman Tim Wagner said.
    American          B-ORG
    Airlines          I-ORG
    a                 O
    unit              O
    of                O
    AMR               B-ORG
    Corp              I-ORG
    .                 O
    immediately       O
    matched           O
    the               O
    move              O
    spokesman         O
    Tim               B-PERS
    Wagner            I-PERS
    said              O
    .                 O

برای یادگیری ماشین از متن‌های ورودی از راه‌های مختلفی استفاده می‌شود، از جمله روش پنهان مارکوف، روش به‌هم‌ریختگی بیشینه و روش CRFs .

**روش‌های بر مبنای قاعده:**
در این روش موجودیت های اسمی را با استفاده از مؤلفه هایی که در ظاهر این عبارات ممکن است موجود باشد تشخیص میدهند. برای مثال در زبان انگلیسی 
دو حرف بزرگ در مجاور هم احتمالا یک اسم خواهد بود و یا عباراتی که در آن ها کلمات و یا حروفی از قبیل Dr. ویا Mr.  شروع میگردد و یا به حروفی از قبیل MD خاتمه می یابد احتمالا اسم یک شخص خواهد بود. (NER-Report) 
یکی از راه های بدست آوردن قواعد در کلمات و یا جملات استفاده از عبارات با قاعده است. عبارات با قاعده به ما کمک میکند تا  موجودیت هایی که ساختاری ثابت و منظم دارند تشخیص داده شوند.  به طور مثال عبارت باقاعده ی زیر را می توان برای تشخیص ایمیل استفاده کرد:

    [`A-Za-z0-9](([_\.\-]?[a-zA-Z0-9]+)*)@([A-Za-z0-9]+)(([\.\-]?[a-zA-Z0-9]+)*)\.([A-Za-z]{2,})`

تاریخ شماره تلفن کدپستی از جمله دیگر مواردی هستند که با این روش میتوان آن ها را تشخیص داد.

**روش مبتنی بر مدل پنهان مارکوف:**
مدل پنهان مارکوف در ریاضی به شکل زیر تعریف می شود:
   
    λ = (A, B, π)
A: پارامتر نشان دهنده احتمال انتقال بین دو وضعیت
B: احتمال انتشار
π:احتمال شروع با هر  وضعیت
در این روش که یکی از روش های آماری است ابتدا با استفاده از فرمول ها و الگوریتم هایی که در ادامه معرفی می شوند پارامترهای معرفی شده در تعریف این روش را بدست می آوریم. سپس با استفاده از الگوریتم ویتربی  ترتیبی از برچسب گذاری ها را با بالاترین احتمال تولید میکنیم.

مراحل استفاده از روش مدل پنهان مارکوف:

1. آماده سازی داده های از قبل برچسب گذاری شده:در این گام  متنی به عنوان نمونه به وسیله انسان برچسب گذاری میشود.
2. محاسبه پارامترهای این مدل:

start probability(π) = (Number of sentences start with particular tag)/(Total number of sentences in corpus)
Input: Annotated Text File
Output: Start Probability vector
Algorithm:
	for each starting tag
			find frequency of that tag as starting tag
	calculate π

Transition probability(A) = (Total number of sequences from Ti to Tj)/(Total number of Ti)
Input: Annotated  text file
Output: Transition probability matrix
Algorithm:
	For each tag in states(Ti)
			For each other tag in states(Tj)
						Find frequency of tag sequence Ti Tj
			Calculate A
		
Emission probability(B) = (Total number of occurrence of  word as a tag)/(Total occurrence of that tag)
Input: Annotated Text file
Output: Emission probability matrix
Algorithm:
For each unique word Wi in Annotated corpus
	Find frequency of word Wi as a particular tag Ti
	Divide frequency by frequency of that tag Ti
	
3. حال پارامترهای بدست آمده را با الگوریتم ویتربی روی متنی که میخواهیم پردازش شود اعمال میکنیم و برچسب گذاری منطبق بر موجودیت ها را بدست می آوریم.
 
**الگوریتم ویتربی:**
فرض کنید یک سری حالت داریم که وضعیت آن ها نامعلوم است. این الگوریتم با کمک گرفتن از پارامترهای بدست آمده از مدل پنهان مارکوف محتمل ترین ترتیب از وضعیت ها را برای این سری از حالات ارایه میدهد. به این صورت که با در نظر گرفتن یک گراف و داشتن احتمال انتقال بین گره ها که همان پارامترهای مارکوف هستند تگ هر کلمه وضعیت گرهی است که به هنگام بررسی آن کلمه در آن گره قرار داریم. اول متن با گره شروع در گراف آغاز میشود. بنابر احتمالات آغازین به گره بعدی میرویم. کلمه اول و گره کنونی را بررسی کرده یک تگ پیشنهاد میشود. بعد به گره بعدی رفته و با کلمه بعد آن را بررسی میکنیم. 

#  آزمایش‌ها

روش انتخاب شده در این پروژه استفاده از روش های مبتنی بر قاعده و مدل مارکوف به همراه هم هست. که ابتدا هر یک را به صورت جدا گانه پیاده سازی کرده و سپس آن ها را ترکیب می کنیم.
پیاده سازی آزمایش های مختلف این پروژه در آدرس زیر قرار گرفته است:
[پروژه تشخیص موجودیت های نامدار در متن فارسی](https://github.com/Mohammad-Eslahi-Sani/Farsi-Named-Entity-Recognition)

**آزمایش اول: استفاده از روشهای ساده**
*مراحل تئوری:*
+ کلمات دریافتی را به فعل و اسم و حرف دسته بندی میکنیم؛ اسم ها را برای مرحله بعد کاندید میکنیم.
+ قواعد از پیش طراحی شده را به روی اسامی اعمال میکنیم؛ برای تعدادی از اسم ها تگ پیشنهاد خواهد شد.
+ با مطابقت دادن اسامی با آموزه های قبلی ماشین تگ های بیشتری برای اسامی پیشنهاد می شوند.
+ تمامی تگ ها ذخیره و نمایش داده میشوند تا در مراحل بعدی تصمیم بگیریم که چگونه تگ بهتر را تشخیص بدهیم.

**مرحله اول:**
برای این مرحله از ماژول هضم استفاده میکنیم. جمله ای را از ورودی گرفته و آن را تگ گذاری میکنیم.

	#! -- encoding: utf-8
    from __future__ import unicode_literals
    from hazm import *
    
    normalizer = Normalizer()
    out_file = open('out.txt','w')
    s = 'این یک متن فارسی است. که به سختی پردازش می شود.'
    out_file.write('\n')
    out_file.write(s.encode('utf8'))
    out_file.write('\n')
    s = normalizer.normalize(s)
    tagger = POSTagger(model='resources/postagger.model')
    a = tagger.tag(word_tokenize(s))
    for i in a:
    	for j in i:
    		out_file.write(j.encode('utf8'))
    		out_file.write('\t')
    	out_file.write('\n')
    in_file.close()
    out_file.close()
پاسخ بدست آمده در فایل خروجی به شکل زیر است:
این یک متن فارسی است. که به سختی پردازش می شود.
 

		    این PRO	
		    یک NUM	
    متن      Ne	
    فارسی      N	
    است      V	
    .      PUNC	
    که      CONJ	
    به      P	
    سختی      N	
    پردازش      N	
    می‌شود      V	
    .      PUNC

بدین ترتیب جمله ورودی تگ گذاری می شود و جملاتی که تگ آن ها N است برای مرحله بعد کاندید میشوند.

**مرحله دوم:**
قواعدی را طراحی میکنیم سپس به روی اسامی اعمال میکنیم.

**آزمایش دوم: مدل پنهان مارکوف ٰ**
**مرحله اول:**
با استفاده از یک متن که از قبل تگ گذاری شده و الگوریتمی که در قسمت توضیح روش مدل پنهان مارکوف آمد پارامترهای مارکوف را بدست می آوریم.
**مرحله دوم:**
الگوریتم ویتربی روی متن اعمال شده و برای هر کلمه تگی پیشنهاد میشود.

**آزمایش سوم: استفاده ترتیبی از روش های مبتنی بر قاعده و مدل مارکوف**
در این آزمایش ابتدا با استفاده از قواعد که در آزمایش اول توضیح داده شدند یک مجموعه پیشنهادی تگ گذاری برای متن داده میشود. سپس در استفاده از مدل مارکوف این تگ ها را در نظر میگیرم. به این صورت که در برخورد با کلماتی که از قبل تگ گذاری شده اند به گره مربوط به آن ها پرش کرده و از مارکوف برای بررسی کلمه بعدی و رفتن به گره بعدی استفاده میکنیم.

#  کارهای آینده
**استفاده ترکیبی از روش های مبتنی برقاعده و مدل مارکوف**
 برای بهبود و افزایش کارایی میتوان قواعد را به عنوان گره به گراف حاصل از مدل مارکوف اضافه کرد.. در این صورت با مشاهده این قواعد به گره مربوط به آن ها رفته  و سپس با بررسی احتمالات برای کلمات تگ پیشنهاد می شود.
استفاده از دیکشنری جامع تر و قوانین دقیق تر و بیشتر نتایج کار را بهبود می بخشند.

#  مراجع

1.  Jurafsky, Daniel, and James H. Martin. 2009. Speech and Language  Processing: An Introduction to Natural Language Processing, Speech  Recognition, and Computational Linguistics. 2nd edition. Prentice-Hall.
2.  Nadeau, David, and Satoshi Sekine. "A survey of named entity  recognition and classification." Lingvisticae Investigationes 30.1  (2007): 3-26.
3.  M. Asgari Bidhendi, et al., "Extracting person names from ancient  Islamic Arabic texts", in Proceedings of LREC-Rel, pp. 1-6, 2012.
4.  پونه سادات مرتضوی، مهرنوش شمس فرد، "شناسایی موجودیت های نام دار در  متون فارسی"، پانزدهمین کنفرانس بین المللی سالانه انجمن کامپیوتر ایران،  1388
5. شهناز پناهی, فرهاد عابدینی, "روشی جدید برای استخراج موجودیت های نام دار", اولین همایش منطقه ای رویکرد های نوین در مهندسی کامپیوتر و فناوری اطلاعات, ۱۳۹۰

#  پیوندهای مفید

+ [تشخیص موجودیت‌های نام‌دار، پروژه درس هوش مصنوعی نیمسال دوم ۸۹-۸۸ دانشگاه علم و صنعت](http://bayanbox.ir/id/6189680504542343855?download)
+ [تشخیص موجودیت‌های اسمی در متن، پروژه درس هوش مصنوعی نیمسال اول ۹۲-۹۱ دانشگاه علم و صنعت](http://bayanbox.ir/id/1685090304266467232?download)
+ [سیستم شناسایی و طبقه بندی اسامی در متون فارسی](http://www.sid.ir/FA/VEWSSID/J_pdf/35213891306.pdf)
+ [پردازش زبان فارسی در پایتون](http://www.sobhe.ir/hazm)
+ [کتابخانه ابزار یادگیری ماشین برای پایتون](http://scikit-learn.org/stable/)
+ [Named Entity Recognition with NLTK](http://nltk.org/book/ch07.html#named_entity_recognition_index_term)
+ [Stanford Named Entity Recognizer(NER)](http://nlp.stanford.edu/software/CRF-NER.shtml)