بخشی از مقاله
چکیده
جاسازی گراف در فضای برداری با بهرهگیری همزمان از جامعیت گرافها در نمایش الگو و برتری محاسباتی بردارهای ویژگی، یک راهحل آسان برای مسائل یادگیری ماشین ارائه میکند. کاهش اطلاعات ازدسترفته در طی تبدیل گراف با قدرت نمایشی بالا به برداری با نمایش محدودتر، نقطه مقابل کاهش هزینه محاسباتی این رویه برای استخراج ویژگی است. هدف از این مقاله ارائه چارچوبی سلسلهمراتبی برای رسیدگی همزمان به این مسائل است.
تبدیل موجک در حوزه پردازش تصویر، ایده تجزیه گراف به چندین گراف مستقل را بهمنظور پردازش بهتر اجزای آن تداعی میکند. برایناساس چارچوبی تعریف میگردد که به جاسازی یک سطح انتزاعی از گراف و سطوح جزئیات متعاقب آن میپردازد. این امر منجر به تکمیل ویژگیهای ازدسترفته گراف در فرایند جاسازی میشود. درنهایت ارزیابیهای آزمایشی، مزیتهای این رویکرد جدید را از نظر دقت و زمان در زمینه مسائل ردهبندی در مقایسه با روش پایه انتخابشده نشان میدهد.
-1 مقدمه
بردارهای ویژگی بهدلیل اساس ریاضی استوار و فراهم آوردن ابزارهای الگوریتمی غنی، از اهمیت زیادی در بازشناسی الگو برخوردار هستند. با اینوجود در مواردی که ساختار نقش مهمی در الگوهای مورد بررسی بازی میکند، نمایشهای مبتنیبر گراف میتوانند بر محدودیتهای نمایشی بردارها چیره شوند. هرچند فضای پراکنده گرافها باعث شده است که تعریف بسیاری از عملیات پایهای ریاضی در آن، چنانچه غیرممکن نباشد بسیار سخت باشد. این موضوع سبب شده است تنها تعداد اندکی ابزار برای پردازش گرافهای ورودی وجود داشته باشد.
این ابزارها عمدتاً مبتنیبر فرایند ارزیابی عدم شباهت دو گراف و از نوع الگوریتمهای ساده نزدیکترین همسایه k- - - NN هستند [1]یک. روش جالب برای غلبه بر این مشکل جدّی، جاسازی گراف در فضای برداری است. بهطور رسمی، جاسازی را میتوان تابع نگاشت : → ℝ دانست که گرافها را از حوزه گراف دلخواه به یک فضای برداری حقیقی ℝ نگاشت میکند. درنهایت براساس نتیجه نگاشت گراف، وظیفه بازشناسی الگوی مورد نظر انجام میشود.
از اینرو کل سلاح ابزارهای الگوریتمی که در اصل برای فضاهای برداری توسعه داده شده بودند برای گرافها - و بهطور دقیقتر برای نگاشتهای گراف - - - ∈ ℝ نیز در دسترس قرار میگیرند. بهمنظور تبدیل گرافهای با اندازه دلخواه به بردارهای ویژگی با اندازه ثابت، نیاز است ویژگیهای مهم موجود در گرافها بهگونهای استخراج شوند که در فضای حاصل از جاسازی ساختارهای مشابه به همدیگر نزدیک و ساختارهای متفاوت از هم دور باشند، یعنی یک خوشهبندی ضمنی از گرافها بهدست آید .[2] با توجه به رویکرد استخراج ویژگیها از گراف، روشهای جاسازی را میتوان به سه خانواده اصلی تقسیم نمود.
روشهای خانواده اول مبتنیبر نمایشهای عدم شباهت میباشند. بر این مبنا، ریزن و بونکه [3] به معرفی روشی پرداختند که در آن هر گراف در برداری جاسازی میشود که هر مؤلفه از آن نشاندهنده میزان فاصله گراف تا یک گراف پیشالگو است. خانواده دوم مبتنیبر فرکانس حضور زیرساختارهای مشخص، استفاده از اطلاعات توپولوژی و محتوای برچسبهای آن است. برای نمونه، بردار مرتبط با یک گراف را میتوان با شمارش تعداد دفعات حضور مدلهای ساختاری متفاوت در گراف موردنظر ایجاد نمود .[4] روش اخیر گیبرت و همکاران او [5] براساس آمار حضور یک مجموعه مشخص از نمایندگان برچسبهای رأس و یالهای میان آنها است.
لقمان و همکارانش [6] در روشی دیگر اطلاعات گراف را در چندین سطح از توپولوژی، ساختار و خصایص در نظر میگیرند. خانواده سوم یعنی جاسازی طیفی گراف مبتنیبر استخراج ویژگی از تجزیه ویژه ماتریس مجاورت یا ماتریس لاپلاسین است [7 , 2]برای. نمونه رِن و همکارانش [8] ضرایب ترکیب خطی حاصل از تابع ایهارا را بهعنوان نمایندههایی از تعداد دورهای موجود در گراف مورد استفاده قرار دادند.
هر یک از این خانوادهها در کنار مزایای خود دارای محدودیتهایی هستند. روشهای مبتنیبر عدم شباهت [3] بهدلیل استفاده از فاصله ویرایش گراف بهعنوان معیار عدم شباهت،قابلیت اِعمال بر روی انواع گرافها و مقابله با انحرافات متنوع را دارد. با اینحال، زمان محاسبه آن برای گرافهای بزرگ چالشبرانگیز است. روشهای خانواده دوم با یافتن زیرساختارها قادر به بهرهبرداری از دانش دامنه هستند [4]، اما یافتن این زیرساختارها یک مسئله یکریختی زیرگراف است و دارای پیچیدگی زمانی بالا است.
روشهای جدیدتر در این خانواده [6 , 5] تکیه بیشتری بر برچسبهای موجود در گراف و روابط همسایگی داشتهاند و تا حدی از زیرساختارهای پیچیدهتر صرفنظر نمودهاند. روشهای طیفی [7] میتوانند در زمان چندجملهای، خصوصیات مفید و معناداری از ساختار گراف فراهم آورند. اما مشکل ذاتی آنها، حساسیت به نویز است. بهعلاوه تنها میتوانند بر روی گرافهایی با الفبای برچسب بهشدت محدودشده استفاده شوند.
بهطور کلی، یافتن نمایشهای برداری مناسب برای گرافها با پیچیدگیهایی همراه است. با توجه به اینکه توان نمایشی گرافها به وضوح بیشتر از بردارهای ویژگی است، ویژگیهای استخراجشده میبایست تا جای ممکن اطلاعات گراف به ویژه اطلاعات ساختاری و پیچیدگیهای آن را به نمایش بگذارند. از طرف دیگر استخراج ویژگی از گراف بهمنظور جاسازی نباید شامل عملیات هزینهبر باشد. این نیازمندیهای متضاد بهخصوص با افزایش اندازه گراف بیشتر به چشم خواهند آمد.
درحقیقت هرچه گراف استخراجشده بزرگتر باشد، پردازش اطلاعات موجود در تمامی اجزای گراف بهمنظور جاسازی مطمئن آن در فضای برداری هزینه بیشتری را در بر خواهد داشت. علاوهبراین، به دلیل افزایش پیچیدگیهای ساختاری، احتمال بروز انحراف از ساختار و محتوای اصلی گراف بیشتر خواهد بود. درنتیجه یک نمایش برداری از گراف برای اهداف ردهبندی و خوشهبندی، باید با برقراری مصالحهای وابسته به کاربرد میان زمان جاسازی و حفظ اطلاعات بهدست آید.
بدینمنظور در این مقاله از یک چارچوب سلسلهمراتبی استفاده شده است. ایده اصلی، بهرهمندی از موفقیتهای حاصلشده از نظریه چنددقتی در حوزه پردازش سیگنال و تصویر [9] بوده است. این نظریه ابزار قدرتمندی برای نمایش کارآمد توابع در چندین سطح از اطلاعات بهحساب میرود. استفاده از این مفاهیم در حوزه گراف منجر به یک جاسازی قوی با حفظ اطلاعات سراسری یک گراف در کنار اطلاعات محلی آن میشود. سازماندهی مطالب باقیمانده بدینصورت است: بخش بعد اشارهای مختصر به مفاهیم اولیه و روش جاسازی پایه استفادهشده در این مقاله میکند. بخش 3 چارچوب کلی مبتنیبر جاسازی سطوح انتزاعی و جزئیات گراف را معرفی میکند . بخش 4 به تحلیل نتایج آزمایشهای ردهبندی میپردازد . سرانجام مقاله با نتیجهگیری و کارهای آینده در بخش 5 به پایان میرسد.
-3 چارچوب پیشنهادی
مفاهیم دقت یا مقیاس، متناظر با میزان جزئیاتی است که میتواند توسط مشاهدهگر درک شود. فرمولهسازی این مفاهیم ابتدایی امکانپذیر بوده و نظریه پردازش سیگنال و تصویر به آنها یک معنای دقیق بخشیده است. الگوریتمهای متنوعی در پردازش تصویر میتوان یافت که بهمنظور تحلیل تصویر آن را به چندین جزء تجزیه میکنند. هر یک از این اجزاء اطلاعات موجود در یک مقیاس مشخص را دربردارد. در میان روشهای مختلف، تبدیل موجک [9] بهعنوان روشی سلسلهمراتبی معرفی میشود که میتواند قدرتهای تفکیک متفاوت در تصویر را بهخوبی مدیریت کند.
در تجزیه موجک، تصویر به مجموعهای از زیرتصاویر تجزیه میشود که علاوهبر مقیاس درشت یا تقریبی از تصویر، جزئیات آن را با جهات مختلف فضایی نمایش میدهد. بهطور کلی هدف از تبدیل موجک بسط یک تابع به تقریبی از آن و مجموعهای از توابع جزئیات است که برای ارزیابی تابع اصلی ضروری هستند. این روش از سازماندهی و نمایش پراکندگی داده منجر به یک پیادهسازی کارآمد شده و یک قانون راهنما برای بهدست آوردن الگوریتمهای جدید برای مسائل دیگر فراهم میآورد.
بر مبنای قانون گفتهشده اگر یک گراف را بتوان بهصورت تعدادی گراف دیگر نمایش داد، امکان تحلیل بهتر آن وجود خواهد داشت. بر این اساس، در یک گام جلوتر از معرفی هرم گراف برای جاسازی [11] به ارائه روشی خواهیم پرداخت که بر مبنای مقیاس تقریبی و جزئیات استخراجشده از گراف عمل میکند. گراف = - , , , - و هرم Π , - - ساختهشده از آن را در نظر بگیرید. متناظر با هر سطح از این هرم، یک گراف کاهشیافته از وجود دارد که تعداد رأسهای آن با هر گام پیش رفتن به سمت بالای هرم با ضریب کاهشی λ > 1 کاهش مییابد.
بنابراین تعداد سطوح هرم برابر با = ⌊logλ | |⌋ خواهد بود. پایه هرم - سطح صفر - همان گراف اصلی با | | رأس و قله آن - سطح ام - انتزاعیترین سطح از گراف با یک رأس را نمایش میدهد. بهطور کلی، گراف سطح - 0 ≤ ≤ - که آن را با نشان میدهیم، دارای | | = ⌊| |⌋ رأس است. از آنجایی که بالاترین سطوح انتزاع مانند گرافی با یک رأس،معمولاً اطلاعات چندانی در اختیار نمیگذارند، میتوان هرم گراف را به - 1 ≤ ≤ - تخمین دقت از گراف اصلی محدود کرد. بنابراین هرم گراف از + 1 سطح انتزاعی اول تشکیل میشود که بالاترین انتزاع در سطح و بیشترین جزئیات در سطح صفر قرار دارد و بقیه سطوح دور ریخته میشوند.
رأسهای گراف هر سطح بر اساس یک روال کاهشی از رأسهای سطح پایین آن بهدست میآیند. در حقیقت، مجموعهای از رأسها در یک سطح به رأسی در سطح بالاتر کاهش مییابند. یالها نیز براساس روابط همسایگی و شباهت میان رأسهای کاهشیافته ساخته میشوند. ما این فرآیند را محلیسازی مینامیم، به این مفهوم که ساختارهای سراسری یک گراف را به ساختارهای محلی گراف سطح بالاتر تبدیل میکند. عملگر محلیسازی پیشنهادی برای گرافها، خلاصهسازی گراف [13 , 12] است . خلاصهسازی گراف، گزینه مناسبی است که علاوه بر محاسبات کم میتواند تصویر روشنی از سطح بالاتر گراف ارائه دهد. الگوریتم خلاصهسازی در سطح بر روی گراف اجرا شده و گراف خروجی +1 را تولید میکند.
