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

کنيم.

ميزان شباهت

2.2.3 .تشابه معنايي بين کلمات
در روش مورد بررسي توجه بر روش هاي اندازه گيري بر پايه مجموعه است، زيرا اين روش ها انواع گسترده اي از متون را پوشش مي دهند متوني که در دنياي واقعي استفاده مي شود در حالي که در روش هاي بر پايه دانش به اين نکته توجه نشده است.
PMI-IRيک روش ساده براي محاسبه شباهت متني مجموعه اي از کلمات است که با استفاده از اطلاعات نقطه به نقطه متقابل به صورت زير تعريف مي شود

w_1وw_2کلمات و p(w_1 ANDw_2) احتمال رخ داد توامان دو واژه است. اگر دو کلمه از نظرآماري مستقل باشند و در غيراينصورت امكان پديدار شدن همزمان را با هم در متن دارند و.
PMI-IR توسط موتور جستجوگر آلتاويستا55 براي جستجو نحوي و محاسبه احتمالات استفاده مي شود. در ساده ترين حالت دو کلمه هنگامي که در يک سند يافت شوند، احتمال رخ داد همزمان را دارند. اين احتمال با بازيابي اسناد قابل اندازه گيري به صورت تقريبي است.

تعداد متوني است که حاوي کلمه x بوده اند.
روش رخ داد همزمان مرتبه دوم (SOC-PMI)PMI56 ليستي از کلمات همسايه با دو کلمه مورد نظر در يک مجموعه بزرگ را، بر اساس اطلاعات متقابل نقطه به نقطه مرتب مي کند.
مزيت ديگر اين روش اين است که شباهت ميان دو کلمه در هر جاي متن نيز مي توان اندازه گيري کرد. حتي اگر در کنار هم نباشد. تنها کافي است کلمات همسايه مشابه داشته باشند.
مزيت ديگر اين روش (PMI-IR ) اين است که شباهت ميان دو کلمه در هرجاي متن نيز مي توان اندازه گيري کرد. حتي اگر در کنار هم نباشند. تنها کافي است که کلمات همسايه مشابه داشته باشند.
در اين روش از مجموعه ملي بريتانيا (BNC) به عنوان يک منبع براي متون استفاده مي شود. کلماتي که در هر دو فهرست مشترک است ليست شده و جمع ارزش PMI ( از ليست مقابل) براي محاسبه براي بدست آوردن نسبت ارزش معنايي محاسبه مي شود. تابع نقطه به نقطه اطلاعات متقابل براي کلماتي که دارند، تعريف مي شود.
فرمول 3-3 fᵗ(〖 t〗_i ) تعداد دفعاتي است که ti در مجموعه ظاهر مي شود. تعداد دفعاتي را که tiو w در يک قاب57 ظاهر مي شود را نشان مي دهد. mتعداد کل توکن ها در مجموعه است. براي کلمه w مجموعه کلماتX^w به صورت زير تعريف مي شود.

قاعده کلي برايβ به صورت زير است
فرمول 3-4
μ يک مقدار ثابت است که در اين روش 5/6 در نظر گرفته شود. μ با اندازه مجموعه رابطه مستقيم دارد. هر چه μ کوچکتر باشد کلمات مهمتر ممکن است ناديده گرفته شود.
تابع مجموعPMI، β کلمه w1 نسبت به کلمات ديگر به صورت زيرتعريف مي شود.
فرمول 3-5
اگر تمام مقادير مثبت PMIبراي کلمات مجموعه درنيز هستند. به عبارت ديگرکلماتي که از نظر معنايي به نزديک باشند. مطمئنا در ليست کلمات هم معني نيز هستند.
مقدار 58بايد مقداري بزرگ تر ازيک باشد. پس تابع مجموعبراي نسبت به با برابرو براي نسبت به با 3 برابر . در نهايت تابع شباهت معنايي PMIبين دو کلمه و به صورت زير تعريف مي شود]23[.
فرمول 3-6
الگوريتم 3 نحوه نرمال سازي مقادير بدست آمده از را نشان مي دهد.
الگوريتم 3. نرمالسازي محاسبات شباهت معنايي

مثال زير روند کار را توضيح مي دهد.
با استفاده از روش توضيح داده در بالا ميزان تشابه معنايي دو کلمه car و automobile در 12 جمله جدول3-1 محاسبه می شود.
جدول 3-1 -12 جمله به عنوان نمونه داده
1
pursuit accident claim car driver exclude
2
soak motorist company car driver risky
3
company car driver tend travel farther
4
job engineer disappear fall mechanical engineer car industry worst affect
5
Sign recession car industry
6
brightest engineer moment car industry
7
yugoslavia benefit direct investment automobile industry
8
acreage expand emergence automobile industry
9
automobile industry among hardest hit recession
10
automobile industry largely male force
11
component supplier automobile industry expand
12
client industry manufacturer component automobile industry

ft(ti) تعداد تکرار کلمات اصلي محاسبه مي شود.( جدول3- 2)

جدول 3- 2 – تعداد تکرار کلمات اصلی
ti
f t(ti)
ti
f t(ti)
disappear
1
worst
1
yugoslavia
1
soak
1
Pursuit
1
fall
1
brightest
1
supplier
1
travel
1
company
2
Benefit
1
recession
2
risky
1
farther
1
Sign
1
car
6
male
1
investment
1
accident
1
industry
10
affect
1
force
1
mechanical
1
job
1
claim
1
client
1
among
1
Tend
1
moment
1
hardest
1
engineer
3
component
2
automobile
6
manufacturer
1
emergence
1
expand
2
direct
1
driver
3
hit
1
exclude
1
Largely
1

در مرحله بعد براي همهها براي دو کلمه مورد نظر محاسبه مي شود. قاب با طول 11 کلمه(5±) براي اين در نظر گرفته شده است.( جدول3- 3)

جدول 3-3 – محاسبه برای همه کلمات جدول 3-2
ti
fb(ti, W1)
ti
fb(ti, W2)
brightest
1
acreage
1
accident
1
Emergence
1
affect
1
direct
1
motorist
1
hit
1
disappear
1
largely
1
worst
1
yugoslavia
1
pursuit
1
supplier
1
soak
1
benefit
1
fall
1
recession
1
travel
1
male
1
risky
1
Investment
1
recession
1
industry
7
company
2
force
1
sign
1
client
1
farther
1
hardest
1
m
echanical
1
Component
2
claim
1
expand
2
tend
1
manufacturer
1
industry
3
Among
1
moment
1

engineer
3

exclude
1

driver
3

تابع اطلاعات متقابل نقطه به نقطه (PMI ) برايti ها يي که بر اساس فرمول3-3 محاسبه مي شود. (جدول3-4)

جدول 3- 4- مفدار تابع اطلاعات متقابل نقطه به نقطه برای تمامی مقادیر با
Xi (also ti)
f pmi(ti, W1)
Yi (also ti)
f pmi(ti, W2)
motorist
3.544
emergence
3.544
disappear
3.544
direct
3.544
worst
3.544
acreage
3.544
pursuit
3.544
hit
3.544
soak
3.544
largely
3.544
travel
3.544
yugoslavia
3.544
brightest
3.544
supplier
3.544
fall
3.544
benefit
3.544
risky
3.544
male
3.544
company
3.544
investment
3.544
sign
3.544
among
3.544
farther
3.544
force
3.544
accident
3.544
client
3.544
affect
3.544
hardest
3.544
mechanical
3.544
component
3.544
tend
3.544
manufacturer
3.544
claim
3.544
expand
3.544
engineer
3.544
industry
3.029
moment
3.544
recession
2.544
driver
3.544

exclude
3.544

recession
2.544

industry
1.807

و طبق فرمول 3-3 براي محاسب نهايي محاسبه مي شود.
= 24.88 = 24.88
μ در اينجا 0.7 در نظر گرفته شده است. γ نيز براي محاسبات همان مقدار بهينه 3 در نظر گرفته مي شود. دو کلمه recession و industry هر دو جز مجموعه Yiو Xi هستند پس طبق فرمول3-4 و 3-5

3.2.3 . تشابه جملات بر اساس عبارات مشترک
اگر دو متن کلمات مشابه با هم داشته باشند مي توان ميزان مشابهت آنها را بر اساس اين کلمات مشترک بدست آورد (اين کلمات يا همگي در يک موقعيت مکاني هستند، و يا در موقعيت هاي مختلف در جملات ظاهر مي شوند). هستينگز]26 [معتقد بود که اين کلمات ارزش چنداني در اندازه گيري شباهت معنايي جملات کوتاه ندارد. در اين روش براي آنکه از اهميت کم اين معيار چشم پوشي نشود فاکتور وزني آن را کمتر از 5/0 در نظر مي گيريم .
روش کار به اين صورت است که ، فرض کنيم P و R دو جمله با کلمات مشابه هستند و|R||P|، تمام کلمات مشابه در دو جمله استخراج مي شوند. اگر X مجموع کلمات مشابه درP وY مجموع کلمات مشابه در R باشد هر کدام از اين مجموعه ها ترتيب مخصوص به خود دارند. از آنجا که تعداد کلمات P بيشتر ازR است و در اصطلاح Pبزرگتر ازR است. به کلمات موجود در مجموعه X به ترتيب موقعيتشان در جمله وزني از1 تا δ اختصاص مي دهيم و همين وزن به کلمات مجموعه Y الحاق مي شود. سپس ميزان شباهت اين جمله بر اساس دستور زير محاسبه مي شود.

فرمول 3-7
به عنوان مثال دو جمله را در نظر بگيرييد
P: Einstein was a German-born theoretical physicist
R: The theoretical physicist – Einstein lived at 19 century
X = {Einstein, theoretical, physicist} X= {1, 2, 3}
Y= {theoretical, physicist, Einstein} Y= {2, 1, 3}
با توجه به فرمول 3-7
4.2.3 . شباهت کلي جملات
Islam روش خود را در6 مرحله ارائه خلاصه کرده است:
ابتدا تمام کلمات اضافه در جملات براي پيدا کردن کلمات کليدي پاک مي شود اگر P و R دو جمله مورد نظر باشند m کلمه از P و n کلمه از R کلمات اصلي ما را تشکيل مي دهند. (حذف حروف و کلمات اضافه)

در اين مرحله کلمات مشابه در اين مجموعه علامت گذاري مي شوند. δ کلمه مشابه درR وP کنار گذاشته شده و بقيه براي بررسي نگه داشته مي شود. اگر m=δبود به مرحله 6 ميرويم. در غيراين صورت δm به ترتيب ادامه ميدهيم.

ماتريس تشابه خطي دو مجموعه به صورت زيرتشکيل مي شود. هر α_ij در a به صورت زير محاسبه مي شود :
اگر p_i ϵ P، کاراکتر داشته باشد و هر 〖 r〗_j ϵ R، کاراکتر وبه صورتي کهطول کوتاه ترين کلمه و بلندترين کلمه مشترک است]23 [.

فرمول 3-8

مثال زير اين مرحله را توضيح مي دهد
=“allmileage_make_maxkm”
=“make_minmile_distance_possible_take”
اجرا مرحله اول
= {all, mileage, make, max, km} m=5
= {make, min, mile, distance, possible, take} n=6
اجرا مرحله دوم
= {all, mileage, max, km}
= {min, mile, distance, possible, take}

به عنوان نمونه ميزان شباهت بين possible و mileageاينگونه محاسبه شده:

مطابق فرمول 3-8
ماتريس ، ماتريس تشابه معنايي از روي الگوريتم 3 تشکيل مي شود.

ماتريسM از طريق دو ماتريس بالابه صورت زيرتشکيل مي شود.
فاکتور وزني شباهت خطي وفاکتور وزني شباهت معنايي است. که . هر کدام از اين ضرايب اگر صفر در نظر گرفته شوند ماتريس مربوطه در محاسبه ماتريس مجموع M لحاظ نمي شود. اگر اين ضرايب هر دو 0.5 باشند يعني شباهت خطي و معنايي هر دو به يک ميزان اهميت دارند. عنصر با ماکزيمال ارزش، در ماتريس Mاستخراج مي شود.
اگر اين مقدار بزرگتراز صفربود به ليست اضافه مي شود،. سطر و ستون مربوط به آن از ماتريس حذف مي شود. اين کار تا زماني که و يا ادامه پيدامي کند.
6- تمام مقاديرو هم جمع مي شوند . طبق فرمول ميزان شباهت چند گانه با ضرب در مجموع m و n و تقسيم بر دو برابر ضريب آنها به مقداري بين صفر و يک بالانس مي شوند. در اين روش مي توان از هرکدام از روش ها و مقادير شباهت صرفه نظر کرد. مثلا از معيار شباهت کلمات متداول با صفر اعلام کردن صرفه نظر کرد و يا اينکه با صفر در نظر گرفتن اهميت نحوي را ناديده گرفت]23 [.

5.2.3 . نمونه توضيح روند کار
دو
تکه متن مورد نظر براي مقايسه و محاسبه ضريب شباهت به روش فوق با R وP مشخص شده است.

مرحله 1 : جدا کردن کلمات اصلي و مشخص
m=5
n=6
مرحله 2 : کلمه هايي که در هر دو مجموعه مشترک است حذف مي شوند.

مرحله 3 : ماتريس تشابه خطي با محاسبه تشابه خطي تک تک کلمات بر اساس فرمول 3-8 تشکيل مي شود.

مرحله 4 :ماتريس تشابه معنايي نيز تشکيل مي شود.

مرحله 5 : ماتريس M از طريق دو ماتريس قبل به کمک فرمول زير تشکيل مي شود.

سپس مقدار ماکزيمم به مجموعه ρ اضافه مي شود و سطر و ستون آن حذف مي شود. اين کار تا زماني که و يا ادامه پيدا مي کند.

ρ = {0.771}

ρ = {0.771, 0.447}

ρ = {0.771, 0.447, 0.445}

ρ = {0.771, 0.447, 0.445, 0.154}

مرحله 6: و در نهايت محاسبه ضريب تشابه ترکيبي براي دو جمله R وS

فرمول3-9

3.3. خوشه بندي داده ها
1.5.2. الگوريتم K-means
با توجه به ]27 [الگوريتم K-means يک الگوريتم ساده تکرار شونده است، که مجموعه داده ها را به K خوشه تقسيم مي کند. اين الگوريتم در سالهاي مختلف در زمينه هاي گوناگون توسط افرادي مانند LIoyd (1982،1957)، Forgey (1965)، Friedman و Rubin (1967) و McQueen (1967) توسعه يافته است. الگوريتم روييک مجموعه از بردار هاي d بعدي تعريف مي شود، کهو نشان دهنده i امين نقطه داده است.
تکنيک مورد استفاده براي انتخاب نمونه هاي اوليه براي تشکيل K دسته، شامل نمونه گيري تصادفي از مجموعه داده هاست. سپس الگوريتم دو قدم زير را به صورت مکرر انجام مي دهد.
گام اول، تخصيص داده:
هر نقطه داده ها به نزديک ترين مرکز جرم اختصاص داده مي شود. اختصاص داده با استفاده از يک سري روابط قراردادي و دلخواه انجام مي گيرد. اين فرآيند منجر به دسته بندي داده ها مي شود.
گام دوم، جابجايي دسته ها:
نمايندگي در دسته به مرکزي ترين نقطه در دسته اختصاص داده مي شود. اگر ميزان احتمال داده ها يک اندازه باشد. پس جابجايي


دیدگاهتان را بنویسید