تبديل رگرسيون لجستيك به يك ابزار اصلي داده‌كاوي توسط TR-IRLS

Paul Komarek

Carnegie Mellon University

School of Computer Science

Pittsburgh, PA 15213

komarek@cmu.edu

Andrew W. Moore

Carnegie Mellon University

School of Computer Science

Pittsburgh, PA 15213

awm@cs.cmu.edu

چكيده

            كلاس‌بندي باينري يك وظيفه اصلي داده‌كاوي است. براي مجموعه‌هاي بزرگ داده‌ها يا ابزارهاي بلادرنگ، كلاس بندي كننده‌هايي مورد علاقه هستند كه دقيق و سريع باشند و نيازي به تنظيم هيچ پارامتري نداشته باشند. ما در اينجا يك كاربرد ساده رگرسيون لجستيك را ارائه مي‌دهيم كه اين شرايط را دارا است. تركيبي از روش تنظيم نيوتني مقطع و روش كمترين مربعات با وزن گذاري چند مرحله‌اي اي كار را سريعتر و دقيقتر از روشهاي مدرن SVM انجام مي‌دهد و حساسيت به پارامترها را تا حدودي كم مي‌كند. و نسبت به وابستگيهاي خطي و برخي مسائل مقياسي مقاوم است كه نياز به برخي عمليات پيش ـ پردازش داده‌ها را از بين مي‌برد.

1- انگيزه و توضيح اصطلاحات

            انگيزه اين مقاله موفقيت يك الگوريتم رگرسيون لجستيك (LR) سريع و ساده در چندين مورد داده‌كاوي با تعداد ابعاد بالا بود، كه شامل داده‌كاوي علو زيستي ( 7 و 10 )، طبقه‌بندي تهديد و آناليز ارتباط موقت ( 16 )،‌ فيلتر كردن شراكتي ( 11 ) و پردازش متن ( 7 ) مي‌گرديد. ظهور ماشينهاي بردار حمايت (SVM) در كلاس‌بندي باينري ( دوتايي ، دو حالته ) به دليل توابع افت مشابه ،‌ موجب علاقه مجدد به LR  شده است ( 20 و 21 )‌.در بسياري از مقالات اخير روشهاي جديدي براي تخمين زدن پارامترهاي مدل LR پيشنهاد شده، مرجع ( 8 ) و ارجاعات آنرا نگاه كنيد. بسياري از كاربردهاي جديد LR شامل دستورالعملهايي براي تنظيم پارامترها و يا پيش ـ پردازش داده‌ها هستند. اين مراحل ميتواند در مورد مجموعه‌هاي داده كوچك گمراه كننده و در مورد مجموعه داده‌هاي بزرگ غير عملي يا غير ممكن باشد. انجام تعداد زيادي ارزيابيهاي متقاطع براي تنظيم پارامترها زمان محققان و اجرا كنندگان را هدر مي‌دهد.

            روش فيت كردن ما براي LR شامل اصلاحات ساده‌اي در كمترين مربعات با وزن گذاري چند‌ مرحله‌اي (IRLS) است كه از روشهاي نيوتني مقطع پيروي ميكند و تنظيماتي را اضافه مي‌كند. ادعاي ما براين است كه اين روش ساده است و احتياجي به تنظيم پارامتر يا پيش ـ پردازش داده‌ها ندارد. ما الگوريتم خودمان TR- IRLS را با ديگر ابزارهاي LR و SVM هاي خطي و SVM‌هاي مبني بر تابع شعاعي (RBF) مقايسه مي‌كنيم. براي مقايسه و تحليل بيشتر مرجع (8) را ببينيد. نرم‌افزار ، source و بيشتر مجموعه‌هاي داده‌هاي ما در   http://www.autonlab.org    و    http://komarix.org    موجود است.

            در ابتدا نشان مي‌دهيم كه TR-IRLS ميتواند LR را ساده ، موثر ، و بدون پارامتر كند. منظور از بدون پارامتر اين است كه عموما تنظيم لازم نيست. اگر چه در اين مقاله كوتاه نيامده ولي، TR-IRLS در مورد LR هسته‌اي و همچنين هر مدل خطي تعميم يافته‌اي كاربرد دارد. ما توضيح كاملي را از الگوريتم خودمان ارائه مي‌دهيم.

            ما در اين مقاله به كلاس‌بندي باينري مي‌پردازيم، و اينكه يه نقطه داده متعلق به كلاس مثبت است يا كلاس منفي. يك كلاس‌بندي كننده به اندازه كافي سريع بطور منطقي ميتواند از طريق يك تبديل خطي نسبت به زمان ( تعداد كلاسها نسبت به زمان خطي باشد) در مورد مسائل چند كلاسي بكار رود ( 11 ). يك مجموعه داده ماتريسي از وروديها X و يك بردار باينري خروجي y است. هنگاميكه yi = 1 باشد سطر i ام از X مربوط به كلاس مثبت است. M خصوصيت و R ركورد وجود دارد. براي يك ماتريس باينري پراكنده، F ميزان پراكندگي، و MRF تعداد عناصر غير صفر است.

            گراديان مزدوج (conjugate gradient)  (CG) يك الگوريتم كمينه سازي چند مرحله‌اي است. CG تنها به محاسبه حاصلضربهاي ماتريس ـ بردار دارد. هنگاميكه CG بر يك صورت نمايي اعمال شود بصورت خطي در مي‌آيد. در غير اين صورت CG غير خطي ناميده مي‌شود و نياز به تصحيح جهت پي برنده ،‌ جستجوهاي خطي،‌ و شروع مجدد دارد. بدليل اينكه Hessian صورت نمايي يك ماتريس است، از CG خطي مي‌توان براي حل سيستمهاي معادلات خطي استفاده نمود. توضيحات بيشتر را مي‌توانيد در مراجع ( 17 و 19 ) پيدا كنيد.

2- رگرسيون لجستيك

            LR رابطه بين هر سطر x1 از X  و مقدار مورد انتظار E(yi) را مدل مي‌كند كه تابع لجستيك آن

 است كه در آن b بردار پارامترها است. فرض مي‌كنيم  بنابراين  يك جمله ثابت است. مدل رگرسيون ما بصورت  است كه  در آ ن يك عبارت خطاي دوجمله‌اي است. قرار دهيم  . احتمال رخداد لگاريتمي بصورت زير است :

                                              ( 1 )

تابع افت همان انحراف است (DEV) ،‌ كه براي خروجيهاي باينري بصورت 2 ln L -  است (4 و 13 ). LR يك كلاس بندي كننده خطي است و ممكن است داده‌هاي با ابعاد پايين با مرزهاي غير خطي را به خوبي كلاس بندي نكند. بهر حال،‌درفضاهاي با ابعاد بالا معمولا شرايط مرزي خطي مناسب هستند. هسته بندي LR ممكن است بر اين محدوديت ابعاد پايين فايق آيد ( 21 ).

IRLS

كمترين مربعات با وزن گذاري چند مرحله‌اي (IRLS) يك الگوريتم بهينه سازي غير خطي است كه از يك سري زير مسائل كمترين مربعات وزني (WLS) براي جستجوي MLE استفاده مي‌كند ( 2 و 13 ). IRLS يك مورد خاص از روش امتياز بندي Fisher است، يك الگوريتم quasi-Newton كه Hessian تابع موضوعي را با اطلاعات Fisher جايگزين مي‌كند. براي LR ، IRLS يك صورت خاص از روش نيوتن است ( 2 و 3 و 13 ). ما IRLS را در الگوريتم 1 خلاصه مي‌كنيم. بر خلاف بيشتر انواع روشهاي نيوتني، هيچ طول مرحله‌اي براي محاسبه وجود ندارد. قسمت مشكل حل كردن زير مسئله WLS بصورت

 است ، يك سيستم خطي با M معادله و M مجهول. عنصر ( i , j ) ام ماتريس X^TWX حاصلضرب نقطه‌اي وزني ستونهاي i ام و j ام است. وزن در هر مرحله تغيير مي‌كند كه بايد دوباره محاسبه شود. روش نيوتن بتدريج به همگرايي مي‌رسد، ولي هر مرحله از نظر محاسبه هزينه بر است. براي توضيح كامل كار اوليه ما روي IRLS مرجع ( 10 ) را نگاه كنيد.

TR-IRLS

            به اين دليل كه زير مسئله‌هاي WLS سيستمهاي خطي هستند، آنها را مي‌توان همانگونه كه در الگوريتم 2 آمده با استفاده از CG خطي حل نمود. اين كار از بهينه سازي احتمال وقوع توسط CG غير خطي آسانتر است، زيرا CG خطي داراي يك فرمول اصلاح جهت بهينه است و هيچ جستجو يا شروع مجددي براي خط ندارد. اگر تعداد شرط X^TWX را در نظر نگيريم، CG خطي بصورت O(MRF) است ( 19 ). ما ميتوانيم مراحل CG را زودتر متوقف كنيم تا راه حل WLS را تخمين بزنيم، بنابراين يك روش نيوتني مقطع ايجاد مي‌كنيم كه همراه با تضمين همگرايي است ( 17 ). CG تنها به حاصلضربهاي ماتريس بردار احتياج دارد كه محاسبه X^TWX را از بين مي‌برد و محاسبات پراكنده را ساده مي‌كند.

            خصوصيات وابسته مي‌توانند موجب مشكلاتي در تغيير مقياس شوند كه ما با استفاده از رگرسيون مرزبندي             (ridge regression) براي رگولاسيون زير مسئله‌هاي WLS به آن پرداخته‌ايم ( 3 و 18 ). براي اين كار تنها لازم است X^TWX را توسط lI برهم بزنيم. ما تركيب IRLS ، CG خطي و رگرسيون ridge را IRLS رگوله شده مقطع يا TR-IRLS مي‌ناميم.

            هنگامي IRLS را متوقف مي‌كنيم كه اختلاف نسبي انحراف |DEV_i-1 - DEV_i| / | DEV_i|   از مقدار 1 e   كمتر باشد. همين تست هم مي‌تواند با مرز 2 e   براي تعداد مراحل CG بكار رود. بعضي اوقات مراحل CG پراكنده مي‌شوند و انحراف زيادي ايجاد مي‌كنند و ما تعداد مراحل غير مفيد متوالي را توسط پارامتر پنجره CG محدود مي‌كنيم. آخرين كار ما اين است كه در الگوريتم 2 مقدار v را به  bi   بدهيم در حاليكه محاسبه را براي bi+1  انجام ميدهيم.

            در خلال يك ارزيابي بزرگ تجربي از l, e1, e2 و پنجره CG ( 7 ) ، مشاهده كرديم كه دقت محاسبه به مقادير اين پارامترها نسبتا غير حساس است. بنابراين، ما از مقادير پيش‌فرض l = 10  e1 = 1=100 ,  e2 = 1=200 ,  و پنجره CG برابر با 3 مرحله براي تمام آزمايشهاي اين مقاله استفاده مي‌كنيم.

            CG-MLE

            علاوه بر IRLS ، از روشهاي غير خطي ديگري نيز براي بهينه كردن احتمال رخداد LR مي‌توان استفاده نمود. CG غير خطي يكي از بهترين روشها در كار Minka  بود ( 15 ). و نيز يكي از اولين روشهاي استفاده شده براي LR كامپيوتري بود ( 14 ). ما اين تركيب را CG-MLE مي‌ناميم. براي بحث درباره جايگزيني quasi-newton در CG غير خطي مرجع ( 8 ) را ببينيد. اگر تعداد شرطهاي ماتريس ورودي را در نظر نگيريم،  CG غير خطي O(MRF) است ( 19 ). مدت زمان واقعي اجرا بستگي به عوامل زيادي از جمله فرمول تصحيح جهت، جستجوي خط و شرايط شروع مجدد دارد. CG غير خطي فرمولهاي تصحيح جهت بسياري دارد. ما در ( 7 ) چهار تا از مهمترين آنها را مقايسه كرديم، و فرمول تغيير يافته Polak-Ribiere را انتخاب كرديم. اين فرمول تصحيح Polak-Ribiere را با شروع مجدد Powel تركيب مي‌كند ( 17 ) و مي‌توان آنرا بصورت زير نوشت :

  كه در آن  با همان علامت در الگوريتم 2 نشان داده شده.

            در CG-MLE رگوله سازي اهميت دارد ( 15 و 20 ). مشابه رگرسيون Ridge ، احتمال رخداد توسط l( bT b) تحت تأثير قرار مي‌گيرد. هر مقدار معقول براي l خوب است و ما مقدار 10 را انتخاب مي‌كنيم. گزارش داده شده كه دادن  به ميانگين y موجب بهبود پايداري مي‌گردد ( 14 )، ولي ما تنها بهبود در سرعت را مشاهده كرديم. روش پنجره CG TR-IRLS  همچنين به CG-MLE نيز كمك مي‌كند. ما با استفاده از تستي مشابه TR-IRLS با اپسيلون 200 / 1 ، مراحل CG-MLE را خاتمه مي‌دهيم ( 7 ).

3- آزمايشات

            تمام آزمايشها  ارزيابيهاي  متقاطع  ده  برابر

امتياز بندي شده توسط مساحت زير منحني (AUC)

بصورت متريك  هستند ( 3 ).  معيار AUC  قابليت

كلاس  بنديها  را  درجه بندي  مي‌كند، كه 0/1  براي

بهترين  است  و  5/0  براي حدس زدن تصادفي. در

( 7 ) AUC را بيشتر توضيح مي‌دهيم. جمع‌بنديهاي

ما با متريكهاي ديگر مثل دقت ، recall و F1 صادق

است. تمام مقادير زمان بصورت ثانيه  واقعي  هستند

ولي  شامل  ورود  و خروج  اطلاعات يا زمان صرف

شده براي تنظيم SVM ها نمي‌شود. ما از يك سيستم

AMD Opteron 242  و  كمتـر  از 4 GB  مقدار

RAM استفاده كرديم.

            در اين مقاله كوتاه، LR را با SVM هاي خطي تنظيم شده براي هر مجموعه از داده‌ها و SVM هاي تابع مبني بر شعاع (RBF) در SVM^light  ويرايش پنج، مقايسه مي‌كنيم ( 6 ). ما بصورت خلاصه TR-IRLS را با SAS proc logistic مقايسه مي‌كنيم. در كار قبلي، Naïve Bayes   و  درختهاي تصميم C4.5 بطور مرتب امتيازي كمتر از LR داشتند ( 7 ).

            هفت مجموعه داده اين مقاله در جدول 1 خلاصه شده است. جزئيات مربوط به مجموعه داده‌هاي آناليز ارتباط citeseer  و imdb  و مجموعه داده‌هاي علوم زيستي ds2  , ds1  , ds1.100  و ds1.10 در ( 7 ) آمده‌اند. اين دو تاي آخري نمايشهاي PCA از ds1 هستند. ما همچنين از يك مجموعه كلاس بندي متن modapte.sub استفاده مي‌كنيم كه زير مجموعه‌اي است از مجموعه آموزشي چند كلاسي Reuters-21578 ModApte . ما كلاسهايي با 100 رديف مثبت يا بيشتر را در نظر گرفتيم : acq  ، قهوه ، ذرت ، نفت خام ، dlr ، درآمد ، gnp ، حبوبات ، بهره ، پول-fx ، پول- ذخيره ، دانه‌هاي روغني ، كشتي ، شكر ، تجارت ، و گندم كه با a1  تا a16 نشان داده مي‌شوند. ستون ‏‎” nonzero “  تعداد وروديهاي غير صفر را در مجموعه‌هاي داده پراكنده نشان مي‌دهد. ”Pos “ تعداد رديفهاي مثبت را نشان مي‌دهد بجز در مورد modapte.sub كه روي صفات ورودي ميانگين گرفته شده است. تمام مجموعه‌هاي داده‌ها به غير از ds1 و ds2  در دسترس عموم قرار دارد ( 9 ).

4- نتايج و آناليزها

            جدول 2 در بالا  AUC و نتايج زماني در علوم زيستي و مجموعه‌هاي ارتباط را نشان مي‌دهد. روشهاي LR تقريبا داراي امتيازات AUC يكساني هستند. براي از بين بردن هرگونه تمايل AUC مقابل سرعت توسط مؤلفان، ما دو مجموعه آزمايش SVM انجام داديم. در اولين مجموعه AUC از طريق تنظيمات فراوان بهينه سازي  مي‌شود، و در مجموعه دوم سرعت چنان بهينه سازي مي‌گردد كه AUC در حدود 10 درصد بهترين SVM AUC باشد. با وجود اين، هنوز هم TR-IRLS در تمام موارد سريعتر است. زمان قابل توجه صرف شده براي تنظيم SVM هاي خطي و RBF در هيچكدام از زمان گيريهاي ما منظور نشده است.

            با تنظيم ظرفيت SVM^light  و پارامتر گاما در RBF بهبود قابل توجهي در دقت حاصل شد. مقادير نهايي بكار رفته در (8) آمده است. بجز آزمايشهاي ds1.100  و  ds1.10 ، امتياز TR-IRLS مساوي و يا بهتر از ديگر كلاس بندي كننده‌ها در تمام آزمايشات بود. اين دو مجموعه داده داراي ابعاد نسبتا كمتري هستند كه احتمالا براي يك كلاس بندي خوب احتياج به شرايط مرزي غير خطي دارند، و RBF SVM ها در اين مورد از تمام كلاس بندي كننده‌هاي خطي بهتر هستند. بهر حال، TR-IRLS روي ds1 اصلي براي محاسبه يك كلاس بندي كننده بهتر نياز به زمان كمتري نسبت به RBF SVM براي ويرايشهاي كمپرس شده PCA ds1.100 و ds1.10  دارد. بر روي اين مجموعه داده‌هاي كوچك، يك ويرايش سريع از KNN براي مسائل كلاسهاي در هم پيچيده (12) قابل رقابت تر بود (8). نزديكترين رقيب TR-IRLS در دقت بر روي مجموعه داده‌هاي بزرگتر CG-MLE است. بهر حال، TR-IRLS بطور كلي سريعتر است و كاربرد و درك عميق آن ساده تر مي‌باشد. تمام كلاس بندي كننده‌ها روي modapte.sub خوب عمل كردند و LR و SVM هميشه امتياز بالاتر از 977/0 داشتند. در جدول 3 زمانهاي مربوط به 10 صفت اول آمده است. باز هم TR-IRLS سريعتر است.

            SVM^light عموما در مقايسه با TR-IRLS نسبت به پارامترهايش داراي حساسيت بيشتري است، ولي هسته خطي آن روي ds1.10 بطور تعجب آوري نامنظم بود. بيشترين تغييرات در AUC براي تغييرات كوچك در ظرفيت در شكل 1 نشان داده شده است. محور سمت چپ نشاندهنده AUC است ، محور افقي ظرفيت است، و دايره‌ها نقاط داده AUC هستند. محور سمت راست و خط تو پر زمان را براي هر آزمايش نشان مي‌دهند. LIBSVM (1) رفتار مشابهي را نشان داد (8).

            ما TR-IRLS را با SAS' proc logistic  مقايسه كرديم (5) ( با تشكرات ويژه از Lujie Chen, Auton Lab ) به اين دليل كه proc logistic گزينه‌اي براي داده‌هاي پراكنده ندارد، ما زيرمجموعه‌هاي متراكم بزرگي از ds1 ساختيم. TR-IRLS  در كل سه برابر سريعتر از محاسبات متراكم اجرا شد. ميزان استفاده SAS از حافظه به سرعت با افزايش تعداد ستونها افزايش يافت و آزمايشات ما را محدود كرد.

5- كارهاي مشابه

          بحث عمده در مقالات فعلي LR اين است كه چگونه بايد پارامترهاي LR را محاسبه كنيم. (8) و ارجاعات آنرا ببينيد. روشهاي پيشنهاد شده شامل انواع تغيير يافته روشهاي نيوتن، CG ، تغيير مقياس چند مرحله‌اي، و نزول مختصات چرخه‌اي   Gauss-Seidel مي‌باشد. اين روشها با مسائل عددي و فيت شدن زياد از حد مواجه هستند كه در بهينه سازي غير خطي در يادگيري ماشين رايج است. مشاهدات (15 و 20) و آناليزهاي (8) را نگاه كنيد.

6- جمع بنديها

          ما روش فيت كردن TR-IRLS  را ارائه نموديم و كاربرد آنرا در رگرسيون لجستيك نشان داديم. به نظر مي‌رسد اين تركيب سريعتر و حد اقل به اندازه SVM ها و ديگر روشهاي فيت كردن رگرسيون لجستيك دقيق است. از TR-IRLS  مي‌توان با هر مدل خطي تعميم يافته‌اي استفاده نمود. TR-IRLS بسيار ساده است و از روي جزئيات آمده در اين مقاله مي‌توان آنرا اجرا كرد. نرم‌افزار ، منابع، و داده‌هاي ما در http://www.autonlab.org  و http://komarix.org  در دسترس مي‌باشد.

منابع

support vector machines, 2001. Software available at

http://www.csie.ntu.edu.tw/ٍcjlin/libsvm.

[2] J. E. Gentle. Elements of Computational Statistics. Statistics

and Computing. Springer Verlag, 2002.

[3] T. Hastie, R. Tibshirani, and J. Friedman. The Elements of

Statistical Learning. Springer Verlag, 2001.

[4] D. W. Hosmer and S. Lemeshow. Applied Logistic Regression.

Wiley, 2nd edition, 2000.

[5] http://www.sas.com/. SAS. http://www.sas.com/.

[6] T. Joachims. SVMlight, 2002. svmlight.joachims.org.

[7] P. Komarek. Logistic Regression for Data Mining and High-

Dimensional Classi_cation. Technical Report TR-O4-34,

Robotics Inst., Carnegie Mellon Univ., Pgh, PA, May 2004.

[8] P. Komarek. Making Logistic Regression A Core Data Mining

Tool: A Practical Investigation of Accuracy, Speed, and

Simplicity. Technical Report TR-O5-27, Robotics Inst.,

Carnegie Mellon Univ., Pgh, PA, May 2004.

[9] P. Komarek. Datasets, 2005. http://komarix.org/ac/ds.

[10] P. Komarek and A. Moore. Fast Robust Logistic Regression

for Large Sparse Datasets with Binary Outputs. In Arti_cial

Intelligence and Statistics, 2003.

[11] J. Kubica, A. Goldenberg, P. Komarek, A. Moore, and

J. Schneider. A Comparison of Statistical and Machine

Learning Algorithms on the Task of Link Completion. In

KDDWorkshop on Link Analysis for Detecting Complex Behavior,

page 8, August 2003.

[12] T. Liu, A. Moore, and A. Gray. Ef_cient Exact k-NN and

Nonparametric Classi_cation in High Dimensions. In Proc.

of Neural Information Processing Systems, 2003.

[13] P. McCullagh and J. A. Nelder. Generalized Linear Models,

volume 37 of Monographs on Statistics and Applied Probability.

Chapman & Hall, 2 edition, 1989.

[14] A. McIntosh. Fitting Linear Models: An Application of Conjugate

Gradient Algorithms, volume 10 of Lecture Notes in

Statistics. Springer-Verlag, New York, 1982.

[15] T. P. Minka. Algorithms for maximum-likelihood logistic

regression. Technical Report Stats 758, Carnegie Mellon