الگوريتم دسته بندي - Artificial Intelligence

lightinstinct · ۰۴-۶-۱۳۸۹, ۱۰:۳۶ قبل از ظهر

سلام.كسي ميدونه اين الگوريتم در كل چه كاري انجام ميده يعني هر مرحله رو ميدونم ولي مثلن ميخوام بدونم اين آرايه هر بار براي هر سند ايجاد ميشه يا واسه همه يه ارايه به سايز kايجاد ميشه ؟يا اينكه چرا اگه مجموع تي اف ها بيشتر از ... اين كار را انجام ميديم؟

تعدادي از تكنيك هاي كلاس بندي آماري و يادگيري ماشيني در روش كلاس بندي در متن كاوي به كار برده مي شود.برخي از اين تكنيك ها عبارتند از :مدل هاي رگرسيون، كلاسه بندهاي بيزي (Bayesian classifiers)،درخت هاي تصميم گيري،كلاسه بندهاي نزديكترين همسايه و ماشين هاي برداري و ...كه ما در اين مقاله به بررسي و تحليل بعضي از اين تكنيك ها مي پردازيم.
الگوريتم KNN: k-Nearest Neighbor))
• D = {D1, D2, …, Dn} مجموعه سندهاي آموزشي است.
• Qسند جديدي است كه قرار است مورد بررسي قرار گيرد.
• TF،term frequency يك عبارت دريك سند است كه به عنوان داده هاي آموزشي پيش پردازش شده است.
• Vمقدار كسينوس شباهت Qو Di است. )به طوري كه i=1,2,…,n)

Algorithm: k-NN_I
Step1: Calculate the TFs of all keywords in Q
Step2: Initialize an empty buffer/array of size k, A[]
/* contains document id/name and similarity value with
the highest k cosine similarity, we call it top-k buffer */
Step3: int count = 0 /* Initialize a counter variable */
Step4: For each document Di in D
If (count <= k)
Calculate v between Q and Di
/* considers only keywords present in both */
Add document name and v into A[]
count++;
Else
If (Sum(TFs) in Di > Min(v) in A[])
Calculate cosine similarity value v between
Q and Di
/* considers only keywords present in both */
If (new v > Min(v) in A[])
Remove document with Min(v) from A[];
Add document Di and new v into A[];
/* Else Skip the document */
Step5: Return the class with highest # of documents in A[]

تحليل الگوريتم :KNN
گام1:وقتي يك سند به عنوان ورودي به برنامه داده مي شود ابتدا TFرا براي همه كلمه هاي كليدي در سند به دست مي آوريم.
گام2:سپس يك آرايه به سايز kدرنظر مي گيريم كه ابتدا خالي است.اين آرايه شامل idو نام و مقدار شباهت هرسند است.
گام 3:يك شمارنده بامقدار اوليه صفر در نطر مي گيريم.counter=0
گام 4:براي هريك ازسندهاي Diدرمجموعه D اگر count<=k مقدار Vبين Q وDiرا محاسبه مي كنيم.(توجه داشته باشيد كه هنگام محاسبه Vفقط كلمات كليدي كه درهردويQوDi ديده مي شوند در نظرگرفته مي شوند.)سپس شمارنده يكي اضافه مي شودو vونام سند در آرايه A[]نوشته مي شود.درغيراين صورت يعني اگرcount<=0نباشداگرمجموع TFهادر سندDi بيشتر از حداقل مقدارV درآرايه A[]باشد مقدار كسينوس شباهت Vبين سندQوDi رامحاسبه مي كنيم. .(باز هم توجه داشته باشيد كه هنگام محاسبه Vفقط كلمات كليدي كه درهردويQوDi ديده مي شوند در نظرگرفته مي شوند.)اگد مقدار جديد Vمحاسبه شده از حداقل مقدار Vدر آرايه A[]بيشتر بود سند را به همراه min(V) از آرايه A[]حذف مي كنيم و سند Qiو مقدار جديد Vرا به A[] اضافه مي كنيم.درغير اين صورت سند را رها مي كنيم.
گام5: كلاسي را كه بيشترين تعداد سند در آرايه A[]را دارد برمي گردانيم.

nameless0059 · ۰۴-۲۷-۱۳۸۹, ۱۰:۲۵ قبل از ظهر

بسم الله الرحمن الرحیم

سلام

آرایه A یک بار ساخته میشه و در آن k همسایه هایی که بیشترین شباهت رو به متن تست دارن نگهداری میکنه. اول همه سند ها رو با مقدار شباهت ها تا جایی که آرایه پر بشه توی اون قرار میده. بعدش برای بقیه سندها هر بار مقدار شباهت رو بدست میاره و اگر از کم ترین مقدار شباهتی که توی آرایه هست بیشتر بود اون کم ترین رو بیرون میندازه و این رو جایگزین میکنه. اینجوری در نهایت داخل آرایه k سندی که بیشترین شباهت رو دارن میمونن.
اما این که چرا چک میکنه مقدار tfها بزرگتر از حداقل شباهت سند داخل آرایه باشه، دقیق نمیدونم ولی فکر میکنم چون اگر کم تر باشه محال خواهد بود که شباهت اون سند بیشتر از کم ترین مقدار شباهت در آرایه بشه.
توی متن توضیح نداده که فرمول شباهت کسینوسی رو با چه مقادیری اعمال میکنه؟
میشه فرمول دقیق محاسبه شباهت بین دو تا سند رو بیارید؟

ممنون

rezaaa · ۰۸-۲۵-۱۳۸۹, ۱۰:۱۰ بعد از ظهر

تخمین گر KNN شبیه به یک دسته بندی کننده Bayesian می باشد.
برای اطلاعات بیشتر اسلاید زیر را دانلود کنید.

LECTURE 8: Nearest Neighbors