خانه / مقالات / داده کاوی و هوش مصنوعی / DT Classification در Matlab ، Weka و RapidMiner

DT Classification در Matlab ، Weka و RapidMiner

در مقاله های قبلی با مفهوم کلاسیفایر DT یا Decision Tree  و طرز کار آن بر روی مجموعه های دلخواه داده در نرم افزار متلب آشنا شدید. در این مقاله هدف این است که با استفاده از نرم افزارهای Weka، RapidMiner و متلب، این الگوریتم را بر روی دیتاست معروف FisherIris اجرا کرده و نحوه کار این الگوریتم را بر روی داده های این دیتاست مشاهده نماییم.
دیتاست Iris حاوی ۱۵۰ نمونه (سطر) و ۴ مشخصه (ستون) و یک کلاس برای گونه های گل زنبق است. یعنی ۳ کلاس (setosa, versicolor,virginica)  که هر یک حاوی ۵۰ نمونه هستند و هر کلاس به نوعی گیاه زنبق یا Iris اشاره می کند. یک کلاس از دو کلاس دیگر بصورت خطی جدایی پذیر است؛ دو کلاس دیگر بصوررت خطی جدایی پذیر نیستند.
در مورد این دیتا ست در مقاله مربوط به اجرای SVM بر روی این دیتاست به طور کامل توضیح داده شده است لذا از بیان توضیحات بیشتر در این مقاله خودداری می شود.
یکی دیگر از الگوریتم های دسته بندی درخت تصمیم است. درخت تصمیم از مجموعه ای از قوانین ساده تشکیل شده است مانند : «اگر طول کاسبرگ کمتر از ۵٫۴۵ باشد، گونه ها را به عنوان setosa دسته بندی کن.» درخت های تصمیم غیر پارامتری هستند زیرا نیاز به هیچ تخمینی از توزیع متغیرهای هر کلاس ندارند.
درخت تصمیم از یک درخت برای ساخت یک مدل پیش بینی (تخمین) استفاده می کند که مشاهدات درباره یک آیتم را به نتیجه گیری هایی درباره مقدار هدف آن آیتم مپ می کند یا نگاشت می دهد. درخت تصمیم یکی از رویکردهای پیش بینانه است که در آمار و دیتا ماینینگ و یادگیری ماشین استفاده می شود. به مدل های درخت که در آنها متغیرهای هدف می توانند مجموعه متناهی از مقادیر داشته باشند درخت های طبقه بندی یا classification trees می گویند.
در ساختار درختها، برگها نشان دهنده لیبل های کلاس و شاخه ها نشان دهنده ارتباط ویژگی هایی هستند که به این کلاس لیبل ها منتج می شود.
درخت به این صورت ساخته می شود که ابتدا data training ها طبقه بندی می شوند مثلا ۵ کلاس داریم که ابتدا همه آنها را به عنوان یک کلاس در نظر می گیریم و پس از دسته بندی داده های این کلاس ها در آخر یک test data اضافه می کنیم و با توجه به تصمیماتی که در نودها گرفته می شود بررسی می کنیم که این داده تست به کدام کلاس تعلق دارد و در کدام برگ قرار میگیرد:
در هر نود درخت یک سوال وجود دارد و هر داده تستی که وارد شود نود سوال را می پرسد و با توجه به سوال تصمیم میگیرد داده به سمت چپ درخت برود یا به سمت راست و به این ترتیب وارد یک نود دیگر شده و در آنجا باز هم سوالی پرسیده می شود که در حرکت داده به چپ یا به راست تصمیم گیرنده است. بنابراین از داده های آموزشی برای ساخت درخت استفاده می کنیم.
دستور classregtree  در متلب یک درخت تصمیم ایجاد می کند.
در ادامه یک درخت تصمیم برای داده های زنبق ایجاد می کنیم و می بینیم که چگونه تقسیم بندی کلاس ها را انجام می دهد.
t = classregtree(meas(:,1:2), species,›names›,{‹SL› ‹SW› });

حال می بینیم که چگونه مناطق ایجاد شده به هر گونه را می توان نمایش داد:
[grpname,node] = eval(t,[x y]);
gscatter(x,y,grpname,›grb›,›sod›)

یک راه دیگر برای نمایش بصری درخت تصمیم ترسیم یک دیاگرام از قوانین تصمیم و انتصابات کلاس ها می باشد یعنی:
view(t);
پس از اجرای کد زیر شکل زیر در خروجی نمایش داده می شود:
load fisheriris
gscatter(meas(:,1), meas(:,2), species,›rgb›,›osd›);

xlabel(‹Sepal length›);
ylabel(‹Sepal width›);
N = size(meas,1);
t = classregtree(meas(:,1:2), species,›names›,{‹SL› ‹SW› });
[grpname,node] = eval(t,[x y]);
gscatter(x,y,grpname,›grb›,›sod›)
در شکل فوق می توان داده های پراکنده هر سه کلاس setosa، versicolour و virginica را مشاهده کرد. در این کد از طول و عرض کاسبرگ به عنوان ویژگی استفاده شده است. در مثالی که بعد از این مثال و در ادامه آورده شده از طول و عرض گلبرگ به عنوان ویژگی استفاده شده است.

با اجرای کد زیر شکلی که در ادامه آمده نمایش داده می شود که در آن مناطقی که به هر گونه نسبت داده شده، visualize شده است.
load fisheriris
gscatter(meas(:,1), meas(:,2), species,›rgb›,›osd›);

[x,y] = meshgrid(4:.1:8,2:.1:4.5);
x = x(:);
y = y(:);
j = classify([x y],meas(:,1:2),species);
gscatter(x,y,j,›grb›,›sod›)

xlabel(‹Sepal length›);
ylabel(‹Sepal width›);
N = size(meas,1);
t = classregtree(meas(:,1:2), species,›names›,{‹SL› ‹SW› });
[grpname,node] = eval(t,[x y]);
gscatter(x,y,grpname,›grb›,›sod›)
برای نمایش درخت در انتهای کد، دستور view(t); را اضافه می کنیم که خروجی آن  بصورت زیر است:
این درخت، از مجموعه قوانینی به شکل SL<5.45 برای دسته بندی هر نمونه به یکی از ۱۹ نود نهایی استفاده می کند. برای تعیین انتصاب نمونه ها از بالاترین نود شروع میکنیم و طبق سوالات پرسیده شده به پیش می رویم. اگر نقطه rule را satisfy کرد به سمت چپ و اگر نکرد به سمت راست می رود. در نهایت به یک نود نهایی می رسید که مشاهدات را به یکی از سه گونه نسبت می دهد.
می توان برای درخت فوق resubstitution error و cross-validation error را با استفاده از کدهای زیر محاسبه کرد:
dtclass = eval(t,meas(:,1:2));
bad = ~strcmp(dtclass,species);
dtResubErr = sum(bad) / N
dtClassFun = @(xtrain,ytrain,xtest)(eval(classregtree(xtrain,ytrain),xtest));
dtCVErr  = crossval(‹mcr›,meas(:,1:2),species, …
‹predfun›, dtClassFun,›partition›,cp)

که نتیجه آن بصورت زیر است:
dtResubErr =
۰٫۱۳۳۳
dtCVErr =
۰٫۲۹۳۳
تخمینی که برای cross-validation error  زده شده برای این درخت تصمیم dtCVErr =0.2933 می باشد که به وضوح از resubstitution error بزرگ تر است. این مقدار نشان دهنده این است که درخت تولید شده مجموعه آموزشی را overfit می کند. به عبارت دیگر این درخت مجموعه داده های آموزشی اولیه را به خوبی دسته بندی می کند ولی ساختار درخت حساس به همین داده های آموزشی است بنابراین کارایی آن روی داده های جدید احتمالا به این خوبی نخواهد بود. معمولا روی داده های جدید یک درخت ساده بسیار بهتر از درختی پیچیده مثل این درخت عمل می کند.
در صورتی که بخواهیم درخت را هرس کنیم ابتدا باید resubstitution error را برای زیرمجموعه های مختلف درخت اصلی محاسبه کنیم. سپس خطای  cross-validation را برای این زیردرخت ها محاسبه می نماییم.
با استفاده از دستور زیر، گرافی ساخته می شود که نشان می دهد resubstitution error بیش از حد خوش بینانه است. هرچه سایز درخت بزرگ تر شود این مقدار هم افزایش می یابد ولی از یک نقطه ای که می گذرد افزایش سایز درخت میزان cross-validation error را افزایش می دهد.
resubcost = test(t,›resub›);
[cost,secost,ntermnodes,bestlevel] = test(t,›cross›,meas(:,1:2),species);
plot(ntermnodes,cost,›b-›, ntermnodes,resubcost,›r–›)
figure(gcf);
xlabel(‹Number of terminal nodes›);
ylabel(‹Cost (misclassification error)›)
legend(‹Cross-validation›,›Resubstitution›)
در انتخاب درخت از میان درخت ساده تر و درخت پیچیده تر باید گفت یک قانون ساده انتخاب درختی است که cross-validation error کمتری دارد. برای این مثال انتخاب یک درخت ساده که خطای استاندارد را مینیمم کند بهتر است و قانون پیش فرض روش classregtree/test نیز همین است.
با اضافه کردن کد زیر در انتهای کد قبلی می توان پلات زیر را با محاسبه یک مقدار cutoff که مساوی با هزینه مینیمم به علاوه یک خطای استاندارد است نمایش داد. بهترین سطح محاسبه شده توسط روش classregtree/test کوچک ترین درخت زیر این cutoff است (bestlevel=0 متناظر است با درخت هرس نشده بنابراین باید ۱ را برای استفاده از آن به عنوان یک شاخص در خروجی های بردار از classregtree/test به آن اضافه کنید.)

[mincost,minloc] = min(cost);
cutoff = mincost + secost(minloc);
hold on
plot([0 20], [cutoff cutoff], ‹k:›)
plot(ntermnodes(bestlevel+1), cost(bestlevel+1), ‹mo›)
legend(‹Cross-validation›,›Resubstitution›,›Min + 1 std. err.›,›Best choice›)
hold off

در نهایت می توان با نگاه به درخت هرس شده misclassification error یا خطای دسته بندی اشتباه را برای آن محاسبه نمود.
کد زیر را به انتهای کد قبلی اضافه می کنیم:
pt = prune(t,bestlevel);
view(pt)
خروجی:
cost(bestlevel+1)
ans =
۰٫۲۴۶۷

در ادامه کدی که خود متلب برای درخت تصمیم و داده های Fisheriris مثال زده است آورده شده است:
load fisheriris;
t = classregtree(meas, species,›names›,{‹SL› ‹SW› ‹PL› ‹PW›});
view(t);
همان طور که مشاهده می شود داده های گونه setosa کاملا جدا از دو کلاس دیگر هستند بنابراین با اجرای اولین شرط pl<2.45 یا pl>=2.45 ( که pl به معنی طول گلبرگ است( در سمت چپ درخت قرار می گیرند. یعنی داده های setosa طول گلبرگی کمتر از ۲٫۴۵ داشتند ولی دو گونه دیگر طول گلبرگی بیش از این مقدار دارند لذا به سمت راست درخت حرکت می کنیم. در نود دوم مجددا یک سوال دیگر پرسیده می شود یعنی یک ویژگی دیگر به نام عرض گلبرگ یا PW مطرح می شود. همان طور که مشاهده می شود برخی از داده های گروه virginica در سمت راست درخت قرار می گیرند زیرا عرض گلبرگ آنها از ۱٫۷۵ بیشتر بوده و در سمت چپ نود مورد نظر (نود دوم) مجددا نود دیگری قرار گرفته و یک ویژگی دیگر را مطرح کرده یعنی طول گلبرگ بزرگتر مساوی و یا کوچک تر از ۴٫۹۵ سانتی متر که باز هم طول گلبرگ بخشی از داده های گروه virginica از این مقدار بیشتر است پس در سمت راست درخت قرار می گیرند. در سمت چپ این نود یک سوال و ویژگی دیگر مطرح می شود که عرض گلبرگ های بزرگتر مساوی ۱٫۶۵ و کوچک تر از ۱٫۶۵ را بررسی می کند. بدین ترتیب داده های versicolor کلا در سمت چپ این نود قرار می گیرند زیرا عرض گلبرگ آنها کمتر از این مقدار است و بقیه داده های کلاس virginica در سمت راست این نود قرار می گیرند.
الگوریتم بصورت زیر است:
Decision tree for classification
۱  if PL<2.45 then node 2 elseif PL>=2.45 then node 3 else setosa
۲  class = setosa
۳  if PW<1.75 then node 4 elseif PW>=1.75 then node 5 else versicolor
۴  if PL<4.95 then node 6 elseif PL>=4.95 then node 7 else versicolor
۵  class = virginica
۶  if PW<1.65 then node 8 elseif PW>=1.65 then node 9 else versicolor
۷  class = virginica
۸  class = versicolor
۹  class = virginica

در ادامه مثال دیگری از کاربرد classregtree در دسته بندی داده های گل زنبق آورده شده است:

%# load dataset
load fisheriris

%# split training/testing
cv = cvpartition(species, ‹holdout›,۱/۳);
trainIdx = cv.training;
testIdx = cv.test;
%# train
t = classregtree(meas(trainIdx,:), species(trainIdx), ‹method›,›classification›, …
‹names›,{‹SL› ‹SW› ‹PL› ‹PW›});
%# predict
pred = t.eval(meas(testIdx,:));
%# evaluate
cm = confusionmat(species(testIdx),pred)
acc = sum(diag(cm))./sum(testIdx)
view(t);
کد بالا نیز مانند مثال موجود در متلب می باشد و ویژگی را از طول و عرض گلبرگ می گیرد ولی این کار و ترسیم درخت را در مراحل کمتری انجام می دهد و نتیجه درختی است که عمق کمتری دارد. در نهایت نیز یک ارزیابی یا evaluation انجام می دهد و confusion matrix  و  accuracyرا نیز نمایش می دهد:
دسته بندی فوق دقتی معادل ۹۴ درصد داشته و ۳ نمونه را در گونه versicolor اشتباه دسته بندی کرده است.

دسته بندی داده های گل زنبق با استفاده از درخت تصمیم در نرم افزار RapidMiner
در RapidMiner پس از نصب RapidMiner Studio روال کار به این ترتیب است که وارد قسمت New Process می شوید سپس از سمت چپ صفحه قسمت Repositories و دایرکتوری data با استفاده از drag and drop داده های Iris را انتخاب کرده و به روی صفحه main process می کشید. سپس از قسمت operatores مسیر Modeling، Classification and Regression ، Tree induction، گزینه Decision Tree را انتخاب کرده و با drag and drop روی صفحه main process قرار می دهید. سپس همان طور که در شکل نشان داده شده خروجی ها و ورودی ها را به هم متصل می نمایید و در نهایت روی دکمه play در بالای صفحه کلیک می کنید. پس از اجرا نتیجه زیر نمایش داده می شود:
همان طور که مشاهده می شود از ویژگی a3 برای تقسیم بندی سطح اول استفاده شده است و داده های گونه setosa به طور کامل در سمت راست درخت قرار گرفته اند. تقسیم بندی نهایی دو گونه دیگر با رنگ های سبز و قرمز در شکل نمایش داده می شود.
در شکل بالا نحوه عملکرد درخت توصیف شده است و می توان دید که در هر یک از ویژگی ها چه تعداد از نمونه های هر گونه قرار گرفته اند.

train و استفاده از Apply Model
از قسمت modeling، model application گزینه apply model را انتخاب کرده و به روی صفحه می کشیم و به صورت شکل فوق به هم متصل می کنیم. منظور از exa داده های نمونه و منظور از unl داده های بدون برچسب است.
در شکلهای سمت چپ می توان دید که پس از استفاده از apply model ، confidence value یا مقدار اعتماد به دست آمده برای گونه setosa برابر با ۱ (در همه حالات ویژگی ها) می باشد به این معنی که مدل برای تخمین اینکه نمونه موجود مربوط به کدام کلاس است چقدر قابل اعتماد است. ولی در شکل دیگر مشخص است که میزان confidence در دسته بندی نمونه های گونه های versicolor و virginica دیگر ۱ نیست. مثلا برای نمونه id-113 که مربوط به گونه virginica استconfidence  ای برابر با ۰٫۹۷۸ در گونه virginica دارد.

ارزیابی پیش بینی ها
برای ارزیابی پیش بینی های انجام شده از validation  استفاده می شود که دارای sub process است. با کلیک بر روی پنجره های کوچک نشان داده شده روی فرایند validation به شکل زیر می رویم:
در اینجا قسمت های مربوط به آموزش و تست را بصورت فوق تکمیل کرده و ورودی ها و خروجی ها را متصل می نماییم. تعداد validation ها بصورت دیفالت ۱۰ تعیین شده است (۱۰ fold).
همان طور که مشاهده می شود دقت درخت تصمیم گیری در این مثال ۹۴ درصد بوده و تعداد نمونه هایی که به اشتباه دسته بندی شده اند ۹ نمونه است.
دسته بندی داده های گل زنبق با استفاده از درخت تصمیم (J48) در Weka:
در اینجا ویژگی های انتخاب شده ابتدا همان طول و عرض گلبرگ هستند و با انتخاب درخت J48 نتیجه دسته بندی بصورت زیر در می آید:
در شکل فوق نحوه انجام الگوریتم نمایش داده شده و مشاهده می شود که تعداد برگ ها ۵ و اندازه درخت ۹ است.
در اینجا مشاهده می شود که درخت با انتخاب ویژگی های طول و عرض گلبرگ داده ها را با دقت ۹۸ درصد مدل می کند و تعداد نمونه هایی که اشتباه دسته بندی شده، ۳ نمونه می باشد.
حال همین روش را برای کل ویژگی ها یعنی هر  پنج attribute تکرار می کنیم:
همان طور که مشاهده می شود نتیجه تغییری نکرد.
با انتخاب گزینه visualize tree می توان شکل زیر را مشاهده نمود:
با انتخاب دو ویژگی طول و عرض کاسبرگ و حذف ویژگی های طول و عرض گلبرگ به نتیجه زیر می رسیم:
همان طور که مشاهده می شود ۲۹ نمونه اشتباه دسته بندی شده و دقت تا ۸۰ درصد کاهش یافته است لذا استفاده از ویژگی های فوق مناسب نیست. درخت شبیه سازی شده برای این حالت به شکل زیر است:

————————–

هدی ابیضی

دیدگاهتان را ثبت کنید

آدرس ایمیل شما منتشر نخواهد شدعلامتدارها لازمند *

*

x

شاید بپسندید

آیا در کارها حضور بشر لازم است؟

رشد تکنولوژی، نیاز به نیروی کار را انسانی را در بسیاری از ...