اولین الگوریتمی که در این سری از پست‌ها به آن می‌پردازیم، الگوریتم K- nearest neighbours یا به اختصار k-NN نام دارد. این الگوریتم  یکی از ساده‌ترین الگوریتم‌های یادگیری ماشینی است و به دسته‌ای از این الگوریتم‌ها به نام الگوریتم‌های classification (طبقه‌بندی) تعلق دارد. الگوریتم‌های classification در یادگیری ماشینی و آمار، الگوریتم‌هایی هستند که مشخص می‌کنند با توجه به یک مجموعه‌ی داده موجود و مورد استفاده به منظور آموزش که شامل مشاهداتی است که عضویتشان در یک دسته موجود است، یک مشاهده جدید به کدام یک از مجموعه دسته‌ها( زیرجمعیت‌ها) تعلق دارد. این الگوریتم در دسته‌ای از الگوریتم‌های یادگیری ماشین به نام یادگیری با نظارت قرار می‌گیرد.

این الگوریتم را با یک مثال فرضی ساده در R بررسی می‌کنیم. در قدم اول دو گروه نقطه  به نام‌های a و b با استفاده از تابع sample در R می‌سازیم. دستور set.seed باعث می‌شود که با وجود تصادفی بودن تابع sample، نتایج یکسانی با نتایج این پست داشته باشید.

set.seed(12345)
a <- cbind(sample( x = seq(1,3 , 0.05) , 10 ) , sample( x = seq(0,2.5, 0.05) , 10))
b <- cbind(sample( x = seq(6,8 , 0.05) , 10 ) , sample( x = seq(5,8, 0.05) , 10))

این دو گروه را تبدیل به یک دیتافریم به نانم df می‌کنیم و با دستورات زیر روی یک نمودار رسم می‌کنیم:

df <- data.frame(rbind(a ,b) )
df <- cbind(df ,rep(c("a" , "b") , c(10,10) ))
colnames(df) <- c("x" , "y" , "class")
library("ggplot2")
qplot(x , y , data = df , asp = 1)

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

اگر کاری کنیم که نقاط به حسب تعلق به مجموعه‌ی a یا b رنگ‌های متفاوتی داشته باشند می‌توانیم ببینیم که نقاط هر گروه روی نمودار نزدیک به هم قرار دارند:

حال نقطه‌ای با مختصات (۵،۶) را در نظر بگیرید، این نقطه در گروه a قرار دارد یا b ؟ با کد زیر فاصله نقطه (۵،۶) از باقی نقاط را با فرمول فاصله اقلیدسی پیدا می‌کنیم:

eeuc.dist <- function(x1 , x2) (sqrt(((x1[1] - x2[,1]) ^ 2) + (x1[2] - x2[,2]) ^ 2)) 

res <- data.frame(eeuc.dist(c(5,6) , df[,1:2]) , df$class)
colnames(res) <- c("distance" , "class")

و با دستور زیر نقاط حاصل در دیتافریم res را با توجه به میزان فاصله‌شان از نقطه  (۵،۶) مرتب می‌کنیم:

res <- res[order(res$distance),]

مشاهده‌ می‌شود که نقاط واقع در گروه B با نقطه (۵،۶)  فاصله کمتری دارند. در واقع نزدیک‌ترین همسایه‌های نقطه (۵،۶)  در گروه B قرار دارند، پس می‌توان نتیجه گرفت که این نقطع در گروه B قرار دارد. اساس الگوریتم k-NN همین است.  K-NN مخفف Kتا نزدیکترین همسایه است. در این الگوریتم تعداد K عدد از نزدیکترین نقاط به نقطه‌ی داده مورد نظر انتخاب می‌شود و نقطه‌ی مورد نظر به گروهی تعلق دارد که اکثریت k نزدیکترین همسایه‌ی آن در آن قرار دارند. معروفترین پکیج R که تابعی دارد که الگوریتم k-NN را اجرا می‌کند پکیج class نام دارد. این پکیج که احتمالا همراه R به صورت پیشفرض روی سیستم شما نصب است مجموعه‌ای از ابزارهای طبقه‌بندی را در خود جای داده است.

اجرای الگوریتم k-NN در R

برای این الگوریتم نخست پکیج class را فراخوانی کرده و سپس از تابع knn موجود در آن به صورت زیر استفاده می‌کنیم:

حاصل کد بالا برداری است که نشان می‌دهد هر مشاهده از داده‌های آزمایشی به کدام گروه یا طبقه‌بندی تعلق دارد. مثال ساده‌ی اول پست را برای دو نقطه (۶،۷) و (۳.۵،۵) با دستور knn امتحان می‌کنیم:

library(class)

result <- knn(train = df[,1:2], test =matrix(c(3.5 , 6 , 5 , 7) , nrow = 2), cl = df[,3], k = 3)
result
[1] a b
Levels: a b

حاصل کد نشاندهنده‌ی این است که نقطه (۶،۷) به گروه b و (۳.۵،۵) به گروه a تعلق دارد.

انتخاب k مناسب

یکی از مهمترین مسايلی که در هنگام استفاده از این الگوریتم پیش می‌آید این است که این K باید چه عددی باشد؟ نقطه‌ی شروع انتخاب K جذر تعداد داده‌های دیتاست تمرینی است. مثلا در مثال بالا ما ۲۰ نقطه تمرینی داشتیم، پس می‌توان K را برابر ۴ قرار داد. انتخاب k خیلی کوچک باعث می‌شود که داده‌های پرت تاثیر زیادی روی الگوریتم بگذارند و از طرف دیگر k بسیار بزرگ ممکن است همواره باعث انتخاب پرجمعیت‌ترین طبقه توسط الگوریتم شود. معمولا برای استفاده از این الگوریتم از همان k مساوی با مجذور تعداد داده‌های تمرینی شروع می‌کنند و یک واحد یک واحد به بالا حرکت کرده و دقت الگوریتم را می‌سنجند تا بهترین k  بدست آید.

مثالی با داده‌های واقعی

برای این پست، مجموعه داده‌ای در نظر گرفته‌ام که مربوط به مقاله‌ای با موضوع تشخیص پر یا خالی بودن اتاق ار طریق اندازه‌گیری نور، رطوبت، دما و میزان co2 آن است. در این مجموعه داده اتاق‌های خالی با ۰ و اتاق‌های پر با ۱ مشخص شده‌اند. داده را از اینجا دریافت کنید. داده را در R می‌خوانیم و ستون‌های موردنظر آن را در یک دیتافریم با نام df ذخیره می‌کنیم :

df <- as.data.frame(read.csv("datatest.txt" , header = TRUE)  )
View(df)
df <- df[, -c(1,6)]

هر ستون داده واحدی جداگانه دارد که برای استفاده از الگوریتم k-NN نخست نیاز است که این ستون‌ها را نرمالایز کنیم تا همسان شوند ( در واقع کاری کنیم که تمامی ستون‌ها مقادیری بین ۰ و ۱ داشته باشند.):

normalize <- function(x) { return((x - min(x)) / (max(x) - min(x)))}
dfn <- apply(df[, -5] , 2 , normalize)
dfn <- as.data.frame(cbind(dfn , df[,5]))

یک نمونه ۵۰۰ تایی از این داده را به عنوان داده‌های تمرینی و نمونه ۵۰۰ تایی دیگری را به عنوان داده‌های آزمایشی جدا می‌کنیم ( در این مرحله ستون آخر که شامل کلاس هر ردیف از داده‌ها یا در اینجا پر و یا خالی بود اتاق است را نیز جدا می‌کنیم و در یک بردار ذخیره می‌کنیم):

set.seed(12345)
library(dplyr)
t <- sample_n( dfn , 1000)
test <- t[1:500,]
train <- t[501:1000,]
test_class <- test$V5
train_class <- train$V5
test <- test[,-5]
train <- train[,-5]

سپس الگوریتم را با k = 22 که نزدیک به جذر ۵۰۰ است اجرا می‌کنیم و حاصل را که یک بردار است در برداری به نام result ذخیره می‌کنیم:

library(class)
result <- knn(train = train , test = test , cl = train_class , k =22)

بررسی دقت الگوریتم:

تا اینجا برداری داریم که حاوی پیش‌بینی‌های الگوریتم k-NN درباره‌ی پر یا خالی بودن اتاق‌ها با توجه به مشخصات‌ آنها است. با توجه به این که پر یا خالی بودن اتاق‌ها را از قبل می‌دانستیم و در یک بردار ذخیره کرده بودیم، برای این که ببینیم الگوریتم تا چه حد دقیق بوده بردار result را با بردار test_class با کمک یک تحلیل آماری به نام جدول پیشایندی که با نام‌های contingency table یا cross tabulation نیز شناخته می‌شود بررسی می‌کنیم. برای این کار از تابع CrossTable در پکیج gmodels استفاده می‌کنیم:

library(gmodels)
CrossTable(x = test_class , y = result)

حاصل این کد در R جدول زیر است:

تحلیل جدول بالا نسبتا ساده است. عدد ۳۰۴ در خانه ردیف اول و ستون اول، نشان می‌دهد که ۳۰۴ اتاق خالی داشته‌ایم که الگوریتم k-NN به درستی آنها را به عنوان اتاق خالی شناسایی کرده است. عدد ۱۸۱ در خانه ردیف دوم ستون دوم نشان‌دهنده‌ی ۱۸۱ اتاق پر است که الگوریتم باز هم به درستی آنها را شناسایی کرده است. ۱۳ اتاق خالی به اشتباه به عنوان اتاق‌های پر و ۲ اتاق پر به عنوان اتاق خالی شناسایی شده‌اند. با جمع زدن مقادیر ۰.۶۰۸ (درصد اتاقهای خالی که به درستی شناسایی شده‌اند) و ۰.۳۶۲ (درصد اتاقهای پر که به درستی شناسایی شده‌اند) به دقت ۹۷ درصدی برای الگوریتم می‌رسیم که دقت بسیار مناسبی است. آیا با Kهای دیگر می‌توان به دقت‌های بیشتری دست یافت؟ اگر K را در هر مرحله یک واحد افزایش دهیم و دقت آن را اندازه‌گیری کنیم و روی نمودار ببریم به نمودار زیر می‌رسیم:

مشاهده می‌شود که در این مثال تا K برابر ۲۷ دقت تقریبا ثابت مانده و بعد از آن به تدریج کمتر شده است. به طور کلی الگوریتم k-NN باوجود سادگی می‌تواند دقت بالایی داشته باشد، به همین دلیل در موارد بسیاری مورد استفاده قرار می‌گیرد.

منبع داده‌ها:

Accurate occupancy detection of an office room from light, temperature, humidity and CO2 measurements using statistical learning models. Luis M. Candanedo, Véronique Feldheim. Energy and Buildings. Volume 112, 15 January 2016, Pages 28–39.

پست‌‌های این سری:

یادگیری ماشینی در R — بخش اول، مقدمه

یادگیری ماشین در R — بخش یک و نیم، طبقه‌بندی الگوریتم‌های یادگیری ماشینی

نوشته یادگیری ماشینی در R — بخش دوم، الگوریتم k-NN اولین بار در use R. پدیدار شد.