Single-linkage clustering
புள்ளிவிவரங்களில், ஒற்றை இணைப்பு கிளஸ்டரிங் என்பது படிநிலை கிளஸ்டரிங்கின் பல முறைகளில் ஒன்றாகும். இது பாட்டம்-அப் பாணியில் (அக்ரோமெரேட்டிவ் கிளஸ்டரிங்) தொகுப்பு கிளஸ்டர்களை அடிப்படையாகக் கொண்டது, ஒவ்வொரு கட்டத்திலும் இரண்டு கிளஸ்டர்களை இணைக்கிறது, அவை ஒருவருக்கொருவர் ஒரே கிளஸ்டரைச் சேராத மிக நெருக்கமான ஜோடி உறுப்புகளைக் கொண்டுள்ளன. இந்த முறை நீண்ட மெல்லிய கிளஸ்டர்களை உருவாக்க முனைகிறது, இதில் ஒரே கிளஸ்டரின் அருகிலுள்ள கூறுகள் சிறிய தூரங்களைக் கொண்டுள்ளன, ஆனால் ஒரு கிளஸ்டரின் எதிர் முனைகளில் உள்ள கூறுகள் மற்ற கிளஸ்டர்களின் இரண்டு கூறுகளை விட ஒருவருக்கொருவர் வெகு தொலைவில் இருக்கலாம். தரவுகளின் சில வகைகளுக்கு, இது தரவை பயனுள்ளதாகப் பிரிக்கக்கூடிய வகுப்புகளை வரையறுப்பதில் சிரமங்களுக்கு வழிவகுக்கும். இருப்பினும், விண்மீன் குழுக்களை பகுப்பாய்வு செய்வதற்கான வானியலில் இது பிரபலமானது, இது பெரும்பாலும் நீண்ட சரங்களை உள்ளடக்கியிருக்கலாம்; இந்த பயன்பாட்டில், இது நண்பர்கள்-நண்பர்கள் வழிமுறை என்றும் அழைக்கப்படுகிறது. திரட்டுதல் கிளஸ்டரிங் முறைகளின் கண்ணோட்டம் திரட்டுதல் கிளஸ்டரிங் செயல்முறையின் தொடக்கத்தில், ஒவ்வொரு உறுப்பும் அதன் சொந்த கிளஸ்டரில் உள்ளது. அனைத்து உறுப்புகளும் ஒரே கிளஸ்டரில் இருக்கும் வரை கிளஸ்டர்கள் பின்னர் தொடர்ச்சியாக பெரிய கிளஸ்டர்களாக இணைக்கப்படுகின்றன. ஒவ்வொரு படியிலும், குறுகிய தூரத்தால் பிரிக்கப்பட்ட இரண்டு கிளஸ்டர்களும் இணைக்கப்படுகின்றன. இரண்டு கிளஸ்டர்களுக்கு இடையிலான தூரத்தை தீர்மானிக்கப் பயன்படுத்தப்படும் செயல்பாடு, இணைப்பு செயல்பாடு என்று அழைக்கப்படுகிறது, இது திரட்டுதல் கிளஸ்டரிங் முறைகளை வேறுபடுத்துகிறது. ஒற்றை இணைப்பு கிளஸ்டரிங்கில், இரண்டு கிளஸ்டர்களுக்கு இடையிலான தூரம் ஒரு ஜோடி உறுப்புகளால் தீர்மானிக்கப்படுகிறதுஃ அந்த இரண்டு கூறுகள் (ஒவ்வொரு கிளஸ்டரிலும் ஒன்று) ஒருவருக்கொருவர் நெருக்கமாக உள்ளன. எந்தவொரு படிநிலையிலும் எஞ்சியிருக்கும் இந்த ஜோடி வாரியான தூரங்களில் மிகக் குறைவானது, உறுப்புகள் சம்பந்தப்பட்ட இரண்டு கிளஸ்டர்களையும் இணைக்க காரணமாகிறது. இந்த முறை அருகிலுள்ள அண்டை கிளஸ்டரிங் என்றும் அழைக்கப்படுகிறது. கிளஸ்டரிங்கின் முடிவை ஒரு டெண்ட்ரோகிராமாக காட்சிப்படுத்தலாம், இது கிளஸ்டர்கள் இணைக்கப்பட்ட வரிசை மற்றும் ஒவ்வொரு இணைப்பும் நடந்த தூரத்தைக் காட்டுகிறது. கணித ரீதியாக, இணைப்பு செயல்பாடு-கிளஸ்டர்கள் X மற்றும் Y க்கு இடையிலான தூரம் D (X, Y)-எக்ஸ் மற்றும் ஒய் ஆகியவை கிளஸ்டர்களாக கருதப்படும் இரண்டு உறுப்புகளின் தொகுப்புகள் மற்றும் டி (x, y) இரண்டு உறுப்புகளுக்கு இடையிலான தூரத்தைக் குறிக்கிறது. முட்டாள்தனமான வழிமுறை பின்வரும் வழிமுறை ஒரு திரட்டும் திட்டமாகும், இது பழைய கிளஸ்டர்கள் புதியவற்றில் இணைக்கப்படுவதால் அருகாமை மேட்ரிக்ஸில் உள்ள வரிசைகள் மற்றும் நெடுவரிசைகளை அழிக்கிறது. அருகாமை மேட்ரிக்ஸ் அனைத்து தூரங்களையும் கொண்டுள்ளது. கிளஸ்டரிங்குகளுக்கு வரிசை எண்கள் ஒதுக்கப்பட்டுள்ளன, இது-th கிளஸ்டரிங்கின் நிலை. வரிசை எண் m கொண்ட ஒரு கிளஸ்டர் (m) குறிக்கப்படுகிறது மற்றும் கிளஸ்டர்களுக்கு இடையிலான அருகாமை மற்றும் குறிக்கப்படுகிறது. ஒற்றை இணைப்பு வழிமுறை பின்வரும் படிகளைக் கொண்டுள்ளதுஃ நிலை மற்றும் வரிசை எண்ணைக் கொண்ட டிஜாயின்ட் கிளஸ்டரிங் மூலம் தொடங்குங்கள். தற்போதைய கிளஸ்டரிங்கில் உள்ள அனைத்து ஜோடி கிளஸ்டர்களுக்கும் குறைந்தபட்சம் இருக்கும் இடத்தின்படி, தற்போதைய கிளஸ்டரிங்கில் மிகவும் ஒத்த ஜோடி கிளஸ்டர்களைக் கண்டறியவும். வரிசை எண்ணை அதிகரிக்கவும்ஃ அடுத்த கிளஸ்டரிங்கை உருவாக்க கிளஸ்டர்களை ஒன்றிணைத்து ஒற்றை கிளஸ்டராக மாற்றவும். கிளஸ்டர்களுடன் தொடர்புடைய வரிசைகள் மற்றும் நெடுவரிசைகளை நீக்குவதன் மூலமும், புதிதாக உருவாக்கப்பட்ட கிளஸ்டருடன் தொடர்புடைய வரிசை மற்றும் நெடுவரிசையைச் சேர்ப்பதன் மூலமும், அருகாமை மேட்ரிக்ஸைப் புதுப்பிக்க இந்த கிளஸ்டரிங்கின் அளவை அமைக்கவும். புதிய கிளஸ்டர், குறிக்கப்பட்ட மற்றும் ஒரு பழைய கிளஸ்டர் இடையே உள்ள அருகாமை என வரையறுக்கப்படுகிறது. அனைத்து பொருட்களும் ஒரே கிளஸ்டரில் இருந்தால், நிறுத்துங்கள். இல்லையெனில், படி 2 க்குச் செல்லுங்கள். செயல்பாட்டு உதாரணம் இந்த செயல்பாட்டு உதாரணம் ஐந்து பாக்டீரியாக்களின் 5S ரைபோசோமல் ஆர்என்ஏ வரிசை சீரமைப்பிலிருந்து கணக்கிடப்பட்ட ஜேசி69 மரபணு தூர மேட்ரிக்ஸை அடிப்படையாகக் கொண்டதுஃ பேசிலஸ் சப்டிலிஸ் (β), பேசிலஸ் ஸ்டியரோதர்மோபிலஸ் (β), லாக்டோபாகிலஸ் விரிடெசென்ஸ் (β), அகோலெபிளாஸ்மா மோடிகம் (β), மற்றும் மைக்ரோகோக்கஸ் லுடியஸ் (β). முதல் படி முதல் கிளஸ்டரிங் நம்மிடம் ஐந்து உறுப்புகள் மற்றும் அவற்றுக்கிடையேயான ஜோடி வாரியான தூரங்களின் பின்வரும் அணி உள்ளது என்று வைத்துக்கொள்வோம்ஃ இந்த எடுத்துக்காட்டில், மிகக் குறைந்த மதிப்பு, எனவே நாம் கூறுகளை கிளஸ்டர் செய்கிறோம் மற்றும். முதல் கிளை நீளம் மதிப்பீடு எந்த முனையுடன் இப்போது இணைக்கப்பட்டுள்ளது என்பதைக் குறிக்கலாம். அமைத்தல் கூறுகள் மற்றும் அவற்றிலிருந்து சம தூரத்தில் இருப்பதை உறுதி செய்கிறது. இது அல்ட்ராமெட்ரிசிட்டி கருதுகோளின் எதிர்பார்ப்புடன் ஒத்திருக்கிறது. கிளைகள் இணைவதற்கும் பின்னர் நீளங்களைக் கொண்டிருப்பதற்கும் (இறுதி டெண்ட்ரோகிராமைப் பார்க்கவும்) முதல் தூர மேட்ரிக்ஸ் புதுப்பிப்பு நாம் பின்னர் ஆரம்ப அருகாமை மேட்ரிக்ஸை ஒரு புதிய அருகாமை மேட்ரிக்ஸில் புதுப்பிக்கத் தொடங்குகிறோம் (கீழே காண்க), ஒரு வரிசை மற்றும் ஒரு நெடுவரிசையால் அளவு குறைக்கப்படுகிறது. முதல் கிளஸ்டரின் ஒவ்வொரு உறுப்புக்கும் மீதமுள்ள ஒவ்வொரு உறுப்புக்கும் இடையிலான குறைந்தபட்ச தூரத்தைத் தக்கவைத்துக்கொள்வதன் மூலம் கணக்கிடப்படும் புதிய தூரங்களுடன் ஒத்திருக்கும் தடித்த மதிப்புகள்ஃ முதல் கிளஸ்டரில் ஈடுபடாத உறுப்புகளுக்கு இடையிலான தூரங்களுடன் ஒத்திருப்பதால் மேட்ரிக்ஸ் புதுப்பிப்பால் இத்தாலிக் செய்யப்பட்ட மதிப்புகள் பாதிக்கப்படுவதில்லை. இரண்டாவது படி இரண்டாவது கிளஸ்டரிங் புதிய தூர மேட்ரிக்ஸில் தொடங்கி முந்தைய மூன்று செயல்களை இப்போது மீண்டும் வலியுறுத்துகிறோம்ஃ இங்கே, மற்றும் மிகக் குறைந்த மதிப்புகள், எனவே நாம் கிளஸ்டரை உறுப்பு மற்றும் உறுப்புடன் இணைக்கிறோம். இரண்டாவது கிளை நீளம் மதிப்பீடு எந்த முனையுடன் இணைக்கப்பட்டுள்ளது என்பதைக் குறிக்கலாம். அல்ட்ராமெட்ரிசிட்டி கட்டுப்பாடு காரணமாக, கிளைகள் சேரும் அல்லது, மற்றும், மற்றும் சமமாக இருக்க வேண்டும் மற்றும் பின்வரும் மொத்த நீளத்தைக் கொண்டுள்ளனஃ காணாமல் போன கிளை நீளத்தை நாம் கண்டறிகிறோம்ஃ (இறுதி டெண்ட்ரோகிராமைப் பார்க்கவும்) இரண்டாவது தூர மேட்ரிக்ஸ் புதுப்பிப்பு நாம் மேட்ரிக்ஸை ஒரு புதிய தூர மேட்ரிக்ஸில் புதுப்பிக்கத் தொடங்குகிறோம் (கீழே காண்க), இரண்டு வரிசைகள் மற்றும் இரண்டு நெடுவரிசைகளால் அளவு குறைக்கப்படுகிறது, ஏனெனில் உடன் மற்றும் உடன் கிளஸ்டரிங்ஃ இறுதி படி இறுதி மேட்ரிக்ஸ்ஃ எனவே நாம் கிளஸ்டர்களை இணைக்கிறோம் மற்றும். இப்போது இணைக்கப்பட்டுள்ள (ரூட்) முனையைக் குறிக்கலாம். கிளைகள் இணைவதற்கும் பின்னர் நீளங்களைக் கொண்டிருப்பதற்கும்ஃ மீதமுள்ள கிளையின் நீளத்தை நாம் கணக்கிடுகிறோம்ஃ ஒற்றை இணைப்பு டென்ட்ரோகிராம் டென்ட்ரோகிராம் இப்போது நிறைவடைந்துள்ளது. இது அல்ட்ராமெட்ரிக் ஆகும், ஏனெனில் அனைத்து நுனிகளும் (,,, மற்றும்) பின்வருவனவற்றிலிருந்து சம தூரத்தில் உள்ளனஃ எனவே டென்ட்ரோகிராம் அதன் ஆழமான முனையால் வேரூன்றியுள்ளது. பிற இணைப்புகள் ஒற்றை இணைப்பு கிளஸ்டரிங்கிற்கான அப்பாவித்தனமான வழிமுறை அடிப்படையில் குறைந்தபட்ச பரவலான மரங்களுக்கான க்ருஸ்கலின் வழிமுறைக்கு சமம். இருப்பினும், ஒற்றை இணைப்பு கிளஸ்டரிங்கில், கிளஸ்டர்கள் உருவாகும் வரிசை முக்கியமானது, அதே நேரத்தில் குறைந்தபட்ச பரவலான மரங்களுக்கு முக்கியமானது வழிமுறையால் தேர்ந்தெடுக்கப்பட்ட தூரங்களை உருவாக்கும் ஜோடி புள்ளிகளின் தொகுப்பாகும். மாற்று இணைப்புத் திட்டங்களில் முழுமையான இணைப்பு கிளஸ்டரிங், சராசரி இணைப்பு கிளஸ்டரிங் (யுபிஜிஎம்ஏ மற்றும் டபிள்யூபிஜிஎம்ஏ) மற்றும் வார்டு முறை ஆகியவை அடங்கும். ஒருங்கிணைந்த கிளஸ்டரிங்கிற்கான அப்பாவி வழிமுறையில், வழிமுறையில் உள்ள கிளஸ்டருக்கு இடையிலான தூரங்களைக் கணக்கிட வேறு சூத்திரத்தைப் பயன்படுத்துவதன் மூலம் வேறுபட்ட இணைப்புத் திட்டத்தை செயல்படுத்தலாம். சரிசெய்யப்பட வேண்டிய சூத்திரம் மேலே உள்ள வழிமுறை விளக்கத்தில் தைரியமான உரையைப் பயன்படுத்தி முன்னிலைப்படுத்தப்பட்டுள்ளது. இருப்பினும், கீழே விவரிக்கப்பட்டுள்ளதைப் போன்ற மிகவும் திறமையான வழிமுறைகள் அனைத்து இணைப்புத் திட்டங்களுக்கும் ஒரே மாதிரியாக பொதுமைப்படுத்தப்படுவதில்லை. வேகமான வழிமுறைகள் ஒற்றை இணைப்பு கிளஸ்டரிங்கிற்கான அப்பாவித்தனமான வழிமுறையைப் புரிந்துகொள்வது எளிதானது, ஆனால் நேர சிக்கலுடன் மெதுவாக உள்ளது. 1973 ஆம் ஆண்டில், ஆர். சிப்சன் நேர சிக்கல் மற்றும் விண்வெளி சிக்கல் (உகந்த இரண்டும்) கொண்ட ஒரு வழிமுறையை முன்மொழிந்தார், இது SLINK என்று அழைக்கப்படுகிறது. ஸ்லிங்க் அல்காரிதம் இரண்டு செயல்பாடுகளால் எண்ணப்பட்ட உருப்படிகளின் தொகுப்பில் ஒரு கிளஸ்டரிங்கை குறிக்கிறது. இந்த செயல்பாடுகள் இரண்டும் உருப்படி மற்றும் குறைந்தபட்சம் ஒரு பெரிய எண்ணைக் கொண்ட உருப்படியைக் கொண்ட மிகச்சிறிய கிளஸ்டரைக் கண்டுபிடிப்பதன் மூலம் தீர்மானிக்கப்படுகின்றன. முதல் செயல்பாடு, கிளஸ்டரில் உள்ள மிகப்பெரிய எண்ணிக்கையிலான உருப்படியுடன் உருப்படியை வரைபடமாக்குகிறது. இரண்டாவது செயல்பாடு, கிளஸ்டர் உருவாக்கத்துடன் தொடர்புடைய தூரத்திற்கு உருப்படியை வரைபடமாக்குகிறது. ஒவ்வொரு உருப்படி எண்ணையும் அதன் செயல்பாட்டு மதிப்புடன் வரைபடமாக்கும் இரண்டு வரிசைகளில் இந்த செயல்பாடுகளைச் சேமிப்பதற்கு இடம் எடுக்கும், மேலும் இந்த தகவல் கிளஸ்டரிங்கைத் தீர்மானிக்க போதுமானது. சிப்சன் காட்டுவது போல், உருப்படிகளின் தொகுப்பில் ஒரு புதிய உருப்படி சேர்க்கப்படும்போது, அதே வழியில் குறிப்பிடப்படும் ஆக்மென்டட் செட்டிற்கான புதிய ஒற்றை இணைப்பு கிளஸ்டரிங்கைக் குறிக்கும் புதுப்பிக்கப்பட்ட செயல்பாடுகளை பழைய கிளஸ்டரிங்கிலிருந்து சரியான நேரத்தில் உருவாக்க முடியும். SLINK வழிமுறை பின்னர் உருப்படிகளின் மீது சுழல்கிறது, ஒவ்வொன்றாக, அவற்றை கிளஸ்டரிங்கின் பிரதிநிதித்துவத்தில் சேர்க்கிறது. ஒரே உகந்த நேரம் மற்றும் இடைவெளி வரம்புகளில் இயங்கும் ஒரு மாற்று வழிமுறை, குறைந்தபட்ச பரவலான மரங்களுக்கான அப்பாவித்தனமான வழிமுறைக்கும் க்ருஸ்கலின் வழிமுறைக்கும் இடையிலான சமநிலையை அடிப்படையாகக் கொண்டது. க்ருஸ்கலின் வழிமுறையைப் பயன்படுத்துவதற்குப் பதிலாக, ஒருவர் ப்ரைமின் வழிமுறையைப் பயன்படுத்தலாம், பைனரி குவியல்கள் இல்லாத மாறுபாட்டில், கொடுக்கப்பட்ட உருப்படிகள் மற்றும் தூரங்களின் குறைந்தபட்ச பரவலான மரத்தை (ஆனால் கிளஸ்டரிங் அல்ல) உருவாக்க நேரமும் இடமும் எடுக்கும். பின்னர், குறைந்தபட்ச பரவலான மரத்தின் விளிம்புகளால் உருவாக்கப்பட்ட சிறிய வரைபடத்திற்கு க்ருஸ்கலின் வழிமுறையைப் பயன்படுத்துவது கூடுதல் நேரத்திலும் இடத்திலும் கிளஸ்டரிங்கை உருவாக்குகிறது. கிளஸ்டர் பகுப்பாய்வையும் பார்க்கவும் முழுமையான இணைப்பு கிளஸ்டரிங் படிநிலை கிளஸ்டரிங் மூலக்கூறு கடிகாரம் அண்டை-இணைந்த யுபிஜிஎம்ஏ டபிள்யூபிஜிஎம்ஏ குறிப்புகள் வெளிப்புற இணைப்புகள் மேட்லேப் கிளஸ்டர் பகுப்பாய்வு வழிமுறைகளில் பயன்படுத்தப்படும் இணைப்புகள்