Author name:
خلود جمال مولود
Supervisor name:
براء علي عطية | سوسن كمال
Abstract:
العنقدة هي نظام خصص لايجاد ووصف قطع متماسكة ومتجانسة في البيانات, هي العناقيد. مثال عن مسالة العنقدة هو الاظهار او الكشف الاوتوماتيكي لاجزاء ذات معنى في الصورة الرقمية. الحث على التركيز على عنقدة البيانات بسبب ان عنقدة البيانات هي عملية مهمة في تمييز الانماط والتعليم الالي. خوارزميات العنقدة تستخدم في عدة تطبيقات مثل تقطيع الصور, حساب متجه ولون الصورة, ضغط البيانات... الخ. لذلك, ايجاد خوارزمية عنقدة كفوءة هو شيء مهم جدا للباحثين في عدة انظمة مختلفة.الهدف الرئيسي لهذه الاطروحة هو استخدام الخوارزمية الجينية كاداة عنقدة للتصنيف غير الموجه للصورة ذات تدرج رمادي. هذه الاطروحة تقدم نوعين مختلفين من الخوارزمية الجينية : النوع الاول يعتمد على خوارزمية جينية بسيطة, بينما النوع الثاني يعتمد على الخوارزمية الجينية المضغوطة. المكونات الخصائصية لكل خوارزمية تعرض بصيغة تمثيل الفرد والمجموعة, حساب دالة الملائمة, عمليات التطور (الانتقاء, التقاطع, والتحديث), وشرط التوقف. هاتان الخوارزميتان الجينيتان سوف تربطان كل على حدة مع خوارزمية عنقدة بحث محلي تعرف ب(K means algorithm). الهدف من الربط هو تسخير قوة كل خوارزمية : قوة الخوارزمية الجينية وقوة (K means). بالاضافة الى ذلك, الالية القانونية لعمليات التشويش التي يرمز لها بالتقاطع والطفرة المفاجئة تحاكي بنسخة محدثة من الخوارزمية الجينية المضغوطة في محاولة لتحسين قوة بحثها.لعرض قابلية تطبيق خوارزميات العنقدة, تم استخدام صور اشعة رنين مغناطيسي لدماغ الانسان, صور اقمار صناعية. ايضا تم استخدام اعداد عناقيد مختلفة في الاختبارات العملية. نتائج المقارنة سجلت بصيغة نوعية (مرئية) وصيغة كمية باستخدام (Quantization Error)و (Weighted Sum of cluster compactness, cluster separation, quantization error ) والنسبة بين (cluster compactness and cluster separation ).النتائج اظهرت ان ) (cross - fertilization بين الخوارزميتين يعتبر فائدة في عنقدة الصورة, ويعمل بشكل افضل من خوارزمية (K - means) والخوارزميات الجينية عندما يعملان بشكل منفرد. بالاضافة الى ذلك وهو الاكثر اهمية, الخوارزمية الجينية المضغوطة المحدثة تعمل بشكل افضل من الخوارزمية الجينية المضغوطة العادية, لانهزاادت من قوة تاثير معاملات التشويش المضافة والتي تتضمن التقاطع ذو نقطتين والطفرة الثنائية | Clustering is a discipline devoted to find and describe cohesive or homogeneous chunks in data, the clusters. An example of clustering problem is the automatic revealing of meaningful parts in a digitalized image. The motivation for the focus on data clustering is the fact that data clustering is an important process in pattern recognition and machine learning. Clustering algorithms are used in many applications such as image segmentation, vector and color image quantization, compression, etc. Therefore, finding an efficient clustering algorithm is very important for researchers in many different disciplines. The primary objective of this thesis is to utilize Genetic Algorithm (GA) as a clustering tool for the unsupervised classification of grayscale image data. It presents two variants of GA : the first variant is based on the canonical GA while the second variant is based on compact GA, cGA. The characteristics components of each algorithm are presented in term of individual and population representation, fitness function evaluation, evolution (selection, crossover, and update) operators, and stopping condition. These two genetic algorithms are then coupled with one popular local - search cluster algorithm, known as K - means algorithm. By coupling, the objective is to harness the power of each algorithm : GA search exploration power and K - means search exploitation power. Moreover, the canonical mechanism of perturbation operators symbolized by both crossover and mutation is imitated in a modified version of cGA in an attempt to improve its search power. To show the applicability of the presented clustering algorithms, Human medical MRI and land sat images, are used in the experiments. Also, the experiments considered different number of clusters. Comparison results are reported in qualitative terms (i.e. visually) and in quantitative terms using quantization error, weighted error (sum of cluster compactness, clusters separation, and quantization error), and compactness - separation ratio. Results demonstrate that cross - fertilization between the two algorithms is of being benefit in image data clustering, and it outperforms K - means and genetic - based algorithms when they operated individually. Additionally and more interestingly, the modified cGA outperforms the traditional cGA, which leverage the influence of the added perturbation operators including two - point crossover and binary mutation.
