Step detection
পরিসংখ্যান এবং সংকেত প্রক্রিয়াকরণে, ধাপ সনাক্তকরণ (ধাপ মসৃণকরণ, ধাপ ফিল্টারিং, স্থানান্তর সনাক্তকরণ, লাফ সনাক্তকরণ বা প্রান্ত সনাক্তকরণ নামেও পরিচিত) একটি সময় সিরিজ বা সংকেতের গড় স্তরে আকস্মিক পরিবর্তন (ধাপ, লাফ, স্থানান্তর) খুঁজে বের করার প্রক্রিয়া। এটি সাধারণত পরিসংখ্যানগত পদ্ধতির একটি বিশেষ কেস হিসাবে বিবেচিত হয় যা পরিবর্তন সনাক্তকরণ বা পরিবর্তন বিন্দু সনাক্তকরণ হিসাবে পরিচিত। প্রায়শই, ধাপটি ছোট হয় এবং সময় সিরিজটি কোনও ধরণের গোলমাল দ্বারা দূষিত হয় এবং এটি সমস্যাটিকে চ্যালেঞ্জিং করে তোলে কারণ শব্দ দ্বারা ধাপটি লুকিয়ে থাকতে পারে। অতএব, পরিসংখ্যানগত এবং/অথবা সংকেত প্রক্রিয়াকরণ অ্যালগরিদমগুলি প্রায়শই প্রয়োজন হয়। ধাপ সনাক্তকরণ সমস্যা একাধিক বৈজ্ঞানিক এবং প্রকৌশল প্রসঙ্গে ঘটে, উদাহরণস্বরূপ পরিসংখ্যানগত প্রক্রিয়া নিয়ন্ত্রণে (নিয়ন্ত্রণ চার্টটি সবচেয়ে সরাসরি সম্পর্কিত পদ্ধতি), অনুসন্ধান ভূ-পদার্থবিজ্ঞানে (যেখানে সমস্যাটি স্ট্র্যাটিগ্রাফিক জোনে একটি ভাল-লগ রেকর্ডিং বিভাগ করা), জেনেটিক্সে (মাইক্রো অ্যারে তথ্যকে অনুরূপ অনুলিপি-সংখ্যার ব্যবস্থায় পৃথক করার সমস্যা), এবং বায়োফিজিক্সে (সময়-অবস্থানের ট্রেসে রেকর্ড করা একটি আণবিক যন্ত্রে অবস্থার রূপান্তর সনাক্ত করা)। 2ডি সিগন্যালের জন্য, প্রান্ত সনাক্তকরণ সম্পর্কিত সমস্যাটি চিত্র প্রক্রিয়াকরণের জন্য নিবিড়ভাবে অধ্যয়ন করা হয়েছে। অ্যালগরিদম যখন ডেটা আসার সাথে সাথে ধাপ সনাক্তকরণ অবশ্যই সম্পাদন করতে হবে, তখন সাধারণত অনলাইন অ্যালগরিদম ব্যবহার করা হয় এবং এটি ক্রমিক বিশ্লেষণের একটি বিশেষ ক্ষেত্রে পরিণত হয়। এই ধরনের অ্যালগরিদমগুলির মধ্যে রয়েছে শাস্ত্রীয় সি. ইউ. এস. ইউ. এম পদ্ধতি যা গড় পরিবর্তনের ক্ষেত্রে প্রয়োগ করা হয়। বিপরীতে, অফলাইন অ্যালগরিদমগুলি ডেটা পাওয়ার অনেক পরে সম্ভাব্যভাবে প্রয়োগ করা হয়। ডিজিটাল ডেটাতে ধাপ সনাক্তকরণের জন্য বেশিরভাগ অফলাইন অ্যালগরিদমকে টপ-ডাউন, বটম-আপ, স্লাইডিং উইন্ডো বা গ্লোবাল পদ্ধতি হিসাবে শ্রেণীবদ্ধ করা যেতে পারে। এই অ্যালগরিদমগুলি এই ধারণা দিয়ে শুরু হয় যে কোনও পদক্ষেপ নেই এবং সম্ভাব্য প্রার্থী পদক্ষেপগুলি একবারে প্রবর্তন করে, প্রতিটি প্রার্থীকে এমন একটি খুঁজে বের করার জন্য পরীক্ষা করে যা কিছু মানদণ্ডকে ন্যূনতম করে (যেমন আনুমানিক, অন্তর্নিহিত পিসওয়াইজ ধ্রুবক সংকেতের সর্বনিম্ন-বর্গ ফিট)। একটি উদাহরণ হল স্টেপওয়াইজ জাম্প প্লেসমেন্ট অ্যালগরিদম, যা প্রথম জিওফিজিক্যাল সমস্যায় অধ্যয়ন করা হয়েছে, যা আধুনিক বায়োফিজিক্সে সাম্প্রতিক ব্যবহার খুঁজে পেয়েছে। বটম-আপ বটম-আপ অ্যালগরিদমগুলি টপ-ডাউন পদ্ধতিতে "বিপরীত" পদ্ধতি গ্রহণ করে, প্রথমে ধরে নেয় যে ডিজিটাল সিগন্যালে প্রতিটি নমুনার মধ্যে একটি ধাপ রয়েছে এবং তারপরে প্রতিটি প্রার্থী একত্রিত হওয়ার জন্য পরীক্ষিত কিছু মানদণ্ডের উপর ভিত্তি করে পর্যায়ক্রমে পদক্ষেপগুলি একত্রিত করে। স্লাইডিং উইন্ডো সিগন্যালের একটি ছোট "উইন্ডো" বিবেচনা করে, এই অ্যালগরিদমগুলি উইন্ডোটির মধ্যে ঘটে যাওয়া একটি ধাপের প্রমাণ সন্ধান করে। উইন্ডোটি সময় সিরিজ জুড়ে "স্লাইড" করে, একবারে এক ধাপ। একটি ধাপের প্রমাণ পরিসংখ্যানগত পদ্ধতি দ্বারা পরীক্ষা করা হয়, উদাহরণস্বরূপ, দুই-নমুনা ছাত্রের টি-টেস্ট ব্যবহার করে। বিকল্পভাবে, মাঝারি ফিল্টারের মতো একটি অরৈখিক ফিল্টার সিগন্যালে প্রয়োগ করা হয়। এই ধরনের ফিল্টারগুলি আকস্মিক পদক্ষেপগুলি সংরক্ষণ করার সময় শব্দটি সরিয়ে ফেলার চেষ্টা করে। গ্লোবাল গ্লোবাল অ্যালগরিদমগুলি একবারে পুরো সংকেতটি বিবেচনা করে এবং কোনও ধরণের অপ্টিমাইজেশন পদ্ধতির মাধ্যমে সংকেতের ধাপগুলি খুঁজে বের করার চেষ্টা করে। অ্যালগরিদমগুলির মধ্যে রয়েছে ওয়েভলেট পদ্ধতি এবং মোট বৈচিত্র্য ডিনোইজিং যা উত্তল অপ্টিমাইজেশনের পদ্ধতি ব্যবহার করে। যেখানে ধাপগুলি মার্কভ চেইন হিসাবে মডেল করা যেতে পারে, সেখানে হিডেন মার্কভ মডেলগুলিও প্রায়শই ব্যবহার করা হয় (বায়োফিজিক্স সম্প্রদায়ের একটি জনপ্রিয় পদ্ধতি)। যখন গড়ের মাত্র কয়েকটি অনন্য মান থাকে, তখন কে-মানে ক্লাস্টারিংও ব্যবহার করা যেতে পারে। ধাপ সনাক্তকরণের জন্য রৈখিক বনাম অরৈখিক সংকেত প্রক্রিয়াকরণ পদ্ধতি কারণ ধাপ এবং (স্বাধীন) শব্দের তাত্ত্বিকভাবে অসীম ব্যান্ডউইথ রয়েছে এবং তাই ফুরিয়ার ভিত্তিতে ওভারল্যাপ হয়, ধাপ সনাক্তকরণের জন্য সংকেত প্রক্রিয়াকরণ পদ্ধতিগুলি সাধারণত লো পাস ফিল্টারের মতো শাস্ত্রীয় মসৃণ কৌশল ব্যবহার করে না। পরিবর্তে, বেশিরভাগ অ্যালগরিদম স্পষ্টভাবে অরৈখিক বা সময়-পরিবর্তিত হয়। ধাপ সনাক্তকরণ এবং পিসওয়াইজ ধ্রুবক সংকেত যেহেতু ধাপ সনাক্তকরণের লক্ষ্য হল একটি সংকেতের গড়ের মধ্যে তাৎক্ষণিক লাফগুলির একটি সিরিজ খুঁজে বের করা, তাই কাঙ্ক্ষিত, অন্তর্নিহিত, গড় সংকেতটি পিসওয়াইজ ধ্রুবক। এই কারণে, ধাপ সনাক্তকরণকে শব্দের দ্বারা দূষিত একটি পিসওয়াইজ ধ্রুবক সংকেত পুনরুদ্ধারের সমস্যা হিসাবে লাভজনকভাবে দেখা যেতে পারে। পিসওয়াইজ ধ্রুবক সংকেতের জন্য দুটি পরিপূরক মডেল রয়েছেঃ কয়েকটি নট সহ 0-ডিগ্রি স্প্লাইন হিসাবে, বা কয়েকটি অনন্য স্তর সহ স্তর সেট হিসাবে। ধাপ সনাক্তকরণের জন্য অনেক অ্যালগরিদম তাই 0-ডিগ্রি স্প্লাইন ফিটিং বা লেভেল সেট পুনরুদ্ধার পদ্ধতি হিসাবে সর্বোত্তমভাবে বোঝা যায়। লেভেল সেট পুনরুদ্ধার হিসাবে ধাপ সনাক্তকরণ যখন গড়ের মাত্র কয়েকটি অনন্য মান থাকে, তখন ক্লাস্টারিং কৌশল যেমন কে-মিন ক্লাস্টারিং বা মিন-শিফট উপযুক্ত। এই কৌশলগুলি অন্তর্নিহিত পিসওয়াইজ ধ্রুবক সংকেতের একটি স্তর সেট বিবরণ খুঁজে বের করার পদ্ধতি হিসাবে সর্বোত্তমভাবে বোঝা যায়। 0-ডিগ্রি স্প্লাইন ফিটিং হিসাবে ধাপ সনাক্তকরণ অনেক অ্যালগরিদম স্পষ্টভাবে ধাপগুলি সনাক্ত করার জন্য (ধাপে ধাপে লাফ বসানোর পদ্ধতি সহ) গোলমাল সংকেতের সাথে 0-ডিগ্রি স্প্লাইনগুলি ফিট করে, তবে অন্যান্য জনপ্রিয় অ্যালগরিদম রয়েছে যা কিছু রূপান্তরের পরে স্প্লাইন ফিটিং পদ্ধতি হিসাবেও দেখা যেতে পারে, উদাহরণস্বরূপ মোট বৈচিত্র্য ডিনোইজিং। উপরে উল্লিখিত সমস্ত অ্যালগরিদমের নির্দিষ্ট পরিস্থিতিতে নির্দিষ্ট সুবিধা এবং অসুবিধা রয়েছে, তবুও, আশ্চর্যজনকভাবে এই ধাপ সনাক্তকরণ অ্যালগরিদমগুলির একটি বড় সংখ্যা আরও সাধারণ অ্যালগরিদমের বিশেষ ক্ষেত্রে। এই অ্যালগরিদমটিতে একটি বিশ্বব্যাপী কার্যকারিতার ন্যূনতমকরণ জড়িত রয়েছেঃ এখানে, i = 1 এর জন্য xi, N হল দৈর্ঘ্য N-এর বিচ্ছিন্ন-সময় ইনপুট সংকেত, এবং mi হল অ্যালগরিদম থেকে সংকেত আউটপুট। লক্ষ্য হল আউটপুট সংকেত m-এর সাপেক্ষে H [m] হ্রাস করা। ফাংশনের রূপ নির্দিষ্ট অ্যালগরিদম নির্ধারণ করে। উদাহরণস্বরূপ, নির্বাচন করুনঃ যেখানে I (S) = 0 যদি S শর্তটি মিথ্যা হয়, এবং অন্যথায় একটি, নিয়মিতকরণ পরামিতি সহ মোট বৈচিত্র্য সূচক অ্যালগরিদম অর্জন করে। একইভাবেঃ ইনপুট সিগন্যাল x দিয়ে শুরু করা একটি অভিযোজিত ধাপ আকারের অয়লার ইন্টিগ্রেটর ব্যবহার করার সময় গড় স্থানান্তর অ্যালগরিদমের দিকে নিয়ে যায়। এখানে W> 0 একটি পরামিতি যা গড় স্থানান্তর কার্নেলের সমর্থন নির্ধারণ করে। আরেকটি উদাহরণ হলঃ দ্বিপক্ষীয় ফিল্টারের দিকে নিয়ে যাওয়া, যেখানে টোনাল কার্নেল প্যারামিটার, এবং ডাব্লু হল স্থানিক কার্নেল সমর্থন। আরও একটি বিশেষ ক্ষেত্রেঃ অ্যালগরিদমগুলির একটি গোষ্ঠী নির্দিষ্ট করা যা লোভের সাথে সিগন্যালে 0-ডিগ্রি স্প্লাইনগুলি ফিট করার চেষ্টা করে। এখানে, শূন্য হিসাবে সংজ্ঞায়িত করা হয় যদি x = 0, এবং অন্যথায় একটি। সমীকরণ ()-এর নির্দিষ্ট পছন্দ দ্বারা সংজ্ঞায়িত অনেকগুলি কার্যকারিতা উত্তল হয়ঃ উত্তল অপ্টিমাইজেশনের পদ্ধতি ব্যবহার করে এগুলি হ্রাস করা যেতে পারে। এখনও অন্যগুলি অ-উত্তল তবে এই কার্যকারিতা হ্রাস করার জন্য অ্যালগরিদমগুলির একটি পরিসীমা তৈরি করা হয়েছে। পটস মডেল ব্যবহার করে ধাপ সনাক্তকরণ ধাপ সনাক্তকরণের জন্য একটি ধ্রুপদী বৈচিত্র্যময় পদ্ধতি হল পটস মডেল। এটি নন-কনভেক্স অপ্টিমাইজেশন সমস্যা দ্বারা দেওয়া হয় এই শব্দটি লাফ দেওয়ার সংখ্যাকে শাস্তি দেয় এবং এই শব্দটি x তথ্যের প্রতি বিশ্বস্ততা পরিমাপ করে। প্যারামিটার γ> 0 নিয়মিততা এবং ডেটা বিশ্বস্ততার মধ্যে বিনিময় নিয়ন্ত্রণ করে। যেহেতু মিনিমাইজারটি পিসওয়াইজ ধ্রুবক, তাই গ্রেডিয়েন্টের অ-শূন্য অবস্থানগুলি দ্বারা পদক্ষেপগুলি দেওয়া হয়। এর জন্য এবং দ্রুত অ্যালগরিদম রয়েছে যা পটস সমস্যার সঠিক সমাধান দেয়। আরও দেখুন টাইম-সিরিজ সেগমেন্টেশন রেফারেন্স এক্সটার্নাল লিঙ্ক পি. ডব্লিউ. সি. টুলসঃ ফ্লেক্সিবল ম্যাটল্যাব এবং পাইথন সফ্টওয়্যার পিসওয়াইজ কনস্ট্যান্ট ডিনোইজিং দ্বারা ধাপ সনাক্তকরণের জন্য পটসল্যাবঃ পটস মডেলের উপর ভিত্তি করে পিসওয়াইজ কনস্ট্যান্ট অনুমানের জন্য ম্যাটল্যাব টুলবক্স পরিবর্তন সনাক্তকরণ অরৈখিক ফিল্টার পরিসংখ্যানগত সংকেত প্রক্রিয়াকরণ বৈশিষ্ট্য সনাক্তকরণ (কম্পিউটার দৃষ্টি)