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

`به نام یگانه نام‌دار عالم

چکیده

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

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

آدولف 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

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

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

آزمایش‌ها

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

آزمایش اول: استفاده از روشهای ساده
مراحل تئوری:

  • کلمات دریافتی را به فعل و اسم و حرف دسته بندی میکنیم؛ اسم ها را برای مرحله بعد کاندید میکنیم.

  • قواعد از پیش طراحی شده را به روی اسامی اعمال میکنیم؛ برای تعدادی از اسم ها تگ پیشنهاد خواهد شد.

  • با مطابقت دادن اسامی با آموزه های قبلی ماشین تگ های بیشتری برای اسامی پیشنهاد می شوند.

  • تمامی تگ ها ذخیره و نمایش داده میشوند تا در مراحل بعدی تصمیم بگیریم که چگونه تگ بهتر را تشخیص بدهیم.

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

#! -- 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. شهناز پناهی, فرهاد عابدینی, "روشی جدید برای استخراج موجودیت های نام دار", اولین همایش منطقه ای رویکرد های نوین در مهندسی کامپیوتر و فناوری اطلاعات, ۱۳۹۰

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

وحید خرازی

سلام
پژوهشنامه‌ شما در این فاز خوب است. لطفا به موارد زیر دقت کنید:

  • از نظر نگارشی در متون علمی، بهتر است از حذف فعل به قرینه استفاده نکنید. مثلا :. به طور مثال میتوانند یک شخص مثل ابوعلی سینا باشد و یا نام یک مکان مثل شهر تهران.

  • کاربردهای موضوع، می‌توانست مفصل‌تر توضیح داده شود.

  • مرجع قبل از نقطه‌ی پایانی جمله شماره‌گذاری می‌شود. مثلا: می‌رفتند[1].

  • توضیح روش‌ها گنگ است. لطفا در فاز بعدی روش‌ها به تفصیل توضیح داده شوند.

  • لطفا مرتب بنویسید.

  • روش بر مبنای قاعده، چه تفاوتی با روش برمبنای عبارات با قاعده دارد. لطفا در صورت وجود تفاوت توضیح دهید و در غیر این‌صورت ادغام کنید.

  • در فازهای بعد بر روی یافتن موجودیت‌های نام‌دار در زبان فارسی هم تحقیق کنید.

  • مراجع بسیار کم است. لطفا از مراجع جدیدتر و بیشتری استفاده کنید.
    موفق باشید

تایید شده

با سلام و خسته نباشید

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

با تشکر

وحید خرازی

سلام
انتظار ما در این فاز پیاده سازی کامل یک روش و توضیح چند روش بوده است. امیدواریم برای فاز نهایی پروژه‌ی خود، چند روش را توضیح دهید و حداقل یک روش را تا انتها پیاده سازی(در گیت‌هاب) کنید. اگر نیاز به راهنمایی و کمک بیشتری برای انجام پروژه داشتید به بنده(vahid@kharazi.net) ایمیل بزنید.
موفق باشید

تایید شده

با سلام و خسته باشید

  • توضیحات پروژه به غیر از قسمت کارهای مرتبط واضح و گویا نیست و می توان گفت در نگارش آن دقت نشده است.

  • در روش مارکوف ارائه ی شبه کد لازم به نظر نمی رسید و می توانستید برای توضیحات بیشتر فقط لینکی برای آن قرار دهید.

  • بعد از پیاده سازی نتایج بیان نشده است و خواننده نمی تواند بفهمد که برنامه واقعا چقدر صحیح و درست کار می کند.

وحید خرازی

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