K q-flats
ڈیٹا مائننگ اور مشین لرننگ میں،-فلیٹس الگورتھم ایک تکراری طریقہ ہے جس کا مقصد مشاہدات کو کلسٹرز میں تقسیم کرنا ہے جہاں ہر کلسٹر-فلیٹ کے قریب ہوتا ہے، جہاں ایک دیا ہوا عدد ہوتا ہے۔ یہ-مینز الگورتھم کی عمومی شکل ہے۔ - کا مطلب الگورتھم میں، کلسٹرز اس طرح بنائے جاتے ہیں کہ ہر کلسٹر ایک نقطہ کے قریب ہو، جو کہ-فلیٹ ہے۔ - فلیٹس الگورتھم کچھ ڈیٹا سیٹ کے لیے-یعنی الگورتھم سے بہتر کلسٹرنگ نتیجہ دیتا ہے۔ وضاحتی مسئلہ تشکیل مشاہدات کے ایک سیٹ کو دیکھتے ہوئے جہاں ہر مشاہدہ ایک n-جہتی حقیقی ویکٹر ہے،-فلیٹس الگورتھم کا مقصد-فلیٹس پیدا کرکے مشاہداتی پوائنٹس کو تقسیم کرنا ہے جو ہر مشاہدے کے فاصلے کے مربعوں کے مجموعے کو قریب ترین-فلیٹ تک کم کرتا ہے۔ اے-فلیٹ اس کا ایک ذیلی مجموعہ ہے جو اس سے مطابقت رکھتا ہے۔ مثال کے طور پر، ایک-فلیٹ ایک نقطہ ہے ؛ ایک-فلیٹ ایک لکیر ہے ؛ ایک-فلیٹ ایک طیارہ ہے ؛ ایک-فلیٹ ایک ہائپرپلین ہے۔ - فلیٹ کو مساوات کے لکیری نظام کے حل سیٹ سے نمایاں کیا جا سکتا ہے:، جہاں،۔ اس کی تقسیم کو ظاہر کریں۔ اس مسئلے کو اس طرح وضع کیا جا سکتا ہے کہ آنٹو کا پروجیکشن کہاں ہے۔ نوٹ کریں کہ یہ سے کا فاصلہ ہے۔ الگورتھم الگورتھم کے-مینز الگورتھم کی طرح ہے (یعنی۔ لائیڈ کا الگورتھم) اس میں یہ کلسٹر اسائنمنٹ اور کلسٹر اپ ڈیٹ کے درمیان بدلتا ہے۔ خاص طور پر، الگورتھم-فلیٹس کے ابتدائی سیٹ سے شروع ہوتا ہے، اور مندرجہ ذیل دو مراحل کے درمیان باری باری آگے بڑھتا ہے: کلسٹر اسائنمنٹ (دی گئی-فلیٹس، ہر پوائنٹ کو قریب ترین-فلیٹ پر تفویض کریں):-th کلسٹر کو کلسٹر اپ ڈیٹ کے طور پر اپ ڈیٹ کیا جاتا ہے (کلسٹر اسائنمنٹ دی گئی ہے،-فلیٹس کو اپ ڈیٹ کریں): اس کے لیے، کلسٹر کو تفویض کردہ تمام قطاروں کے مطابق ہونے دیں۔ میٹرکس کے طور پر سیٹ کریں جس کے کالم آرتھونورمل آئجین ویکٹر ہیں جو اور کے کم سے کم آئجین ویلیوز سے مطابقت رکھتے ہیں۔ جب بھی اسائنمنٹ تبدیل نہ ہوں تو رک جائیں۔ کلسٹر اسائنمنٹ مرحلہ مندرجہ ذیل حقیقت کا استعمال کرتا ہے: ایک-فلیٹ اور ایک ویکٹر دیا گیا ہے، جہاں،-فلیٹ سے فاصلہ ہے۔ اس الگورتھم کا کلیدی حصہ یہ ہے کہ کلسٹر کو کیسے اپ ڈیٹ کیا جائے، یعنی۔ دیئے گئے پوائنٹس، ایک-فلیٹ کیسے تلاش کیا جائے جو-فلیٹ سے ہر پوائنٹ کے فاصلے کے مربعوں کے مجموعے کو کم سے کم کرے۔ ریاضیاتی طور پر، یہ مسئلہ یہ ہے کہ: کواڈریٹک آپٹیمائزیشن کے مسئلے کو حل کریں جہاں دیا گیا ہے، اور۔ اس مسئلے کو لاگرانجین ملٹی پلیئر طریقہ استعمال کرتے ہوئے حل کیا جا سکتا ہے اور اس کا حل کلسٹر اپ ڈیٹ مرحلے میں دیا گیا ہے۔ یہ دکھایا جا سکتا ہے کہ الگورتھم تکرار کی ایک محدود تعداد میں ختم ہو جائے گا (ممکنہ تفویض کی کل تعداد سے زیادہ نہیں، جو پابند ہے)۔ اس کے علاوہ، الگورتھم اس مقام پر ختم ہو جائے گا کہ مجموعی مقصد کو یا تو کسی مختلف تفویض سے یا ان کلسٹرز کے لیے نئے کلسٹر طیاروں کی وضاحت سے کم نہیں کیا جا سکتا (ایسے نقطہ کو حوالہ جات میں "مقامی طور پر بہترین" کہا جاتا ہے)۔ یہ کنورجنس نتیجہ اس حقیقت کا نتیجہ ہے جسے بالکل حل کیا جا سکتا ہے۔ وہی کنورجنس نتیجہ-کا مطلب الگورتھم کے لیے ہے کیونکہ کلسٹر اپ ڈیٹ کا مسئلہ بالکل حل کیا جا سکتا ہے۔ مشین لرننگ کے دیگر طریقوں سے تعلق-یعنی الگورتھم-فلیٹس الگورتھم-یعنی الگورتھم کی عمومی شکل ہے۔ در حقیقت،-کا مطلب الگورتھم-فلیٹس الگورتھم ہے کیونکہ ایک نقطہ 0-فلیٹ ہے۔ ان کے تعلق کے باوجود، انہیں مختلف منظرناموں میں استعمال کیا جانا چاہیے۔ - فلیٹس الگورتھم اس معاملے کے لیے کہ ڈیٹا چند کم جہتی خالی جگہوں میں ہے۔ - مطلب الگورتھم اس صورت کے لیے مطلوب ہے کہ کلسٹرز وسیع جہت کے ہوں۔ مثال کے طور پر، اگر تمام مشاہدات دو لائنوں میں ہوں، تو-فلیٹس الگورتھم کے ساتھ استعمال کیا جا سکتا ہے ؛ اگر مشاہدات دو گوسیائی بادل ہیں،-کا مطلب الگورتھم استعمال کیا جا سکتا ہے۔ اسپرس ڈکشنری لرننگ نیچرل سگنلز ایک اعلی جہتی جگہ میں ہوتے ہیں۔ مثال کے طور پر، 1024-بائی-1024 تصویر کا طول و عرض تقریبا 106 ہے، جو زیادہ تر سگنل پروسیسنگ الگورتھم کے لیے بہت زیادہ ہے۔ اعلی جہتی سے چھٹکارا پانے کا ایک طریقہ یہ ہے کہ بنیادی افعال کا ایک مجموعہ تلاش کیا جائے، جیسے کہ اعلی جہتی سگنل کی نمائندگی صرف چند بنیادی افعال کے ذریعے کی جا سکے۔ دوسرے لفظوں میں، سگنل کی نمائندگی کے کوفیشنٹس کم جہتی جگہ میں ہوتے ہیں، جو سگنل پروسیسنگ الگورتھم کو لاگو کرنے میں آسان ہے۔ ادب میں، ویولیٹ ٹرانسفارم عام طور پر امیج پروسیسنگ میں استعمال ہوتا ہے، اور فورئیر ٹرانسفارم عام طور پر آڈیو پروسیسنگ میں استعمال ہوتا ہے۔ بنیادی افعال کے سیٹ کو عام طور پر ڈکشنری کہا جاتا ہے۔ تاہم، یہ واضح نہیں ہے کہ سگنل ڈیٹا سیٹ دیے جانے کے بعد استعمال کرنے کے لیے بہترین لغت کون سی ہے۔ ایک مقبول طریقہ یہ ہے کہ جب اسپارس ڈکشنری لرننگ کے خیال کا استعمال کرتے ہوئے ڈیٹا سیٹ دیا جائے تو ڈکشنری تلاش کی جائے۔ اس کا مقصد ایک لغت تلاش کرنا ہے، تاکہ لغت کے ذریعے اشارے کی بہت کم نمائندگی کی جا سکے۔ اصلاح کا مسئلہ درج ذیل لکھا جا سکتا ہے۔ a-by-میٹرکس کہاں ہے۔ کے ہر کالم ایک سگنل کی نمائندگی کرتے ہیں، اور کل سگنل ہوتے ہیں۔ a-by-میٹرکس ہے۔ کے ہر کالم ایک بنیادی فعل کی نمائندگی کرتے ہیں، اور لغت میں کل بنیادی فعل ہوتے ہیں۔ a-by-میٹرکس ہے۔ (-th کالم) کوفیشنٹس کی نمائندگی کرتے ہیں جب ہم ڈکشنری کو-th کالموں کی نمائندگی کے لیے استعمال کرتے ہیں۔ ویکٹر کے صفر معیار کی نشاندہی کرتا ہے۔ میٹرکس کے فروبینیوس معیار کی نشاندہی کرتا ہے۔ - فلیٹس الگورتھم کا خیال فطرت میں شاذ و نادر لغت سیکھنے سے ملتا جلتا ہے۔ اگر ہم-فلیٹ کو-جہتی ذیلی جگہ تک محدود رکھتے ہیں، تو-فلیٹس الگورتھم محض ایک دیئے گئے سگنل کے لیے بند جہتی ذیلی جگہ تلاش کر رہا ہے۔ اسپارس ڈکشنری لرننگ بھی یہی کام کر رہی ہے، سوائے نمائندگی کے پھیلاؤ پر اضافی رکاوٹوں کے۔ ریاضیاتی طور پر، یہ ظاہر کرنا ممکن ہے کہ-فلیٹس الگورتھم ایک اضافی بلاک ڈھانچے کے ساتھ اسپارس ڈکشنری لرننگ کی شکل کا ہے۔ ایک میٹرکس ہونے دیں، جہاں کے کالم-th فلیٹ کی بنیاد ہیں۔ پھر-th فلیٹ پر سگنل کا پروجیکشن ہے، جہاں ایک جہتی گتانک ہے۔ فلیٹس کی بنیاد کے ارتکاز کو ظاہر کرتے ہیں، یہ ظاہر کرنا آسان ہے کہ-فلیٹ الگورتھم مندرجہ ذیل جیسا ہی ہے۔ کے بلاک ڈھانچے سے مراد یہ حقیقت ہے کہ ہر سگنل کو صرف ایک فلیٹ پر لیبل کیا جاتا ہے۔ دونوں فارمولیشنوں کا موازنہ کرتے ہوئے،-فلیٹ ایک ہی ڈکشنری ماڈلنگ کی طرح ہے جب اور آر پر ایک اضافی بلاک ڈھانچے کے ساتھ۔ صارفین دونوں تصورات کے درمیان تعلقات کے بارے میں مزید بحث کے لیے زلام کے مقالے کا حوالہ دے سکتے ہیں۔ ایپلی کیشنز اور تغیرات درجہ بندی ایک ایسا طریقہ کار ہے جو ان پٹ سگنل کو مختلف کلاسوں میں درجہ بندی کرتا ہے۔ ایک مثال ای میل کو اسپیم یا غیر اسپیم کلاسوں میں درجہ بندی کرنا ہے۔ درجہ بندی کے الگورتھم میں عام طور پر زیر نگرانی سیکھنے کے مرحلے کی ضرورت ہوتی ہے۔ زیر نگرانی سیکھنے کے مرحلے میں، کلاس کی خصوصیات کو سیکھنے کے لیے الگورتھم کے لیے ہر کلاس کے لیے تربیتی ڈیٹا استعمال کیا جاتا ہے۔ درجہ بندی کے مرحلے میں، ایک نئے مشاہدے کو ان خصوصیات کا استعمال کرتے ہوئے کلاس میں درجہ بند کیا جاتا ہے جو پہلے ہی تربیت یافتہ تھیں۔ - فلیٹ الگورتھم درجہ بندی کے لیے استعمال کیا جا سکتا ہے۔ فرض کریں کہ کل m کلاسیں ہیں۔ ہر کلاس کے لیے، فلیٹس کو ٹریننگ ڈیٹا سیٹ کے ذریعے ترجیحی تربیت دی جاتی ہے۔ جب کوئی نیا ڈیٹا آتا ہے تو وہ فلیٹ تلاش کریں جو نئے ڈیٹا کے قریب ہو۔ پھر نیا ڈیٹا قریب ترین فلیٹ کی کلاس سے منسلک ہوتا ہے۔ تاہم، درجہ بندی کی کارکردگی کو مزید بہتر بنایا جا سکتا ہے اگر ہم فلیٹوں پر کچھ ڈھانچہ لگائیں۔ ایک ممکنہ انتخاب یہ ہے کہ مختلف کلاس کے مختلف فلیٹوں کو کافی دور ہونا ضروری ہے۔ کچھ محققین اس خیال کو استعمال کرتے ہیں اور ایک امتیازی کے کیو فلیٹ الگورتھم تیار کرتے ہیں۔ K-میٹرکس ان-فلیٹس الگورتھم، نمائندگی کی غلطی کی پیمائش کے لیے استعمال ہوتا ہے۔ فلیٹ F پر x کے پروجیکشن کو ظاہر کرتا ہے۔ اگر ڈیٹا-طول و عرض کے فلیٹ میں ہے، تو ایک واحد-فلیٹ ڈیٹا کو بہت اچھی طرح سے پیش کر سکتا ہے۔ اس کے برعکس، اگر ڈیٹا بہت زیادہ طول و عرض کی جگہ میں ہے لیکن ایک مشترکہ مرکز کے قریب ہے، تو ڈیٹا کی نمائندگی کرنے کے لیے k-کا مطلب الگورتھم-فلیٹ الگورتھم سے بہتر طریقہ ہے۔ اس کی وجہ یہ ہے کہ-کا مطلب الگورتھم غلطی کی پیمائش کے لیے استعمال ہوتا ہے، جہاں مرکز کی نشاندہی ہوتی ہے۔ K-میٹرکس ایک عمومی شکل ہے جو فلیٹ اور اوسط دونوں کے خیال کو استعمال کرتی ہے۔ کے-میٹرکس میں، غلطی کو مندرجہ ذیل محلانوبس میٹرک سے ماپا جاتا ہے۔ مثبت نیم یقینی میٹرکس کہاں ہے۔ اگر شناخت میٹرکس ہے، تو محلانوبس میٹرک بالکل وہی ہے جو-ذرائع میں استعمال ہونے والی غلطی کی پیمائش ہے۔ اگر شناخت میٹرکس نہیں ہے، تو پھر-فلیٹ غلطی کی پیمائش کے طور پر کچھ سمتوں کی حمایت کرے گا۔ حوالہ جات کلسٹر تجزیہ الگورتھم