الگوریتم نامه

دنیای برنامه نویسی و هوش مصنوعی، بررسی الگوریتم های موجود، همفکری

الگوریتم نامه

دنیای برنامه نویسی و هوش مصنوعی، بررسی الگوریتم های موجود، همفکری

اسم الگوریتم: KNN یا ( K تا ) نزدیک ترین همسایه.


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


این الگوریتم به چه دردی خواهد خورد؟

طبقه بندی کردن کلا" برای ما مهم بوده و هست. ما غالبا" در حال طبقه بندی و مقایسه ی پدیده های دور و بر خودمون هستیم. غذای خوب، غذای شرقی، آدم حساس، فیلم تاثیر گذار..

معمولا" هروقت ما نیاز داریم یک چیزی رو طبقه بندی کنیم و ایده ای نداریم، سعی میکنیم ازمقایسه اون موضوع با داده های قبلیمون به نتیجه برسیم. منطقی به نظر میاد نه؟ موسیقی میتونه یک مثال ملموس باشه. شما با شنیدن یک آهنگی که قبلا" نشنیدید، با توجه به داده های قبلی ذهنتون سعی میکنید اونو توی یک گروه بگنجونید. میگید سنتی، یا کلاسیک یا پاپ. این که شما یک چراغ راهنمایی با شکل و شمایل کاملا" جدید رو توی یک کشور دیگه میبینید و میشناسید، دلیلش اینه که شما چراغ راهنما زیاد دیدید. بینشون به یکسری جمع بندی و نتیجه رسیدید که آها، اسمش، شکلش، جایی که معمولا" میشه اونو دید، کاربردش و غیره.


برگردیم به الگوریتم KNN و ببینیم چطور میتونه مارو کمک کنه توی طبقه بندی کردن. فرض کنید یک جعبه داریم پراز فیلم با ژانر و محتوای مختلف و از قبل مشخص شده. من به شما یک نمونه فیلم که تا به حال ندید میدم و از شما میخوام 6 تا از شبیه ترین فیلم های موجود رو برای من رو پیدا کنید. بعد توی اون 6 تا ببینید اکثرا" توی چه ژانری هستند. با این کار،من میتونم بهترین طبقه بندی رو با توجه به طبقه بندی های قبلی برای فیلمم انجام بدم.

توی این مثال، K همون 6 هست و همسایه ها، همون شبیه ترین فیلم ها.


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


فاصلهٔ دو نقطهٔ p و q اندازهٔ پاره‌خطی‌ست که آنها را به هم متصل می‌کند (pq vector). در مختصات دکارتی اگر:


p = (p۱p۲... pn)
q = (q۱q۲,...qn)


دو نقطه در فضای اقلیدسی n بعدی باشند، آنگاه فاصلهٔ بین آنها به صورت زیر تعریف می‌شود:

فاصله اقلیدسی


برای توضیح رابطه ی بالا، بهتره برگردیم به مثال فیلم. به نظر شما چه خصوصیاتی از یک فیلم رو میشه با دیگری مقایسه کرد؟


خصوصیت

مثال

زبان

فرانسوی

کارگردان

خانوم x

نویسنده

آقای y

سال تولید

1990

مدت

90 دقیقه

تعداد هنرپیشه ستاره

4

تعداد جایزه بین المللی

7

تعداد صحنه های احساسی

2

تعداد صحنه های اکشن

10

..

 



حالا ما میتونیم همه خصوصیت های یک فیلم رو کنار هم به شکل یک بردار ببینیم و تعداد اونها فضای n بعدی ما رو تشکیل میده. یک مثال برای فضای دو بعدی میتونه به شکل زیر باشه:



p = (تعداد صحنه های احساسیتعداد صحنه های اکشن) = (1, 7)
q = (تعداد صحنه های احساسیتعداد صحنه های اکشن) = (5, 2)




دستگاه مختصات دکارت


در نتیجه طبق تعریف، اندازه پاره خط pq vector خواهد بود:


((۷-۲)2 + (۱-۵)2)1/2 = ۶.۷ cm


درواقع ما با تبدیل کردن خصوصیات فیلم به بردار، می تونیم ازریاضیات بهره ببریم و فاصله فیلم خودمون رو از فیلم های موجود توی یک دستگاه دکارتی چند بعدی (توی مثال فیلم، 9 بعدی) بدست بیاریم. 


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

 

برگردیم به یک مثال عملی.

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


گراف قیمت مس
تصویر 1: نمونه یک عکس با داده های عددی


فرض نویسنده بر اینه که شما دانش اولیه راجع به پردازش تصویر دارید. اولین کاری که نیاز داریم انجام بدیم، بریدن اون تیکه عکس هست که عدد مورد نظر ما توی اون قرار داره. چون تصویردو بعد داره، نقطه شروع تصویر (0,0) و نقطه پایان عکس (m,n) خواهد بود که m نشون دهنده طول عکس و n عرض عکس رو نشون میده. باتوجه به گرافی که در دست داریم، نقطه شروع (15, 136) و نقطه پایان (28, 179) خواهد بود.



تصویر 2: قسمتی از تصویرکه داده مورد نظر ما درآن قرار دارد.




بسته به اینکه چه زبان برنامه نویسیی رو برای پیاده سازی این الگوریتم استفاده میکنید، روش بریدن تصویر و کار با اون هم متفاوت خواهد بود. ما توی این مقاله از زبان پایتون نسخه 2.7.1 استفاده می کنیم. برای کار با تصویر هم از تابخانهPIL یا همون
Python Imaging Library 
نسخه 1.1.7 استفاده خواهیم کرد.




لطفا" به کد زیر دقت کنید
from PIL import Image
im = Image.open(graphPath)
im = im.crop((136,15,179,28))




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



تصویر 3: نمونه یک ناحیه بریده شده از عکس اصلی

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


لطفا" به کد زیر دقت کنید


for i in xrange(6):
            img2 = im.crop(((i*7)+1,(3),((i+1)*7),(12))).convert('1')


همونطور که میبینید، ما نیاز داریم هر بار که توی حلقه میچرخیم، نقطه شروع عکس رو با توجه به طول و عرض هر کاراکتر محاسبه کنیم .


توجه

توی قطعه کد بالا، یک دستور جدید مشاهده میشه به اسم convert و به عنوان ورودی مقدار یک (1) رو به این تابع ارسال میکنیم. در واقع ما با این کارمون خروجی کاراکتر بریده شده رو تبدیل میکنیم به یک عکس دو رنگ سیاه و سفید. همینطوری که توی تصویر4 دیده میشه، توی هر پیکسل فقط یک رنگ خواهیم داشت، سیاه یا سفید:




تصویر 4: نمونه یک عکس که در هرپیکسل فقط رنگ سفیدیا سیاه قرار دارد

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



توجه

با استفاده از کتابخونه ی PIL، ما تونستیم حالت عکس رو تبدیل کنیم به سیاه و سفید. درنتیجه برای ذخیره کردن داده ی یک پیکسل میتونیم از یک بایت استفاده کنیم. همونطور که میدونید یک بایت دارای 8 بیت هست و حداکثر حالاتی که میتونه توی خودش نگه داره، 28 یا 256 حالت هست. یعنی از عدد 0 تا 255. توی این 256 حالت، از سفید مطلق داریم تا سیاهِ سیاه. این لابه لا هم قاعدتا" خاکستری به چشم خواهد خورد.



تصویر 5: طیف رنگ از سفید مطلق به سیاهِ سیاه


با توجه به تصویر 4، برای اینکه خیال خودمون رو راحت کنیم، فرض میکنیم هر پیکسل که عددی بین 0 تا 50 داره، سفید و الباقی سیاه هستند. 




قرارداد

بیایم از این به بعد، هر رنگ سفید رو با 1 و هر رنگ سیاه رو با 0 نشون بدیم. برای مثال عدد 9 که با دست نوشته شده میتونه به اینصورت نوشته بشه:

سایز عکس: 32
* 28

0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000111110100000000
0000000000001111111110000000
0000000000011100011100000000
0000000001111000011100000000
0000000011100000111000000000
0000000011100000110000000000
0000000110000011110000000000
0000000110011111100000000000
0000000111111111100000000000
0000000011100011000000000000
0000000000000011000000000000
0000000000000011000000000000
0000000000000011000000000000
0000000000000011000000000000
0000000000000111000000000000
0000000000000011000000000000
0000000000000011000000000000
0000000000000001100000000000
0000000000000001110000000000
0000000000000000110000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
 





تا این لحظه، ما یاد گرفتیم چطور عکس رو ببریم، اعداد رو جدا کنیم و قرار گذاشتیم هر پیکسل رو با بسته به رنگش با 0 و 1 نمایش بدیم.
برای تبدیل عکس به معادل عددی اون (نمایش با 0 و 1، همونطور که در بالا نمایش داده شد)، ما توی پیکسل های یک عکس میچرخیم و این رشته صفر و یکی رو بوجود میاریم. لطفا" کد زیر رو بررسی کنید:

def stringify(self, img):
        res= []
        sz = img.size
        pix = img.load()
        for j in xrange(sz[1]):
            for i in xrange(sz[0]):
                if(pix[i, j]<50):
                    p = 1
                else:
                    p=0
                res.append(p)
        return res


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


سایز عکس: 9 * 6

طول لیست: 54




[0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]



نکته مهم

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


خوب، سوال اینه که من عدد رو از عکس جدا کردم، اون رو به یک بردار تبدیل کردم، حالا با چه نقاطی باید اون رو مقایسه کنم که به کوتاه تربن پاره خط برسم؟ سوال خوب و مهمیه.
چیزی که نیاز داریم نمونه درست و قابل اعتماد اعداد از 0 تا 9 هست. به زبان ساده، ما باید برای 0 بودن یا 1 بودن، یک معیار یا
خط کش داشته باشیم که بتونیم 0 های مرتبط رو از 0 های بی ربط شناسایی کنیم. درست مثل کاری که مغز ما انجام میده. وقتی ما مکررا" موسیقی خوب گوش میدیم و به اون عادت میکنیم، وقتی یک قطعه آهنگ ضعیف میشنویم، نا خودآگاه متوجه میشیم یک جای کار ایراد داره. این همون راه کاریه که برای تشخیص عدد از غیر عدد میشه بکار برد.

برای این کار، اول میایم و نمونه 0 تا 9 صحیح رو استخراج و تبدیل به رشته میکنیم:




                        

: 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0
: 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0
.
.
: 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0
: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0



میشه نتیجه این تبدیل رو توی یک فایل ذخیره کنیم. اونوقت هروقت که خواستیم عملیات مقایسه رو انجام بدیم، کافیه از روی فایل، محاسبات قبلیمون رو وارد حافظه کنیم و نیازی نیست دوباره از نو محاسبه کنیم.

تابع زیر کل مراحل مقایسه رو نشون میده. ما برای کار با ماتریس ها، از کتابخانه ی numpy استفاده کردیم که بسیار غنی و قویست:




1 def GetDigits(self, graphPath):
2       
3        result = []
4        with open('{0}\\trainset\\trainset.pickle'.format(os.getcwdu()),'r') as f:
5            ds =  pickle.load(f)
6        instance = ImageEngine().convertImageToVector(graphPath)
7        dataSet = []
8        labels = []
9        for item in ds:
10            dataSet.append(item[0])
11            labels.append(item[1])
12
13        dataSetSize = array(dataSet).shape[0]
14        for d in instance:
15            diffMat = tile(d, (dataSetSize,1)) - dataSet
16            sqDiffMat = diffMat**2
17            sqDistances = sqDiffMat.sum(axis=1)
18            distances = sqDistances**0.5
19            sortedDistIndicies = distances.argsort()
20            k = 1
21            classCount={}
22            for i in range(k):
23                voteIlabel = labels[sortedDistIndicies[i]]
24                classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
25                sortedClassCount = sorted(classCount.iteritems(), key = operator.itemgetter(1), reverse=True)
26            result.append('.' if sortedClassCount[0][0]== -1 else sortedClassCount[0][0])
27        converted = ''
28        for item in result:
29            converted+=str(item)
30        return converted




  • سیداحمد موسوی

نظرات (۱۹)

  • علیرضا زاد
  • با سلام خدمت شما استاد،محقق و مهندس گرامی

    لطفا الگوریتم KNN یا ( K تا ) نزدیک ترین کارواش  را هم بیان فرمایید.

    با تشکر از مطالب مفید و آموزندتون

    با سلام

    در قسمت اول توضیح الگوریتم مثل اینکه اندازهٔ بردار pq رو برای مثال فیلم‌ها اشتباه نوشتید؟ شما دو مولفهٔ هر نقطه رو از هم کم کردید که باید مولفه های متناظر رو باید از هم کم میکردید. یا من اشتباه می‌کنم؟

  • سیداحمد موسوی
  • ممنون جناب غلامی.
    مطلب اصلاح شد.
    مطلبتون فوق العاده خوب و مفید بود
    خدا پدر و مادرتو بیامرزه
    مطلبتون فوق العاده بود.
    خیلی ممنون.
  • سعید رحمانی
  • با سلام
    بسیار عالی و کاربردی
    پایدار باشید
    سلام ممنون توضیحاتتان خیلی خوب بود اگر در دسته بندی  درخت تصمیم C4.5 هم کار کردین لطفا راهنمایی28.با سپاس
  • سیداحمد موسوی
  • سلام. اگر فرصتی بدست بیارم حتما. در ضمن نیاز به مطالعه هم دارم
    عالی بود مفهوم کلیش خوب بود متوجه شدم اما در مورد کد نه
    پاسخ:
    سلام محمد جان. بزودی کل سورس کد رو میگذارم توی بلاگ. اونوقت اگر سوال داشتی درخدمتم.
    فرق بین ویژگی پایدار با ویژگی ناپایدار تو تقسیم بندی داده به چه معناست؟ممنم میشم کسی جوابمو بده
    واقعا خیلی ساده  و قابل فهم الگوریتم knn رو گفتین سپاس
    اگر درباره شبکه عصبی و تبدیل موجک هم به همین روانی مطلب دارید برام میل بزنید یا اینجا بزارید ممنون میشم
    سلام خسته نباشید
    ببخشید میخواستم ببینم مقدار k رنج خاصی میتونه باشه؟ یعنی مثلا از 2 به بالا یا از 3 به بالا؟
    خدایی عالی بود
    دمت گرم
    عالی...
    سلام. عالی بود. تیکه اولش خیلی به درد من خورد
    پاسخ:
    سلام. شرمنده من خیلی دیر دیدم پیغام شما رو. کار بجایی رسید؟
    سلام وقتتون بخیر
    میخواستم بدونم درالگوریتم knnورودی هاکه مشخصه خودمون داریمشون خروجی ها چیه؟لطفاجواب بدین خیلی واجبه
    پاسخ:
    سلام. وقتی از knn استفاده میکنیم باید تمام داده ها رو به بردار تبدیل کنیم که بشه با هم مقایسه بشن. در نتیجه خروجی الگوریتم میشه فاصله بردار ورودی با بقیه بردارها. بعد که تمام فواصل بدست اومد نتایج رو از کمترین به زیاد ترین فاصله مرتب (sort) میکنیم  و بعد (K تا) جواب دلخواه رو خواهیم داشت.
    سلام
    ببخشید یه سوال داشتم. خیلی واجبه لطفا جواب بدید
    وقتی که ما سایز تصویری که به برنامه آموزش میدیم 6 * 9 باشه پس قطعا 54 مولفه داریم و میتونیم با عکس های 6 * 9 دیگه مقایسش کنیم. تا اینجا مشکلی نیست.
    ولی اگر ما بخوایم با یه عکس که توش مثلا نوشته 9 و ابعادش 12 * 18 هست مقایسش کنیم تعداد مولفه ها برابر نیستن.
    یکی 54 مولفه داره و دیگری 216 مولفه!
    اگه میشه ساده توضیح بدید چطور باید این دو تصویر با مولفه های نابرابر رو با هم مقایسه کنیم؟
    پاسخ:
    سلام. چند تا نکته:
    ۱- دو نمونه ای که باهم مقایسه میکنید باید توی یک فضای هندسی باشند. یعنی اینکه یا هردو ۶ * ۹، یا هردو ۱۲ * ۱۸. در غیر این صورت، این الگوریتم کار نمیکنه. 
    ۲ - میتونید عکس بزرگتر رو با پردازش تصویر برش بدید تا بشه ۶ * ۹.
    ۳ - اگه جای عدد توی تصویر دومی تغییر میکنه، مثلا یک بار بالاتره، یک بار وسط و بعضی وقتا پایین عکس قرار گرفته، تو این حالت هم نباید از این الگوریتم استفاده کنید. شبکه عصبی مناسب تره.

    سلام وقت بخیر ممنون ازتون

    من کد رو متوجه نشدم اگر امکانش هست راهنمایی کنید

    عااااااااااااااالی بود مطلبتون اجرتون با خدا
    ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
    شما میتوانید از این تگهای html استفاده کنید:
    <b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
    تجدید کد امنیتی