دانلود پایان نامه ارشد درمورد سلسله مراتبی، سلسله مراتب، ماشین بردار پشتیبان

ا نمونه‏های موجود می‏باشند و همانطور که در گراف به سمت بالا حرکت می‏کنیم، می‏بینیم نقاطی که با توجه به تابع تشابهِ مفروض به یکدیگر نزدیک هستند ادغام شده‏اند. با حرکت در جهت بالا، اندازه خوشه‏ها نیز افزایش می‏یابد. از طرف دیگر فرآیند ادغام تا زمانی ادامه می‏یابد که یا تنها یک خوشه داشته باشیم و یا اینکه به یک آستانه مناسب برسیم.

شکل3-5: مثالی از نمودار دندوگرام در تشخیص عبارت‏های اسمی هم‏مرجع 207
شکل 3-6، یک پیاده سازی مناسب از الگوریتم خوشه‏بندی سلسله مراتبی پایین به بالا را نمایش می‏دهد. این الگوریتم با مقدار‏دهی اولیه خوشه‏بندی C آغاز می‏شود؛ به این ترتیب که خوشه‏بندی C، شامل تمامی نمونه‏ها در قالب خوشه‏های یگانه خواهد بود. از آنجائیکه، خوشه‏بندی اولیه، شامل تعداد زیادی خوشه می‏باشد، مکررآً، جفت خوشه‏ای ⟨c_i ┤,├ c_j ⟩که دارای امتیاز بالاتری نسبت به سایرین هستند انتخاب می‏شوند و درصورتی که امتیاز آنها از حد آستانه مورد نظر τ=f(0,0) بیشتر باشد، خوشه‏های c_i,c_j با یکدیگر ادغام و تشکیل یک خوشه‏ی جدید می‏دهند، و این فرآیند با جفت خوشه دیگری که دارای امتیاز بالاتری نسبت به سایرین هستند ادامه پیدا می‏کند. تابع امتیازدهی f(c_i,c_j ) یک ترکیب وزن‏دار خطی از ویژگی‏های φ(c_i,c_j ) می‏باشد که از جفت خوشه‏ها استخراج شده، و توسط بردار وزن W پارامتردهی می‏شود. از سویی دیگر، تابع ρ نیز، خوشه‏بندی208 C را به عنوان ورودی گرفته و طبق رابطه 3-14، مجموعه‏ای از جفت خوشه‏ها ⟨c_i ┤,├ c_j ⟩را برمی‏گرداند.
رابطه (3-14) } }∪{⟨0┤,├ 0⟩ c_i,c_j∈c, c_i≠c_j | ⟨c_i ┤,├ c_j ⟩ ρ(C)={
همانطور که در رابطه‏ی 3-14، مشاهده می‏شود، ρ(C) شامل جفت ⟨0┤,├ 0⟩ نیز می‏باشد، که برای آن، φ(0,0) تعریف خواهد شد تا شامل ویژگی دودویی منحصر بفردی برای جفت‏های خالی نیز باشد. وزن متناظرِ آن، به همراه تمام وزن‏های دیگر، مورد یادگیری قرار می‏گیرد تا به طور موثر به عنوان آستانه‏ی خوشه‏بندی τ=f(0,0) عمل نماید.
3-2-1-2. آموزش الگوريتم خوشه‏بندی سلسله مراتبی
الگوریتم‏هایی که در شکل‏های 3-7 و 3-8 آمده‏اند، بیانگر یک مدل یادگیری افزایشی می‏باشند. در الگوریتم 3-7، بردار وزنی W، با تکراری به اندازه‏ی تعداد دوره‏های آموزشیT و یک مجموعه خوشه‏بندی شده209، بروزرسانی می‏شود؛ بدین ترتیب که این الگوریتم مکرراً، از خوشه‏بندی‏های مشخص شده برای نیل به این منظور استفاده می‏کند. این اقدام و استفاده از میانگین در بردارِ وزنی مانع از بروز بیش‏برازش210 خواهد شد. همان طور که مشاهده می‏شود، هسته اصلی مدل یادگیری، رویه بروزرسانی است و بطوریکه الگوریتم یادگیری، برای بروزرسانی آخرین بردار وزنی، این رویه را فراخوانی می‏کند.

الگوریتم خوشه‏بندی سلسله مراتبی پایین به بالا با ورودی‏های (X,F):
X={x_1,x_2,…,x_n } و
f(c_i,c_j )=W^T φ(c_i,c_j )
به ازای i=n تا i=1 انجام بده
C_i←{x_i }
پایان حلقه اول
C ←{C_i }1≪i≪n
در همه‏ی جفت خوشه‏هایی که فاصله‏ی میان آنها را بوسیله تابع f(c_i,c_j ) محاسبه شده است، آنکه دارای بیشترین امتیاز است را در نظر بگیر ⟨c_i ┤,├ c_j ⟩←argmaxf(p)/(p∈ρ(c) )
تا زمانی که |C|1 و f(c_i,c_j )τ ادامه بده
در C، c_i,c_jرا با c_i∪c_j جایگزین کن
حالا از میان جفت‏های باقیمانده، جفت بعدی که دارای بیشترین امتیاز است را انتخاب کن ⟨c_i ┤,├ c_j ⟩←argmaxf(p)/(p∈ρ(c) )
پایان حلقه دوم
بازگرداندن C در خروجی
شکل 3-6: الگوریتم خوشه‏بندی سلسله مراتبی پایین به بالا
الگوریتم بروزرسانی، نخست مانند الگوریتم خوشه‏بندی حریصانه عمل می‏کند، تا تمام داده‏های ورودی را در قالب خوشه‏های تک عنصری در مجموعه خوشه‏بندی C ̂ قرار دهد. در هر تکرار ازحلقه(خطوط 6 تا 17)، یک جفت خوشه ⟨c ̂_i ┤,├ c ̂_j ⟩ که دارای بیشترین امتیاز نسبت به سایرین هستند ادغام می‏شوند، حلقه آنقدر ادامه پیدا می‏کند تا تمام خوشه‏ها با هم یکی شده و تشکیل یک خوشه را بدهند و یا جفت خوشه خالی نیز به حداکثر امتیاز برسد. منطق بروزرسانی وزن در خطوط8-11 تعبیه شده‏است. به این ترتیب که اگر بتوان جفت دقیق تری پیدا کرد، آن‏را به عنوان جفتی که دارای بالاترین امتیاز است به ورودی پرسپترون در خط 11 داده‏می‏شود.

الگوریتم یادگیری با ورودی‏های (C,T)
ورودی این الگوریتم: دریافت مجموعه خوشه‏بندی‏های ∁ به عنوان مجموعه‏ی آموزشی و تعداد دوره‏های آموزش T
خروجی: مقدار میانگین شده W ̅
مقدار 0 را به W اختصاص بده
به ازای t=T تا t=1 انجام بده
برای تمام C∈∁ انجام بده
UPDATE(C,W) W←
پایان حلقه اول
پایان حلقه دوم
بازگرداندن W ̅
شکل 3-7: الگوریتم آموزش خوشه‏بندی حریصانه
اگر چندین جفت خوشه در خطوط 7و10 کاندیدا شوند، به طور تصادفی یکی از آنها انتخاب می‏شود. این عمل به خصوص در هنگام شروع فرآیند و هنگامی که بردار وزن برابر با صفر است، می‏تواند موثر واقع شود. از طرفی دیگر در خط 8، تابع خوبی211 یا تناسب استفاده شده‏است، این تابع برای جفت خوشه⟨c ̂_k ┤,├ c ̂_l ⟩ به صورت g(c ̂_k,c ̂_l│C ̂ ) تعریف شده است. این مقدار با توجه به خوشه‏بندی برچسب‏دار آموزشیِ ∁ به عنوان صحتِ212 جفت‏های هم‏مرجع درنظر گرفته می‏شود، که در صورت ادغام c ̂_k وc ̂_l ایجاد گردیده است.
رابطه (3-15) g(.)=|{(x,y)∈c_k×c_l |∃c_i∈C:x,y∈c_i }|/(|C ̂_k |.|C ̂_l | )
رابطه‏ی3-4 نشان می‏دهد، تابع تناسب، در خطوط 8تا 10، جفت خوشه‏ای را انتخاب می‏کند که در هنگام ادغامشان، نتایج در خوشه‏بندی به دقت بهتری منتج شوند. به طورکلی این الگوریتم سعی دارد به گونه‏ای با جستجو در داده‏های آموزشی، پارامترهایی را پیدا کند که هم بیش‏برازش را تحت کنترل داشته باشد(با استفاده از پارامترهای میانگین) و هم دقت خوشه‏بندی، بیشینه گردد.
الگوریتم UPDATE با ورودی‏های (C,W)
X←{C_1∪C_2∪…∪C_m }={x_1,x_2,…,x_n }
به ازای i=n تا i=1 انجام بده
C ̂_i←{x_i }
پایان حلقه اول
C ̂ ←{ C ̂_i }1≪i≪n
تا زمانیکه |C ̂ |1 ادامه بده
⟨c ̂_i ┤,├ c ̂_j ⟩←(argmaxW^T φ(ρ))/(p∈ρ(c) )
β←{⟨c ̂_k ┤,├ c ̂_l ⟩∈ρ(C ̂)|g(c ̂_k,c ̂_l |C ̂)g(c ̂_i,c ̂_j |C ̂)
اگر β≠0 آنگاه
حالا از میان جفت‏های باقیمانده، جفت بعدی که دارای بیشترین امتیاز است را انتخاب کن ⟨c ̂_k ┤,├ c ̂_l ⟩←(argmaxW^T φ(ρ))/(p∈ρ(c) )
W←W+φ(c ̂_k,c ̂_l )-φ(c ̂_i,c ̂_j)
پایان شرط اول
اگر ⟨c ̂_i ┤,├ c ̂_j ⟩=⟨0,├ 0⟩┤ آنگاه
بازگرداندن W در خروجی
پایان شرط دوم
در C ̂، c ̂_i,c ̂_jرا با c ̂_i∪c ̂_j جایگزین کن
پایان حلقه دوم
بازگرداندن Wدر خروجی
شکل3-8: الگوریتم بروز رسانی
3-3.جمع‏بندی
در این فصل الگوریتم‏های یادگیری مناسب برای ارزیابی تشخیص مرجع مشترک در این پایان‏نامه مورد بررسی قرار گرفت، این روش‏ها شامل روش‏های رده‏بندی پرسپترون، ماشین بردار پشتیبان، درخت تصمیم C5 و خوشه‏بندی سلسله مراتبی می‏باشند.
فصل چهارم
سيستم ارزيابی
« شناسايی اشاره و تشخيص اشاره‏های هم‏مرجع »

4-۱.مقدمه
امروزه اغلب پژوهشگران، فرآیند تشخیص مرجع مشترک را به دو مرحله تقسیم می‏کنند؛ (۱) کشف اشاره؛ برای شناسایی عبارت‏های اسمی که به موجودیت‏ها در دنیای واقعی اشاره دارند، (۲) شناسایی اشاره‏های که به یک مرجع واحد اشاره دارند. از آنجائی‏که ما نیز از این رویکرد پیروی می‏کنیم، در این فصل، این دو فرآیند را در قالب چارچوبی شامل سیستم ارزیابی معرفی می‏نمائیم. در بخش اول، برای فرآیند مهم کشف اشاره سیستمی معرفی می‏کنیم که می‏تواند اشاره‏های موجود در پیکره لوتوس را شناسایی کرده و علاوه بر نمایش ویژگی‏های مهم هر اشاره، محدوده و هسته هر اشاره را نیز شناسایی و ذخیره نماید. در بخش دوم نیز با به کارگیری الگوریتم‏های گفته شده در فصل سوم، به تحلیل جفت اشاره‏‏های هم‏مرجع در پیکره می‏پردازیم.
4-۲. سيستم شناسايی اشاره لوتوس
این سیستم، سه رکن اساسی دارد؛ پیکره ورودی، بانک اطلاعاتی و برنامه کاربردی. ورودی این سیستم پیکره‏ی نشانه‏گذاری شده لوتوس می‏باشد که ویژگی‏های آن در فصل دوم معرفی شدند. در ادامه به معرفی مختصری از بانک اطلاعاتی لوتوس و سیستم شناسایی اشاره‏ها می‏پردازیم.
4-۲-۱. بانک اطلاعاتی
با پیروی از سیستم ارائه شده توسط [40]، ما نیز رویکرد تبدیل پیکره، به اطلاعات ساختار یافته بانک اطلاعاتی را دنبال می‏کنیم، با این تفاوت که مبنای کار ما استخراج اطلاعاتِ مربوط به اشاره‏های موجود در پیکره می‏باشد. به همین منظور بانک اطلاعاتی سیستم پایه لوتوس را طراحی نمودیم، این بانک اطلاعاتی شامل جداولی است که تمام چهار گروه موجودیت‏های گفته شده در فصل قبل را پوشش می‏دهد و به گونه‏ای طراحی شده است تا بتواند نقش فرهنگ جغرافیایی213 را نیز ایفا نموده و به شبکه واژگان نیز مرتبط گردد. در جدول 4-1، یک شمای کلی از جداول این بانک اطلاعاتی نمایش داده شده است.
همان‏طور که گفته شد، در سیستم شناسایی اشاره با در نظر گرفتن یک سری قوانین و اولویت‏ها، اشاره‏ها و اطلاعات مربوط به آنها را از پیکره استخراج شده و در بانک اطلاعاتی ذخیره می‏شوند. سیستم شناسایی اشاره ارائه شده دراین پایان‏نامه، به موازات ذخیره اطلاعات اشاره‏ها در جدول مربوط به اشاره‏ها، تمامی واژه‏های موجود در متن را نیز به جدول واژگان منتقل می‏نماید. ویژگی‏های جدول واژگان در جدول 4-۱ مشاهده می‏شود.

شکل4-1: شمای کلی از جداول این بانک اطلاعاتی لوتوس

جدول 4-۱: بانک اطلاعاتی سیستم کشف اشاره؛ جدول واژگان
Word_Table
Word_ID
Primary Key
کلید اصلی
Document_ID
Attribute
به ازای هر متن یک شناسه تعیین می‏شود
Sentence_ID
Attribute
به ازای هر متن یک شناسه تعیین می‏شود
Word_String
Attribute
واژه
Word_Feature1
Attribute
نوع واژه
Word_Feature2
Attribute
تعداد واژه
در این جدول اطلاعات پایه در مورد هر واژه ذخیره خواهد شد، این اطلاعات پایه شامل خود واژه، متنی که واژه به آن تعلق دارد، شماره جمله‏ای که واژه به آن تعلق دارد، نوع واژه، مفرد یا جمع بودن واژه می‏شود. از طرفی دیگر ویژگی‏های جدول اشاره‏ها، که شامل اطلاعات مورد نیاز برای تشخیص مرجع مشترک می‏باشد نیز در جدول 4-۲، آمده است. در جدول اشاره‏ها، نوع اشاره، نوع موجودیت، زیر گروه موجودیت، نوع کلاس موجودیت، کد موجودیتی که اشاره به آن ارجاع دارد، جمله‏ای که اشاره در آن قرار گرفته است و شناسه متنی که اشاره در آن قرار دارد ذخیره خواهد شد. بعلاوه اینکه، محدوده‏ی اشاره نیز در قالب سه ویژگی شناسه واژه آغازین اشاره، شناسه واژه پایانی اشاره و شناسه هسته اشاره ذخیره خواهد شد. لازم به ذکر است که شماره ارجاع از جداول انواع موجودیت‏هایی که در دنیای واقعی وجود دارند گرفته شده است. (از آنجائیکه تهیه اطلاعات این جدول کاری سخت و زمان بر بوده و از حوزه این پایان‏نامه خارج است، ما به موجودیت‏های ارجاع شده در پیکره لوتوس و برخی از اطلاعات در دسترس اکتفا نموده‏ایم). نکته‏ی مهم دیگر اینکه اطلاعات مربوط به اشاره، در اشاره‏هایی که از بیش از یک واژه تشکیل شده‏اند، از هسته واژه گرفته شده است.
جدول4-۲: بانک اطلاعاتی سیستم کشف اشاره؛ جدول اشاره‏ها
Tbl_Markables
Markable_ID
Primary Key
شناسه اشاره
Begin_Word_ID
Foreign key
شناسه واژه آغازین اشاره
End_Word_ID
Foreign key
شناسه واژه پایانی اشاره
Head_Word_ID
Foreign key
شناسه واژه هسته
Mention_Type
Attribute
نوع اشاره*
Entity_Type
Attribute
نوع موجودیت*
Entity_Sub_Type
Attribute
نوع موجودیت*
Entity_Class
Attribute
نوع کلاس موجودیت*
Entity
Attribute
شماره