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

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

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

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

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

* این پروژه توسط یک بنگاه تجاری تعریف شده است و اگر به خوبی انجام شود، مورد حمایت قرار می‌گیرد.

# مقدمه
موجودیتهای نامدار در متن به عباراتی گفته می شود که حاوی اسامی اشخاص، سازمانها و یا مکانها باشند[1].در سامانه های تشخیص موجودیتهای اسمی عمومی بیشتر به سمت پیدا نمودن اسامی اشخاص، مکانها و سازمانهایی که در یک متن معمولی خبری ذکر شده است، تمرکز می شود.اولین مرحله در اغلب کاربردهای استخراج اطلاعات از متن [^ Information Extraction]، تشخیص و دسته بندی موجودیتهای نامدار در یک متن است. به این عملیات تشخیص موجودیتهای نامدار [^Named – Entity Recognition(NER)] اطلاق میشود[2].
 در واقع مساله تشخیص موجودیت های نامدار در متن عموما به دو زیر مساله تشخیص و دسته بندی موجودیت ها تقسیم می شود :
  1.اسامی خاصی که تشخیص داده می شوند. 
  2.قالبی که برای دسته بندی آنها به کار میرود که وابسته به نوع کاربرد آن خواهد بود. 

نیاز به شناسایی موجودیتهای نامدار، در دنیای امروز که عصر ارتباطات و اطلاعات است رو به رشد میباشد. شناسایی موجودیتهای نامدار برای جستجوهای معنادار، ترجمه ی خودکار، استخراج خودکار مفاهیم متن، کشف ارجاعات درمتن و بسیاری دیگر از زمینه های مربوط به پردازش زبان های طبیعی[^Natural Language Processing] کاربرد دارد[3].کاربردهای دیگری برای تشخیص موجودیت های نامدار تعریف گردیده است:

+ طبقه بندی متون [^Text categorization] : یک سیستم طبقه بندی کننده می تواند به جای اینکه ویژگی های خود را از کل متن  استخراج کند ابتدا توسط NER  اسامی را از متن استخراج کرده و سپس طبقه بندی را بر اساس این اسامی انجام دهد.استفاده از NER  دقت طبقه بندی را تا حد قابل توجیهی افزایش می دهد.
+ سیستم پرسش و پاسخ [^Question Answering] : پاسخ بسیاری از سوالات یک متن مانند کی؟ کجا؟چه زمانی؟ چه مقدار ؟ و ... در اسامی حاضر در متن قرار دارد که می توان آنها را توسط یک سیستم NER  از متن استخراج کرد.
+ خلاصه سازی متون[^Text Summarization] :داده های به دست آمده از یک سیستم NER شامل اطلاعات کلی از یک متن می باشد که در خلاصه سازی متون بسیار مفید است.
+ بهینه کردن جستجو: زمانی که ما یک کلمه را جستجو می کنیم با توجه به فرم و نقش آن نتایج متفاوتی به دست می آید .به طور مثال اگر "استاد یوسفی " را جستجو کنیم منظورمان اسم شخص است و نتایجی مانند "خیابان استاد یوسفی" که اسم مکان است غیرمفید هستند.[11]

# کارهای مرتبط
در زیر ویژگی هایی که در اغلب سیستم های تشخیص موجودیت های اسمی استفاده می شود را مرور می کنیم. این ویژگی ها را می توان به سه قسمت تقسیم کرد: 1- ویژگی های کلمه ای 2- ویژگی های فهرستی 3- ویژگی های سندی

1- ویژگی های کلمه ای:
این ویژگی ها مربوط به نویسه های سازنده ی کلمه است و از روی شکل وظاهر خود کلمه استخراج می گردد . این ویژگی ها توصیف گر حالت کلمه ، نقش کلمه ، حالت عددی و مانند آن است. ویژگی های زیر از این دسته اند [4]:
+ ویژگی هایی که مربوط به بزرگ یا کوچک بودن حروف در کلمه است ، مانند :1- شروع کلمه با حروف بزرگ 2- بزرگ بودن تمام حروف در کلمه 3- وجود حروف بزرگ در وسط کلمه مثل eBay
+ ویژگی های عددی کلمات مانند : الگوی اعداد به کار رفته(استفاده از 2 یا 4 عدد جهت نمایش تاریخ و مانند آن )
+ ویژگی های نویسه ی کلمات مانند : 1- ضمیر اول شخص 2- ضمیر ملکی 3- حروف یونانی
+ ویژگی های صرفی کلمات کانند : 1- پسوند 2- پیشوند 3-ریشه ی کلمات
و ...

2- ویژگی های فهرستی
یک سری دیگر از ویژگی هایی که برای کلمات یک جمله در سیستم های NER در نظر گرفته می شود ، ویژگی هاییست که از یک سری فهرست ها استخراج می گردد ؛ برای استخراج این ویژگی ها از فهرست هایی که شامل اسامی افراد ، مکان ها ، شهرها ، کشورها ، افراد و ... است استفاده می شود. وجود کلمه در هر یک از این فهرست ها ، نشان دهنده ی یکی از ویژگی های کلمه است .  بزرگ بودن این فهرست ها باعث می شود تا ویژگی هایی با دقت بالاتری استخراج گردد؛ اما در بسیار ی از موارد ، محدودیت وجود دارد که نمی توان از فهرست هایی بزرگ استفاده کرد . به همین دلیل از یک سری روش ها در جستجو استفاده می شود تا فهرست ها بتوانند تعداد کلمات بیشتری پوشش دهند [4].

3- ویژگی های سندی
این ویژگی ها مربوط به اطلاعاتی ازکلمه است که در کل سند وجو دارد . این اطلاعات از طریق پردازش کل اسناد به دست می آید . واضح است که اگر حجم اسناد و داد های ما زیاد باشد ، ویژگی های قوی تری استخراج می گردد.ویژگی های سندی ، ماورای ساختار کلمه است در واع از یک بررسی آماری از کل سند به دست می آید در ادامه چند نوع از این ویژگی ها رابررسی می کنیم:
+ وجود چند شکل از کلمه در سند : اگر یک کلمه در یک سند به چند شکل مختلف ظاهر شود ، مانند : boy و Boy آن گاه می توان نتیجه گرفت که شکل های دیگر کلمه مربوط به مسائل دیگری همچون شروع جمله است ، با استفاده از این نوع ویژگی می توان تا حدی از این ابهامات جلوگیری کرد .
+ ویژگی محلی : تعداد تکرار در متن یا پاراگراف ، موقعیت کلمه در متن یا پاراگراف
.
.
.
برای تشخیص موجودیت های نامدار چندین روش وجود دارد :

1. روش تشخیص موجودیتهای اسمی بر مبنای قواعد
در روش برمبنای قواعد[^Rule – Based] سعی میشود قالب و شکل کلی موجودیتهای اسمی را به صورت یک عبارت باقاعده نمایش داده شده تا سامانه اسامی خاص را بر مبنای این عبارات تشخیص دهد.
برای مثال در زبان انگلیسی دو حرف بزرگ مجاور هم احتمالا یک اسم خواهد بود و یا عباراتی که در آنها کلمات و یا حروفی از قبیل Dr,Mr. و ...شروع می شود یا به حروفی از قبیل MD خاتمه می یابد احتمالا اسم یک شخص خواهدبود . شکل ظاهری بعضی از موجودیتهای اسمی را میتوان به صورت یک عبارات باقاعده نمایش داد. برای مثال نشانی ایمیل را می توان به صورت عبارت باقاعده ی زیر نوشت[6]:
$$[A-Za-z0-9](([_\.\-]?[a-zA-Z0-9]+)*)@([A-Za-z0-9]+)(([\.\-]?[a-zA-Z0-9]+)*)\.([A-Za-z]{2,})$$

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

+ روشهای مبتنی بر واژه نامه
در این روش ها از واژه نامه هایی که در آن موجودیت ها و نوع آن ها در یک زمینه خاص ذکر شده است استفاده می شود و پس از پیدا کردن یک واژه در یک مقوله خاص از واژه نامه مربوط به آن مقوله استفاده می شود. در بسیاری از کاربردها، به نسبت ساده تر میباشد که یک لیست از موجودیتهای اسمی و نوع آنها تهیه شده و  موجودیتهای اسمی داخل متن با استفاده از این لیست تشخیص داده شود. برای مثال: اسامی مکانها در فرهنگهای جغرافیایی  که شامل میلیونها اسم مکان به همراه مشخصات جغرافیایی آن میباشد به عنوان یک واژه نامه مناسب برای تشخیص اسامی مکانها قابل استفاده است.معمولا واژهنامه میتواند در کنار روشهای تشخیص آماری برای بهبود تشخیص کلماتی که با روشهای آماری به سختی مشخص میشوند، به کار می رود .
تهیه و به روز نگهداری این واژه نامه ها با صرف هزینه و زمان بسیار زیادی ممکن می شود و موضوع دیگری که این مشکل را بسیار بزرگتر و وخیم تر می کند این است که واژه نامه ها برای هر زبان باید به طور جداگانه استفاده شوند بنابر این هزینه بسیار بالا تر می شود. مشکل دیگر این روش این است که ممکن است کلمه اختصاری که نشان دهنده یک سرکلمه مانند هما است به جای اینکه هواپیمایی ملی ایران برگردانده شود به عنوان اسم یک شخص برگردانده شود[7].

+ روشهای آماری
این روشها غالباً به عنوان روشهای اصلی جهت تشخیص اسامی خاص شناخته میشوند و سایر روشها به عنوان مکمل در کنار آن مورد استفاده قرار میگیرند.خیلی از مسائل در پردازش زبان های طبیعی را میتوان به صورت مساله های پردازش طبیعی زبان بیان کرد، یعنی بیان احتمال وقوع حالت "الف" با محتوای "ب" که در مساله ما محتوا کلمات یا عبارات هستند[8] .
در این روش ابتدا سامانه به وسیله ی پیکره ای از داده های آموزشی که به صورت دستی و به وسیله ی انسان برچسب گذاری[^labelling] شده اند آموزش دیده، با یادگیری از طریق این داده ها به تشخیص خودکار اسامی خاص در متن می پردازد، که در بخش ویژگی های سندی اشاره شد.
برای برچسب زنی داده ی آموزشی از روش برچسبزنی شروع-داخل- خارج  [^BIO tagging] استفاده میشود. در این روش، برای تشخیص موجودیتهای اسمی، کلمات متن را تک تک برچسب زنی می نماییم[1].
در این سیستم یک متن ،به عنوان ورودی به سیستم ارائه می شود و اسامی به تفکیک طبقه ی مربوط به آن به عنوان خروجی سیستم به دست می آید . مراحل لازم جهت شناسایی و طبقه بندی اسامی یک متن عبارتند از :
1- یک متن به عنوان ورودی به سیستم ارائه می شود ، مانند جمله ی : " محمد جمعه به دانشگاه نرفت ."
2- با استفاده از یک نشان گذار ، کلمات در متن ورودی از هم دیگر جدا می شوند. (محمد/جمعه /به/ دانشگاه /نرفت)
3- با استفاده از برچسب زن دستوری نقش دستوری هر کلمه مشخص می شود(محمد/اسم| جمعه/اسم| به /حرف| دانشگاه/اسم| نرفت/فعل)
4- یا استفاده از برچسب دستوری کلمات ، اسامی شناسایی شده و از بقیه ی کلمات متن جدا می شوند .(محمد/جمعه/دانشگاه)
5-برای هر یک از اسامی بردار ویژگی لازم استخراج می شود.
6- با استفاده از یک دسته بند آماری ، اسامی در طبقات مربوطه طبقه بندی می شوند .
.
*طبقه بندی با روش های زیر صورت می گیرد :

+ [مدل پنهان مارکوف](http://en.wikipedia.org/wiki/Hidden_Markov_model)
مدلهای پنهان مارکوف[^Hidden Markov Model] یکی از قویترین ابزارها برای پردازش سیگنالها میباشند. انواع مختلف مدلهای پنهان مارکوف علیرغم محدودیتهایی که دارند، هنوز پراستفاده ترین تکنیک در سیستمهای مدرن بازشناسی گفتار و تشخیص متون هستند. مدل پنهان مارکوف، کل الگوی ورودی را به عنوان یک بردار ویژگی تکی مدل نمیکند، بلکه رابطه بین بخشهای متوالی یک الگو را استخراج میکند، زیرا هر بخش نسبت به کل ورودی کوچکتر و بنابراین مدلسازی آن ساده تر است[9] .

+ [طبقه کننده نایو بیز](http://fa.wikipedia.org/wiki/دسته‌بندی_کننده_نایو_بیز)
به طور ساده روش بیز روشی برای دسته بندی پدیده‌ها، بر پایه احتمال وقوع یا عدم وقوع یک پدیده‌است. براساس ویژگی‌های ذاتی احتمال(به ویژه اشتراک احتمال) نایو بیز [^Naive Bayes classifier] با دریافت تمرین اولیه نتایج خوبی ارایه خواهد کرد. تمرین دادن نایو بیز یک تمرین بانظارت [^ Supervised learning]  است.
برای نمونه یک میوه ممکن است پرتغال باشد. اگر نارنجی و کروی با شعاع حدود ده سانتی متر باشد. اگر این احتمالات به درستی به همدیگر وابسته باشند نایو بیز در تخشیص اینکه این میوه پرتغال است یا نه بدرستی عمل خواهد کرد.. با وجود مسایل طراحی و پیش فرض‌هایی که در خصوص روش بیز وجود دارد، این روش برای طبقه بندی کردن بیشتر مسایل در جهان واقعی، مناسب است.

+ [میدان تصادفی شرطی ](http://blog.echen.me/2012/01/03/introduction-to-conditional-random-fields/)
  مدل میدان تصادفی شرطی[^(CRF)Conditional Random Fields]  بیشتر برای تشخیص الگو[^pattern recognition] و آموزش ماشین[^machine learning] به کار گزفته میشود . به خصوص در کارهایی چون برچسب زنی و پارس کردن [^parsing] در نتیجه برای مساله ما که از دسته ی مسائل برچسب زنیست بسیار مناسب می باشد . ایده ی کلی آن برچسب زنی با توجه به برچسبهای همسایه است . مثلا در مساله ما برای انتخاب برچسب یک توکن برچسبهای توکن های قبلی را نیز مد نظرر قرار می دهیم.سال های اخیر سیستم های تشخیص واستخراج خودکار واحدهای اسمی به یکی از محدوده های پر طرفدار تحقیقاتی تبدیل شده است. این سیستم ها را می توان به سه دسته تقسیم بندی کرد: 
1-روش های مبتنی بر قوانین که به صورت دستی مشخص شده اند [^Hand-made Rule-based approaches] 
2- سیستم ها ی مبتنی بر یادگیری ماشینی[^ Machine Learning -base approaches] 
3- سیستم های که ترکیبی از دو روش قبل هستند.[10]

سیستمهای توسعه یافته بر پایه یادگیری برای NERC به سه دسته تقسیم میشوند :
1.یادگیری با نظارت[^Supervised Learning] : یادگیری با نظارت، نیاز به حجم زیادی از متون حاشیه نویسی شده است و از تکنیک هایی نظیر درخت تصمیم گیری و مدل استفاده می کند. این روش مناسب برای مدل مخفی مارکوف[^Hidden Markov Model] و سیستمهای وابسته به دامنه است.
2.یادگیری نیمه نظارت[^Semi-supervised Learning] : در یادگیری نیمه نظارت از مجموعهای از کلمات نمونه برای یادگیری استفاده میشود (مثل مجموعهای از نام کتابها). این روش ها ابتدا سعی در  یافتن موجودیتهای نمونه در متون کرده و سپس با توجه به ساختار متن در بر دارنده کلمات، بدنبال سایر موجودیتهایی از آن نوع میگردد. 
3.یادگیری بی نظارت[^Unsupervised Learning] :یادگیری بدون نظارت، با استفاده از منابع لغوی  و الگوهای لغوی و محاسبات آماری به  شناسایی میپردازد. به عبارتی تکنیک معمول برای یادگیری  بدون نظارت بر پایه دسته بندی موجودیتها است.[3]


**روش مبتنی بر قوانین** 
 رهیافت های مبتنی بر قوانین، روی استخراج نام با استفاده از تعداد زیادی از مجموعه قوانین ساخته شده به صورت دستی تمرکز نموده اند . به طور کلی این سیستم ها مجموعه ای از الگوها هستند که از مشخصه ها ی گرامری (مانند ادات سخن) ،نحوی ( مانند تقدم کلمات) و املایی ( مانند بزرگ و کوچک بودن حروف ) در کنار ترکیبی از لغت نامه استفاده می کنند.
این نوع از مدل ها  برای دامنه های خاص نتایج بهتری را حاصل کرده اند و توانایی تشخیص واحدهای پیچیده ای را دارند که روش های مبتنی بر یادگیری ماشین به سختی می توانند آنها را تشخیص دهند .
به هر حال روش های مبتنی بر قوانین مشکل غیر قابل حمل بودن و نیز کمبود قابلیت اطمینان را دارند. علاوه بر آن هزینه های بالای ایجاد قوانین نیز به مشکلات این روش اضافه می شود حتی اگر تغییر کوچکی در داده های ما ایجاد شود این هزینه افزایش می یابد . این نوع رهیافت اغلب منحصر به زبان یا حوزه خاص می شوند و نمی توانند به طرز مناسبی با زبان و حوزه ها ی جدید منطبق شوند.[6]
روشهای اولیه ای که برای کشف موجودیتهای نامدار پیشنهاد می شد بیشتر مبتنی بر قانون بود، در حالی که امروزه اکثر کارها به سمت استفاده از روشهای یادگیری پیش میرود.
در زبان فارسی با توجه به عدم وجود پیکره های برچسب خورده با برچسب های معنایی یا طبقات نامدار و همچنین دردسترس نبودن واژگان های کاملی چون وردنت [^ WordNet ]به ناچار باید تمرکز بیشتر بر روش های مبتنی بر قاعده باشد. چون در زبان فارسی همچون زبان انگلیسی امکان درک موجودیت نامدار با توجه به بزرگی حرف اول کلمات وجود ندارد،پس بجای آن برای بهبود سیستم از برچسبگذاریهای نحوی و مجموعهای از اسامی خاص مانند مجموعه اسامی مناطق، افراد، روزهای هفته، واحدهای پولی، عناوین و... استفاده میشود.[3]

معماری سیستم مبتنی بر قوانین
سیستم NER معرفی شده در این قسمت از سه بخش اصلی : پیش پردازش، تشخیص و برچسب زنی و  پالایش تولید نتیجه تشکیل شده است.
<a href="http://upload7.ir/"><img src="http://upload7.ir/imgs/2014-12/28819320022762287490.jpg" border="0" alt="آپلود عکس | آپلود | سایت آپلود عکس | اپلود عکس" /></a>


در این سیستم پس از دریافت متن، با ورودی مورد پذیرش سیستم تطبیق داده میشود، واحدهای خاص شناسایی شده و برچسب POS  زده میشود. بعد از این سپس بر روی آن برچسب گذاری نحوی، با توجه به ترکیبهای اعداد، کلمات و علامات به شناسایی اولیه اعداد و برچسب گذاریهای معنایی پرداخته می شود و برچسب گذاری ثانویهای از نامهای خاص مکمل این مرحله است. در انتهای مرحله پیش پردازش، با استفاده از ساختار واژگانی اسامی خاص، سعی در شناخت این واژگان مستقل از متن میشود.
در مرحله ی شناسایی، با توجه به نحوهی چیدمان واژگان درمتن و الگوهای موجود برای هر مقوله، موجودیتهای نامدار شناخته شده و مرز آنها با توجه به تکرارها و برچسب نحوی و معنایی کلمات مشخص میشود. در انتها با حذف خطاها و تکرارهای شناخته شده، هر موجودیت در مقوله ی مناسب خود دسته بندی شده و خروجی با برچسب گذاری معنایی موجودیتهای نامدار با عنوان مقوله ای که در آن قرار می گیرند تولید می شود.[3]

مقوله بندی برچسب های معنایی
موجودیتهای نامدار در مقوله های مختلفی دسته بندی میشوند. این مقوله ها میتوانند بسته به هدف سیستم تشخیص اسامی نامدار، در طیفی از زمینه های تخصصی چون تشخیص و ... تا زمین های عامی چون نام «DNA» اسامی بیماریها و افراد یا سازمانها رده بندی شوند. در این طبقه بندی هر مقوله ی کلی هم میتواند به زیر مقوله های جزئی تر تقسیم شود. یک موجودیت نامدار میتواند در هر رده از سلسله مراتب بالا قرار گیرد. هر چه در عمق پایینتر، برچسب معنایی آن دقیقتر است.[3]
<a href="http://upload7.ir/"><img src="http://upload7.ir/imgs/2014-12/25301845293428945496.png" border="0" alt="آپلود عکس | آپلود | سایت آپلود عکس | اپلود عکس" /></a>

1***مرحله پیش پردازش**
پس از دریافت متن ورودی و پیش از انجام هر گونه عملیاتی شناسایی بر روی متن، ابتدا واحدهای خاص چون URL شناسایی می شوند و سپس پردازشهای اولیه مورد نیاز برروی متن، اجرا می شوند. این پردازش ها شامل قطعه بندی و تحلیل ساختواژی احتمالی جهت آماده سازی متن برای ورود به پیمانه برچسب زن مقوله نحوی ارتقاء یافته است. همچنین برچسبهای معنایی اولیه، برای اعداد و ترکیب آنها با علامات اطراف و نیز ساخت شناسی کلمات خاص، در این مرحله زده میشود تا در مرحله تشخیص، اصلاح و تکمیل شوند.همچنین این قسمت شامل مراحل زیر است :
1- استخراج واحدهای خاص
برخی از واحدهای متنی لازم است به همان شکل وارد شده در متن و بدون هیچ پردازش یا تغییر شکلی استخراج شوند. از  جمله این واحدها می توان به آدرس صفحات وب URL یا آدرس نامه های الکترونیکی اشاره نمود چون ایجاد فاصله در این موارد امکان تشخیص را پایین می آورد.
2-	قطعه بندی و برچسب گذاری مقوله نحوی ارتقاء یافته
پس از استخراج واحدهای خاص برای عمل قطعه بندی، کلیه عملیات لازم اعم از جدا کردن کلمات چسبیده، برداشتن فاصله ها و نیم فاصله های اضافه، چسباندن کلمات جدا را سیستم انجام میدهد.
بعد از این پردازشهای اولیه، متن حاصل به برچسب زن مقوله نحوی می شو دکه  متن را بر اساس مجموعهای از  نوع برچسب[^Tagset ]برچسب گذاری می کند.
3-	برچسب زنی اعداد
در سیستم شناسایی موجودیت های نامدار، علاوه بر برچسب زنی معمول نیاز به برچسب های پیشرفته تری نیز هست که بر اساس ترکیب برچسب های قبلی بدست می آیند. در جدول زیر برچسبهای بکار رفته در این مرحله آورده شده است.[3]
<a href="http://upload7.ir/"><img src="http://upload7.ir/imgs/2014-12/16245711849628545229.jpg" border="0" alt="آپلود عکس | آپلود | سایت آپلود عکس | اپلود عکس" /></a>

2***شناسایی موجودیت و برچسب معنایی آن**
پس از مرحله پیش پردازش نوبت به شناسایی موجودیت های نامدار با استفاده از متن برچسب گذاری شده میرسد. در این مرحله ابتدا موجودیت های اسمی ها با استفاده از روشهای بکار برده شده که در ادامه مطرح شده اند حدس زده می شوند، سپس صحت موجودیت های اسمی  و نوعشان  که حدس زده شده بررسی می شود و نهایتًا مشخص میشود.
برای تشخیص یک کلمه در متنش، می توان از الگو استفاده کرد. در این سیستم نیز توجه به الگویی که هر کلمه در آن قرار گرفته به عنوان مبنای تشخیص بکار میرود. الگوها به صورت مجموعهای از کلمات و برچسبهایی هستند که در متن بدنبال هم میآیند.
الگوها به طور عام به صورت << دسته  *>> و یا << دسته * *>> ظاهر می شوند.  * در الگوی اول یک موجودیت یک کلمه ای  و * * در الگوی دوم جایگاه یک موجودیت چند کلمه ایست. 
مثلا «دولت* » برای برای نام کشور و« نهاد** »  نام یک نهاد بکار  و  میرود. در اینصورت عباراتی مثل "...دولت ایران.." و یا "...نهاد نمایندگی مقام معظم رهبری در دانشگاه ها..." با این الگوها مطابقت خواهند کرد.
مجموعًا در این سیستم، جستجو برای تشخیص موجودیت نامدار با کمک الگوها به این صورت انجام میگیرد که برای تک- تک عناصر برچسب گذاری شده در متن (با در نظر داشتن ضمایر چسبیده به کلمات و نیز ادات جمع)، هم برای خود کلمه وهم برای برچسب آن بررسی میشود که آیا در هیچ یک از الگوها صدق میکنند یا نه و به این ترتیب مجموعهای از اسامی خاص و نوع آنها (که عنوان مقوله هر الگو است) مشخص می شود.[3]

3***پالایش و تولید خروجی نهایی**
پس از کشف موجودیتها و اعمال برچسب معنایی به آنها، سیستم وارد مرحله پردازش نهایی میشود. در این مرحله با توجه به ساختار سلسله مراتبی سیستم، موجودیتهای نامدار تکرار شده در یک مقوله و یا در مقوله های سطح پایینتر (گره فرزند) کشف شده و حذف میشوند. همچنین موجودیتهایی که درون موجودیتی دیگر قرار گرفته اند با توجه به مکان آنها در متن شناسایی و حذف میگردند. مثلا « انجمن شرکتهای بازرگانان نمونه » ممکن است  « بازرگانان نمونه » را از مقوله شرکت ببیند ، در حالی که « شرکت  بازرگانان نمونه>> از مقوله انجمن ، موجودیت خاص مورد نظر است. پس سیستم با مشاهده چنین شرایطی موجودیت نامدار تکرار شده در موجودیت نامدار دیگر را حذف میکند. نهایتًا مجموعه موجودیتهای شناسایی شده در مقوله مناسبشان دسته بندی شده و خروجی با برچسبهای معنایی تولید میشود.
 این سیستم قابل استفاده به عنوان مکملی برای کاربردهایی از قبیل برچسبگذاریهای نحوی، استخراج اطلاعات و درک مطلب و خلاصه سازی ماشین میباشد.[3]

**روش های مبتنی بر یادگیری ماشین**
در سیستم های مبتنی بر یادگیری ماشینی ،هدف از رهیافت تشخیص واحدهای اسمی تبدیل مساله تشخیص به مساله دسته بندی است و از یک مدل آماری دسته بندی برای حل این مساله استفاده می شود.در این روش مدل به دنبال تشخیص الگوها و یافتن رابطه ی آنها با متن و ساختن یک مدل آماری و الگوریتم یادگیری ماشین است.
این سیستم ها نام ها را یافته و آن ها را بر اساس مدل به دست آمده با استفاده از روش های یادگیری ماشین به کلاس های از پیش تعیین شده مانند اشخاص ، مکان ها ، زمان ها و ... تقسیم می کند.
این مدل یادگیری، یادگیری با ناظر است یعنی سیستم با استفاده از یک مجموعه از مثال های برچسب گذاری شده ،دسته بندی را یاد می گیرد.
در این روش ابتدا سامانه به وسیله ی پیکره ای از داده های آموزشی که به صورت دستی و به وسیله ی انسان برچسب گذاری[^labelling] شده اند آموزش دیده، با یادگیری از طریق این داده ها به تشخیص خودکار اسامی خاص در متن می پردازد، که در بخش ویژگی های سندی اشاره شد.
برای برچسب زنی داده ی آموزشی از روش برچسبزنی شروع-داخل- خارج  [^BIO tagging] استفاده میشود. در این روش، برای تشخیص موجودیتهای اسمی، کلمات متن را تک تک برچسب زنی می نماییم[1].
روش های با ناظر به داده های برچسب گذاری شده برای ساخت یک مدل آماری نیاز دارند. برخلاف رهیافت های مبتنی بر قوانین ، روش های یادگیری ماشین به راحتی به حوزه ها و زبان های دیگر منتقل می شوند. [6]

معماری سیستم تشخیص موجودیت های نامدار مبتنی بر یادگیری ماشین
شکل زیر معماری این سیستم را نشان می دهد :
<a href="http://upload7.ir/"><img src="http://upload7.ir/imgs/2014-12/19854141653915483021.png" border="0" alt="آپلود عکس | آپلود | سایت آپلود عکس | اپلود عکس" /></a>

مراحل شناسایی و طبقه بندی اسامی یک متن عبارتند از :
 1 – یک متن با ورودی به سیستم ارائه می شود مانند جمله ی " حسن شنبه به تهران می رود."
2 – با استفاده از یک نشان گذار کلمات در متن ورودی از یکدیگر جدا می شوند.(حسن/شنبه/به/تهران/می رود)
3-با استفاده از برچسب زن دستوری نقش دستوری هر کلمه مشخص می شود(حسن/اسم | شنبه/اسم | به/حرف | تهران/اسم | می رود/فعل)
4 – با استفاده از برچسب دستوری کلمات ، اسامی شناسایی شده و از بقیه کلمات متن جدا می شوند.(حسن/شنبه/تهران)
5 –برای هر یک از اسامی بردار ویژگی لازم استخراج می شود.
6 – با استفاده از یک طبقه بند آماری ، اسامی در طبقات مربوطه طبقه بندی می شوند.

مراحل یک تا چهار مانند روش با قاعده است که توضیح داده شد.در اینجا مراحل استخراج ویژگی و طبقه بندی را توضیح می دهیم.
در مرحله استخراج برای هر یک از اسامی بردار ویژگی لازم استخراج می شود که این ویژگی ها شامل ویژگی های نویسه ای و ویژگی های دیگری که از کل متون آموزشی بدست آمده استفاده می شود.
سپس این بردارهای ویژگی به طبقه بند آماری داده می شود تا اسامی مکان و افراد از اسامی عمومی استخراج گردند.
برای آموزش سیستم خود هر اسم را به عنوان یک داده ی ورودی در نظر گرفته وبرای هر اسم با توجه به برچسب هایی که در این مجموعه داده برای آن در نظر گرفته شده یک سری ویژگی هایی را مشخص می کنیم.بعضی از ویژگی ها را هم که مربوط به خود کلمه است،می توان با استفاده از یک سری از الگوریتم های پردازش زبان بدست آورد.
برای هر اسم می توان ویژگی هایی از قبیل :
 1.نقش دستوری کلمه قبل
 2.نقش دستوری کلمه بعد 
3.طول کلمه
 4.جمع یا مفرد بودن
 5.وجود پسوندهایی که باعث تولید اسم مکان می شوند مثل گاه ،خانه،آبادو..
  6.وجود پسوندهایی که در اغلب موارد باعث تولید اسم خاص می شوند مثل پور،زاده،نژاد و...
  7.وجود "ی" نسبی در آخر کلمه
   8.درصد حضور کلمه در کل متون آموزشی به صورت اسم مکان
   9.درصد حضور کلمه در کل متون آموزشی به صورت اسم خاص افراد[7]
   **طبقه بندی اسامی**
   پس از اینکه ویژگی های لازم برای آموزش سیستم استخراج شد در این مرحله با استفاده از طبقه بندی کننده ،داده های خود را طبقه بندی می کنیم.
   **ماشین بردار پشتیبان** [^support vector machine]
   هدف تشخیص واحدهای اسمی این است که مساله ی شناسایی را به مساله ی دسته بندی یا کلاس بندی تبدیل کند و یک مدل آماری کلاس بندی را برای حل آن به کار گیرد. رهیافت استفاده از ماشین پشتیبان برای بهتر کردن این کلاس بندی استفاده می شود.
ماشین بردار پشتیبان یکی از روش های یادگیری ماشین با ناظر معروف برای کلاس بندی دو تایی در طیف وسیعی از مجموعه داده ها است.ماشین بردار پشتیبان بهترین پاسخ را در مواقعی که مجموعه داده ها پراکنده هستند و یا هنگامی که مجموعه آموزشی کوچک است تولید می کند و با استفاده از توسعه های مختلف از این الگوریتم می توان برای مسائل با چند کلاس نیز به کار رود.
برای حل یک مسئله کلاس بندی با استفاده از یک الگوریتم با ناظر ، همواره ماشین با استفاده از یک مجموعه آموزشی که در آن کلاس هر مورد مشخص است آموزش می بیند. برای هر ماشین بردار پشتیبان ، دو مجموعه داده وجود دارد که در آن ماشین با استفاده از مجموعه داده ی آموزشی این داده ها را بر اساس خصیصه هایشان کلاس بندی می کند.
با توجه به شکل زیر یک ماشین بردار پشتیبان می آموزد که چگونه یک ابر صفحه را برای جداسازی دو کلاس مختلف با بیشترین حاشیه بیابد.
<a href="http://upload7.ir/"><img src="http://upload7.ir/imgs/2014-12/55980154359750392615.jpg" border="0" alt="آپلود عکس | آپلود | سایت آپلود عکس | اپلود عکس" /></a>
در روش استفاده از ماشین بردار پشتیبان ،ابتدا داده های موجود به دو قسمت داده های آموزشی و داده های آزمون تقسیم می شوند. در قدم بعدی ،مجموعه خصیصه ها انتخاب می شوند.در انتخاب مجموعه خصیصه یا ویژگی ، اغلب ویژگی هایی انتخاب می شوند که مختص آن زبان هستند مثل :اطلاعات لغوی وابسته به فرهنگ لغت ،حروف پسوند و پیشوند ،اطلاعات واحد اسمی که در گذشته آمده اند، کلاس های واحد اسمی ممکن و...
در بعضی موارد هم می توان از خصیصه های مستقل از زبان مانند : کلمه ی اول جمله بودن،شامل رقم بودن،حاوی رقم و ویرگول بودن و ...
در روش استفاده از ماشین بردار پشتیبان ، بعد از انتخاب ویژگی ها ، کلمات را در یک فضای n بعدی که n تعداد ویژگی ها است قرار می دهند و سپس فضا را تقسیم بندی می کنند. البته لزومی ندارد که تقسیم کننده ی فضا لزوما یک ابرصفحه باشد و با استفاده از ماشین هسته ای[^ kernel machine ]به جای ماشین بردار پشتیبان می توان از یک تقسیم کننده ی غیر خطی استفاده نمود.
از این روش بر روی زبان هندی که به یک سری از ویژگی های زبان فارسی نزدیک است انجام شد که نتایج قابل قبولی داشت.[6]

**مدل مخفی مارکوف**
مدل مخفی مارکوف در اواخر دهه 1960 میلادی معرفی گردید و در حال حاظر به سرعت در حال گسترش  دامنه کاربرد ها می باشد.دو دلیل مهم برای این مسئله وجود دارد ; اول اینکه این مدل از لحاظ ساخنار ریاضی بسیار قدرتمند است و به همین دلیل مبانی بسیاری از کاربردها را شکل داده است.
در مدل مارکف معمولی، هر حالت متناظر با یک رویداد قابل مشاهده است اما در مدل مخفی مارکف مشاهدات توابع احتمالاتی از حالت ها هستند.در این صورت مدل حاصل یک مدل تصادفی با یک فرایند تصادفی است و تنها توسط مجموعه ای از فرآیندهای تصادفی که دنباله مشاهدات را تولید می کند قابل مشاهده است.اطلاق کلمه ی مخفی به این دلیل است که درباره مسائلی صحبت می کنیم که طریقه انجام آن ها از دید ما پنهان است و البته ماهیت ماهیت آماری دارد.
در شکل زیر معماری مدل مخفی مارکف نشان داده شده است.هر شکل بیضی بیانگر یک مقدار متغیر تصادفی است.x_t  مقدار  تصادفی است که مقدار تغییر پذیرش در واحد زمان مخفی است و y_t  مقدار تصادفی است که مقدار پذیرش در زمان t قابل مشاهده است.
<a href="http://upload7.ir/"><img src="http://upload7.ir/imgs/2014-12/91327354706197271918.jpg" border="0" alt="آپلود عکس | آپلود | سایت آپلود عکس | اپلود عکس" /></a>
مدل مخفی مارکف با پارامترهای زیر تعریف می شود:
N : (تعداد حالات (متناهی
M : تعداد خروجی های ممکن
A : ماتریس گذار حالت
B : توزیع های احتمالاتی برای خروجی های ممکن در حالت
P : توزیع احتمالاتی حالات اولیه.
مدل مخفی مارکف مانند روش های دیگر یادگیری ماشین در تشخیص واحدهای اسمی به کار می رود.یکی از کاربرد های اصلی مدل مخفی مارکف تشخیص محتمل ترین دنباله از حالت های مخفی با استفاده از الگوریتم ویتربای[^Viterbi algotithm] است.
از لحاظ ساختار داخلی ، مدل مخفی مارکف سعی دارد با محاسبه ی پارامترهای داخلی یک توالی( برای مساله ما جملات)را برچسب گذاری کند.
با در نظر گرفتن برچسب ها به عنوان حالت های مدل مارکف می توانیم این موقعیت را با استفاده از الگوریتم ویتربای تخمین بزنیم و مشکل کلیدی این است که چگونه مدل مخفی را با استفاده از داده های آموزشی بسازیم.در استفاده از این روش فرض می شود داده های آموزشی کافی هستند و ما به تعدادی از گذارهای بین برچسسب های ادات سخن دست یافته ایم تا مدل (X,Y,A,B,P ) را بسازیم که در آن X وy به ترتیب کلمات و برچسب ها هستند.
<a href="http://upload7.ir/"><img src="http://upload7.ir/imgs/2014-12/59793109084280214239.jpg" border="0" alt="آپلود عکس | آپلود | سایت آپلود عکس | اپلود عکس" /></a>
استفاده از مدل مخفی مارکف در بسیاری موارد به نتایج خوب و قابل قبولی منجر شده است.[6]



















# آزمایش‌ها

# کارهای آینده

# مراجع

[1] Erik, F., Tjong, K. S., & Fien, D. M. (2003). Introduction to the CoNLL-2003 Shared Task: Language-
Independent Named Entity Recognition. CoNLL-2003 (p. 6). CNTS - Language Technology Group University of Antwerp.
[2] 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.
[3] پونه سادات مرتضوی، مهرنوش شمس فرد، "شناسایی موجودیت های نام دار در متون فارسی"، پانزدهمین کنفرانس بین المللی سالانه انجمن کامپیوتر ایران، 1388
[4] Nadeau, David, and Satoshi Sekine. "A survey of named entity recognition and classification." Lingvisticae Investigationes 30.1 (2007): 3-26.
[5] M. Asgari Bidhendi, et al., "Extracting person names from ancient Islamic Arabic texts", in Proceedings of LREC-Rel, pp. 1-6, 2012.
[6] LingePipe: Named Entity Tutorial. (2003 - 2009). Retrieved June 28, 2010, from allias-i.com:
http://alias-i.com/lingpipe/demos/tutorial/ne/read-me.html
[7] Jurafsky, D., & Martin, J. H. (2007). Speech and Language Processing: An introduction to natural
language processing,. Draft.
[8] Ratnaparkhi, A. (1997). A Simple Introduction to Maximum Entropy Models for Natural Language
Processing. Pennsylvania: Institute for Research in Cognitive Science.
[9] محمدمهدی حاجی،مدل سازی آماری زبان فارسی ،بهار 1384
[5] محمدمهدی حاجی،مدل سازی آماری زبان فارسی ،بهار 1384
[6]مجید عسگری بیدهندی،ساخت چهارچوبی برای استخراج خودکار نام از متن،پایان نامه مقطع کارشناسی ارشد،شهریور1390
[7]سیدعبدالحمید اصفهانی،سیدراحتی قوچانی،نادر جهانگیری ،سیستم شناسایی و طبقه بندی اسامی در متون فارسی،1389


# پیوندهای مفید
+ [تشخیص موجودیت‌های نام‌دار، پروژه درس هوش مصنوعی نیمسال دوم ۸۹-۸۸ دانشگاه علم و صنعت](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)