Single-linkage clustering
পরিসংখ্যানে, একক-সংযোগ ক্লাস্টারিং শ্রেণিবদ্ধ ক্লাস্টারিংয়ের বিভিন্ন পদ্ধতির মধ্যে একটি। এটি বটম-আপ ফ্যাশনে (অ্যাগ্লোমেরেটিভ ক্লাস্টারিং) গোষ্ঠীবদ্ধকরণ ক্লাস্টারের উপর ভিত্তি করে, প্রতিটি ধাপে দুটি ক্লাস্টারের সংমিশ্রণে যা এখনও একে অপরের মতো একই ক্লাস্টারের অন্তর্গত নয় এমন নিকটতম জোড়া উপাদান ধারণ করে। এই পদ্ধতিটি দীর্ঘ পাতলা গুচ্ছ তৈরি করার প্রবণতা দেখায় যেখানে একই গুচ্ছের নিকটবর্তী উপাদানগুলির দূরত্ব কম থাকে, তবে একটি গুচ্ছের বিপরীত প্রান্তের উপাদানগুলি অন্যান্য গুচ্ছের দুটি উপাদানের তুলনায় একে অপরের থেকে অনেক দূরে থাকতে পারে। কিছু শ্রেণীর তথ্যের জন্য, এটি এমন শ্রেণীগুলিকে সংজ্ঞায়িত করতে অসুবিধা সৃষ্টি করতে পারে যা উপকারে উপবিভাগ করতে পারে। যাইহোক, এটি গ্যালাক্সি ক্লাস্টার বিশ্লেষণের জন্য জ্যোতির্বিজ্ঞানে জনপ্রিয়, যা প্রায়শই পদার্থের দীর্ঘ স্ট্রিং জড়িত থাকতে পারে; এই প্রয়োগে, এটি ফ্রেন্ডস-অফ-ফ্রেন্ডস অ্যালগরিদম নামেও পরিচিত। এগ্লোমেরেটিভ ক্লাস্টারিং পদ্ধতির সংক্ষিপ্ত বিবরণ এগ্লোমেরেটিভ ক্লাস্টারিং প্রক্রিয়ার শুরুতে, প্রতিটি উপাদান তার নিজস্ব একটি ক্লাস্টারে থাকে। ক্লাস্টারগুলি তারপর ক্রমানুসারে বৃহত্তর ক্লাস্টারে একত্রিত হয়, যতক্ষণ না সমস্ত উপাদান একই ক্লাস্টারে থাকে। প্রতিটি ধাপে, স্বল্পতম দূরত্ব দ্বারা পৃথক দুটি গুচ্ছ একত্রিত করা হয়। দুটি ক্লাস্টারের মধ্যে দূরত্ব নির্ধারণ করতে ব্যবহৃত ফাংশন, যা লিঙ্কেজ ফাংশন নামে পরিচিত, সেটিই এগ্লোমেরেটিভ ক্লাস্টারিং পদ্ধতিগুলিকে পৃথক করে। একক-সংযোগ ক্লাস্টারিং-এ, দুটি ক্লাস্টারের মধ্যে দূরত্ব একটি একক জোড়া উপাদান দ্বারা নির্ধারিত হয়ঃ সেই দুটি উপাদান (প্রতিটি ক্লাস্টারে একটি) যা একে অপরের নিকটতম। এই জোড়া-ভিত্তিক দূরত্বগুলির মধ্যে যে কোনও ধাপে থাকা সংক্ষিপ্ততম দুটি ক্লাস্টারকে একত্রিত করে যার উপাদানগুলি জড়িত। পদ্ধতিটি নিকটতম প্রতিবেশী ক্লাস্টারিং নামেও পরিচিত। ক্লাস্টারিংয়ের ফলাফলটি একটি ডেনড্রোগ্রাম হিসাবে কল্পনা করা যেতে পারে, যা দেখায় যে কোন ক্রমে ক্লাস্টারগুলি একত্রিত হয়েছিল এবং প্রতিটি একত্রিত হওয়ার দূরত্ব। গাণিতিকভাবে, সংযোগ ফাংশন-এক্স এবং ওয়াই ক্লাস্টারের মধ্যে দূরত্ব ডি (এক্স, ওয়াই)-এই অভিব্যক্তি দ্বারা বর্ণনা করা হয় যেখানে এক্স এবং ওয়াই ক্লাস্টার হিসাবে বিবেচিত উপাদানগুলির যে কোনও দুটি সেট এবং ডি (এক্স, ওয়াই) দুটি উপাদানের মধ্যে দূরত্বকে বোঝায়। নিষ্ক্রিয় অ্যালগরিদম নিম্নলিখিত অ্যালগরিদমটি একটি সমষ্টিগত পরিকল্পনা যা একটি প্রক্সিমিটি ম্যাট্রিক্সের সারি এবং কলামগুলিকে মুছে দেয় কারণ পুরানো ক্লাস্টারগুলি নতুনগুলির সাথে একীভূত হয়। প্রক্সিমিটি ম্যাট্রিক্সে সমস্ত দূরত্ব রয়েছে। ক্লাস্টারিংগুলিকে ক্রম সংখ্যা বরাদ্দ করা হয় এবং এটি-তম ক্লাস্টারিংয়ের স্তর। ক্রম সংখ্যা m সহ একটি গুচ্ছকে (m) চিহ্নিত করা হয় এবং গুচ্ছগুলির মধ্যে নৈকট্য এবং চিহ্নিত করা হয়। একক সংযোগ অ্যালগরিদম নিম্নলিখিত ধাপগুলি নিয়ে গঠিতঃ স্তর এবং ক্রম সংখ্যা সহ বিচ্ছিন্ন ক্লাস্টারিং দিয়ে শুরু করুন। বর্তমান ক্লাস্টারিং-এ সবচেয়ে অনুরূপ জোড়া ক্লাস্টার খুঁজে বের করুন, ধরুন জোড়া, বর্তমান ক্লাস্টারিং-এ সমস্ত জোড়া ক্লাস্টারের উপর সর্বনিম্ন কোথায়। ক্রম সংখ্যা বৃদ্ধি করুনঃ পরবর্তী ক্লাস্টারিং তৈরি করতে ক্লাস্টারগুলি এবং একটি একক ক্লাস্টারে একত্রিত করুন। ক্লাস্টারের সাথে সম্পর্কিত সারি এবং কলামগুলি মুছে দিয়ে এবং নতুন গঠিত ক্লাস্টারের সাথে সম্পর্কিত একটি সারি এবং কলাম যুক্ত করে প্রক্সিমিটি ম্যাট্রিক্স আপডেট করার জন্য এই ক্লাস্টারিংয়ের স্তর নির্ধারণ করুন। নতুন গুচ্ছ, চিহ্নিত এবং একটি পুরানো গুচ্ছের মধ্যে নৈকট্য হিসাবে সংজ্ঞায়িত করা হয়। যদি সমস্ত বস্তু এক গুচ্ছের মধ্যে থাকে, তাহলে থামুন। অন্যথায়, ধাপ 2-এ যান। কার্যকরী উদাহরণ এই কার্যকরী উদাহরণটি পাঁচটি ব্যাকটেরিয়ার 5এস রাইবোসোমাল আরএনএ সিকোয়েন্স অ্যালাইনমেন্ট থেকে গণনা করা একটি জেসি69 জেনেটিক ডিস্টেন্স ম্যাট্রিক্সের উপর ভিত্তি করেঃ ব্যাসিলাস সাবটিলিস (), ব্যাসিলাস স্টিয়ারোথার্মোফিলাস (), ল্যাকটোব্যাসিলাস ভাইরিডেসেন্স (), অ্যাকোলেপ্লাজমা মোডিকাম (), এবং মাইক্রোকোকাস লুটিয়াস ()। প্রথম ধাপ প্রথম ক্লাস্টারিং আসুন আমরা ধরে নিই যে আমাদের পাঁচটি উপাদান রয়েছে এবং তাদের মধ্যে যুগ্ম দূরত্বের নিম্নলিখিত ম্যাট্রিক্স রয়েছেঃ এই উদাহরণে, এর সর্বনিম্ন মান, তাই আমরা উপাদানগুলিকে ক্লাস্টার করি এবং। প্রথম শাখার দৈর্ঘ্যের অনুমান আসুন সেই নোডটি নির্দেশ করি যার সাথে এবং এখন সংযুক্ত। সেটিং নিশ্চিত করে যে উপাদানগুলি এবং থেকে সমান দূরত্বে রয়েছে। এটি আল্ট্রামেট্রিসিটি অনুমানের প্রত্যাশার সাথে মিলে যায়। শাখাগুলি যুক্ত হয় এবং তারপর দৈর্ঘ্য থাকে (চূড়ান্ত ডেনড্রোগ্রাম দেখুন) প্রথম দূরত্ব ম্যাট্রিক্স আপডেট আমরা তারপর প্রাথমিক প্রক্সিমিটি ম্যাট্রিক্সকে একটি নতুন প্রক্সিমিটি ম্যাট্রিক্সে আপডেট করতে এগিয়ে যাই (নীচে দেখুন), যার ক্লাস্টারিংয়ের কারণে একটি সারি এবং একটি কলাম দ্বারা আকারে হ্রাস পায়। বোল্ড মানগুলি নতুন দূরত্বের সাথে সামঞ্জস্যপূর্ণ, যা প্রথম গুচ্ছের প্রতিটি উপাদান এবং অবশিষ্ট প্রতিটি উপাদানের মধ্যে ন্যূনতম দূরত্ব বজায় রেখে গণনা করা হয়ঃ ইটালিকাইজড মানগুলি ম্যাট্রিক্স আপডেট দ্বারা প্রভাবিত হয় না কারণ তারা প্রথম গুচ্ছের সাথে জড়িত নয় এমন উপাদানগুলির মধ্যে দূরত্বের সাথে সামঞ্জস্যপূর্ণ। দ্বিতীয় ধাপ দ্বিতীয় ক্লাস্টারিং আমরা এখন নতুন দূরত্ব ম্যাট্রিক্স থেকে শুরু করে পূর্ববর্তী তিনটি ক্রিয়া পুনরাবৃত্তি করিঃ এখানে, এবং এর সর্বনিম্ন মান, তাই আমরা উপাদান এবং উপাদানের সাথে ক্লাস্টারে যোগ দিই। দ্বিতীয় শাখার দৈর্ঘ্যের অনুমান আসুন নোডটি নির্দেশ করি যার সাথে, এবং এখন সংযুক্ত। আল্ট্রামেট্রিসিটি সীমাবদ্ধতার কারণে, শাখাগুলি বা এর সাথে এবং এর সাথে যোগ দেয় এবং সমান হয় এবং এর মোট দৈর্ঘ্য নিম্নরূপঃ আমরা অনুপস্থিত শাখার দৈর্ঘ্য অনুমান করিঃ (চূড়ান্ত ডেনড্রোগ্রাম দেখুন) দ্বিতীয় দূরত্ব ম্যাট্রিক্স আপডেট আমরা ম্যাট্রিক্সকে একটি নতুন দূরত্ব ম্যাট্রিক্সে আপডেট করতে এগিয়ে যাই (নীচে দেখুন), আকারে দুটি সারি এবং দুটি কলাম দ্বারা হ্রাস করা হয় কারণ এর সাথে এবং এর ক্লাস্টারিংয়ের কারণেঃ চূড়ান্ত ধাপ চূড়ান্ত ম্যাট্রিক্স হলঃ সুতরাং আমরা ক্লাস্টারে যোগ দিই এবং। (মূল) নোডকে নির্দেশ করা যাক যার সাথে এবং এখন সংযুক্ত। শাখাগুলি যুক্ত হয় এবং তারপর দৈর্ঘ্য থাকেঃ আমরা অবশিষ্ট শাখার দৈর্ঘ্য অনুমান করিঃ একক-সংযোগ ডেনড্রোগ্রাম ডেনড্রোগ্রামটি এখন সম্পূর্ণ। এটি আল্ট্রামেট্রিক কারণ সমস্ত টিপস (,,, এবং) এর থেকে সমান দূরত্বে রয়েছেঃ ডেনড্রোগ্রামটি তাই এর গভীরতম নোড দ্বারা শিকড়যুক্ত। অন্যান্য সংযোগ একক সংযোগ ক্লাস্টারিংয়ের জন্য সরল অ্যালগরিদম মূলত ন্যূনতম বিস্তৃত গাছের জন্য ক্রুস্কালের অ্যালগরিদমের মতোই। যাইহোক, একক সংযোগ ক্লাস্টারিং-এ, যে ক্রমে ক্লাস্টার গঠিত হয় তা গুরুত্বপূর্ণ, যেখানে ন্যূনতম বিস্তৃত গাছের জন্য যা গুরুত্বপূর্ণ তা হল অ্যালগরিদম দ্বারা নির্বাচিত দূরত্ব গঠনকারী জোড়ার বিন্দুর সেট। বিকল্প সংযোগ প্রকল্পগুলির মধ্যে রয়েছে সম্পূর্ণ সংযোগ ক্লাস্টারিং, গড় সংযোগ ক্লাস্টারিং (ইউ. পি. জি. এম. এ এবং ডব্লিউ. পি. জি. এম. এ) এবং ওয়ার্ড পদ্ধতি। সমষ্টিগত ক্লাস্টারিংয়ের জন্য নিষ্ক্রিয় অ্যালগরিদমে, অ্যালগরিদমে আন্তঃ-ক্লাস্টার দূরত্ব গণনা করার জন্য একটি ভিন্ন সূত্র ব্যবহার করে একটি ভিন্ন সংযোগ প্রকল্প বাস্তবায়ন করা যেতে পারে। যে সূত্রটি সামঞ্জস্য করা উচিত তা উপরের অ্যালগরিদম বর্ণনায় গাঢ় পাঠ্য ব্যবহার করে হাইলাইট করা হয়েছে। যাইহোক, নীচে বর্ণিত অ্যালগরিদমের মতো আরও দক্ষ অ্যালগরিদমগুলি সমস্ত সংযোগ স্কিমগুলিতে একইভাবে সাধারণীকরণ করে না। দ্রুততর অ্যালগরিদম একক-সংযোগ ক্লাস্টারিংয়ের জন্য সরল অ্যালগরিদম বুঝতে সহজ তবে সময় জটিলতার সাথে ধীর। 1973 সালে, আর. সিবসন সময় জটিলতা এবং স্থান জটিলতা (উভয় অনুকূল) সহ একটি অ্যালগরিদম প্রস্তাব করেছিলেন যা স্লিংক নামে পরিচিত। স্লিংক অ্যালগরিদম দুটি ফাংশন দ্বারা সংখ্যাযুক্ত আইটেমগুলির একটি সেটের উপর একটি ক্লাস্টারিং উপস্থাপন করে। এই ফাংশনগুলি উভয়ই ক্ষুদ্রতম গুচ্ছ খুঁজে বের করে নির্ধারিত হয় যাতে আইটেম এবং কমপক্ষে একটি বড় সংখ্যাযুক্ত আইটেম উভয়ই থাকে। প্রথম ফাংশন, ক্লাস্টারে বৃহত্তম সংখ্যাযুক্ত আইটেমের সাথে আইটেমটি ম্যাপ করে। দ্বিতীয় ফাংশন, ক্লাস্টার তৈরির সাথে সম্পর্কিত দূরত্বের সাথে আইটেমটি ম্যাপ করে। এই ফাংশনগুলিকে দুটি অ্যারেতে সংরক্ষণ করা যা প্রতিটি আইটেম নম্বরকে তার ফাংশন মানের সাথে ম্যাপ করে স্থান নেয় এবং এই তথ্য ক্লাস্টারিং নিজেই নির্ধারণ করার জন্য যথেষ্ট। যেমন সিবসন দেখায়, যখন আইটেমগুলির সেটে একটি নতুন আইটেম যুক্ত করা হয়, তখন বর্ধিত সেটের জন্য নতুন একক-সংযোগ ক্লাস্টারিংয়ের প্রতিনিধিত্বকারী আপডেটেড ফাংশনগুলি, একইভাবে প্রতিনিধিত্ব করা হয়, সময়মতো পুরানো ক্লাস্টারিং থেকে তৈরি করা যেতে পারে। স্লিংক অ্যালগরিদম তারপর আইটেমগুলির উপর একের পর এক লুপ করে, সেগুলিকে ক্লাস্টারিংয়ের উপস্থাপনায় যুক্ত করে। একটি বিকল্প অ্যালগরিদম, যা একই সর্বোত্তম সময় এবং স্থান সীমার মধ্যে চলে, ন্যূনতম বিস্তৃত গাছের জন্য নিষ্ক্রিয় অ্যালগরিদম এবং ক্রুস্কালের অ্যালগরিদমের মধ্যে সমতুল্যতার উপর ভিত্তি করে। ক্রুস্কালের অ্যালগরিদম ব্যবহার করার পরিবর্তে, কেউ প্রাইমের অ্যালগরিদম ব্যবহার করতে পারে, বাইনারি হিপ ছাড়া একটি বৈচিত্র্যে যা প্রদত্ত আইটেম এবং দূরত্বের ন্যূনতম স্প্যানিং ট্রি (তবে ক্লাস্টারিং নয়) তৈরি করতে সময় এবং স্থান নেয়। তারপর, ন্যূনতম বিস্তৃত গাছের প্রান্ত দ্বারা গঠিত বিরল গ্রাফে ক্রুস্কালের অ্যালগরিদম প্রয়োগ করলে অতিরিক্ত সময় এবং জায়গার মধ্যে ক্লাস্টারিং তৈরি হয়। আরও দেখুন ক্লাস্টার বিশ্লেষণ সম্পূর্ণ-সংযোগ ক্লাস্টারিং শ্রেণিবদ্ধ ক্লাস্টারিং আণবিক ঘড়ি প্রতিবেশী-যুক্ত ইউ. পি. জি. এম. এ ডব্লিউ. পি. জি. এম. এ রেফারেন্স ম্যাটল্যাব ক্লাস্টার বিশ্লেষণ অ্যালগরিদমগুলিতে ব্যবহৃত বাহ্যিক লিঙ্ক লিঙ্ক