Single-linkage clustering
આંકડામાં, સિંગલ-લિન્કેજ ક્લસ્ટરિંગ એ અધિક્રમિક ક્લસ્ટરિંગની ઘણી પદ્ધતિઓમાંની એક છે. તે બોટમ-અપ ફેશન (એગ્લોમેરેટિવ ક્લસ્ટરિંગ) માં જૂથોના જૂથ પર આધારિત છે, દરેક તબક્કે બે જૂથોને સંયોજિત કરે છે જેમાં તત્વોની સૌથી નજીકની જોડી હોય છે જે હજુ સુધી એકબીજા જેવા જ સમૂહ સાથે સંબંધિત નથી. આ પદ્ધતિ લાંબા પાતળા સમૂહોનું ઉત્પાદન કરે છે જેમાં એક જ સમૂહના નજીકના ઘટકોનું અંતર ઓછું હોય છે, પરંતુ સમૂહના વિરુદ્ધ છેડા પરના ઘટકો અન્ય સમૂહના બે ઘટકો કરતાં એકબીજાથી ઘણા દૂર હોઈ શકે છે. ડેટાના કેટલાક વર્ગો માટે, આ વર્ગોને વ્યાખ્યાયિત કરવામાં મુશ્કેલીઓ તરફ દોરી શકે છે જે ડેટાને ઉપયોગી રીતે પેટા વિભાજિત કરી શકે છે. જો કે, તે આકાશગંગાના સમૂહોનું વિશ્લેષણ કરવા માટે ખગોળશાસ્ત્રમાં લોકપ્રિય છે, જેમાં ઘણીવાર દ્રવ્યના લાંબા તાર સામેલ હોઈ શકે છે; આ એપ્લિકેશનમાં, તેને ફ્રેન્ડ્સ-ઓફ-ફ્રેન્ડ્સ અલ્ગોરિધમ તરીકે પણ ઓળખવામાં આવે છે. એગ્લોમેરેટિવ ક્લસ્ટરિંગ પદ્ધતિઓની ઝાંખી એગ્લોમેરેટિવ ક્લસ્ટરિંગ પ્રક્રિયાની શરૂઆતમાં, દરેક તત્વ તેના પોતાના સમૂહમાં હોય છે. જ્યાં સુધી બધા ઘટકો એક જ સમૂહમાં ન હોય ત્યાં સુધી સમૂહને ક્રમિક રીતે મોટા સમૂહમાં જોડવામાં આવે છે. દરેક તબક્કે, ટૂંકા અંતર દ્વારા અલગ કરાયેલા બે સમૂહને જોડવામાં આવે છે. બે ક્લસ્ટરો વચ્ચેનું અંતર નક્કી કરવા માટે વપરાતું કાર્ય, જેને જોડાણ કાર્ય તરીકે ઓળખવામાં આવે છે, તે જ એગ્ગ્લોમેરેટિવ ક્લસ્ટરિંગ પદ્ધતિઓને અલગ પાડે છે. સિંગલ-લિન્કેજ ક્લસ્ટરિંગમાં, બે ક્લસ્ટરો વચ્ચેનું અંતર તત્વોની એક જોડી દ્વારા નક્કી થાય છેઃ તે બે ઘટકો (દરેક ક્લસ્ટરમાં એક) જે એકબીજાની સૌથી નજીક છે. આ જોડી મુજબના અંતરમાંથી સૌથી નાનું અંતર જે કોઈપણ તબક્કે રહે છે તે બે સમૂહોનું કારણ બને છે જેમના ઘટકો સામેલ છે. આ પદ્ધતિને નજીકના પડોશી ક્લસ્ટરિંગ તરીકે પણ ઓળખવામાં આવે છે. ક્લસ્ટરિંગના પરિણામને ડેંડ્રોગ્રામ તરીકે જોઈ શકાય છે, જે દર્શાવે છે કે ક્લસ્ટરો કયા ક્રમમાં મર્જ થયા હતા અને દરેક મર્જ કયા અંતરે થયું હતું. ગાણિતિક રીતે, જોડાણ કાર્ય-સમૂહ X અને Y વચ્ચેનું અંતર D (X, Y)-એ અભિવ્યક્તિ દ્વારા વર્ણવવામાં આવે છે જ્યાં X અને Y એ સમૂહ તરીકે ગણવામાં આવતા તત્વોના કોઈપણ બે સમૂહ છે, અને d (x, y) એ બે તત્વ x અને y વચ્ચેનું અંતર સૂચવે છે. નિષ્કપટ અલ્ગોરિધમ નીચેનું અલ્ગોરિધમ એક એકત્રીકરણ યોજના છે જે નિકટતા મેટ્રિક્સમાં પંક્તિઓ અને સ્તંભોને ભૂંસી નાખે છે કારણ કે જૂના ક્લસ્ટરોને નવા સમૂહમાં ભેળવી દેવામાં આવે છે. નિકટતા મેટ્રિક્સમાં તમામ અંતર હોય છે. ક્લસ્ટરિંગ્સને ક્રમ સંખ્યાઓ સોંપવામાં આવે છે અને તે-th ક્લસ્ટરિંગનું સ્તર છે. ક્રમ સંખ્યા m ધરાવતા સમૂહને (m) સૂચવવામાં આવે છે અને સમૂહ અને સમૂહ વચ્ચેની નિકટતા સૂચવવામાં આવે છે. સિંગલ લિન્કેજ અલ્ગોરિધમ નીચેના પગલાઓથી બનેલું છેઃ સ્તર અને ક્રમ નંબર ધરાવતા ડિસજોઈન્ટ ક્લસ્ટરિંગથી પ્રારંભ કરો. વર્તમાન ક્લસ્ટરિંગમાં ક્લસ્ટરોની સૌથી સમાન જોડી શોધો, જેમ કે જોડી, વર્તમાન ક્લસ્ટરિંગમાં ક્લસ્ટરોની તમામ જોડી પર લઘુત્તમ ક્યાં છે તે મુજબ. ક્રમ સંખ્યા વધારોઃ આગામી ક્લસ્ટરિંગ બનાવવા માટે ક્લસ્ટરોને એક જ ક્લસ્ટરમાં ભેળવી દો. ક્લસ્ટરોને અનુરૂપ પંક્તિઓ અને સ્તંભોને કાઢીને અને નવા રચાયેલા સમૂહને અનુરૂપ પંક્તિ અને સ્તંભ ઉમેરીને, નિકટતા મેટ્રિક્સને અપડેટ કરવા માટે આ ક્લસ્ટરીંગનું સ્તર સેટ કરો. સૂચવેલા નવા સમૂહ અને જૂના સમૂહ વચ્ચેની નિકટતાને આ રીતે વ્યાખ્યાયિત કરવામાં આવે છે. જો બધી વસ્તુઓ એક સમૂહમાં હોય, તો બંધ કરો. નહિંતર, પગલું 2 પર જાઓ. કાર્યશીલ ઉદાહરણ આ કાર્યશીલ ઉદાહરણ પાંચ બેક્ટેરિયાના 5S રિબોસોમલ RNA અનુક્રમ સંરેખણમાંથી ગણતરી કરાયેલ JC69 આનુવંશિક અંતર મેટ્રિક્સ પર આધારિત છેઃ બેસિલસ સબટિલિસ (β), બેસિલસ સ્ટીયરોથર્મોફિલસ (β), લેક્ટોબેસિલસ વિરિડેસેન્સ (β), એકોલેપ્લાસ્મા મોડિકમ (β), અને માઇક્રોકોકસ લ્યુટિયસ (β). પ્રથમ પગલું પ્રથમ ક્લસ્ટરિંગ ચાલો ધારીએ કે આપણી પાસે પાંચ તત્વો છે અને તેમની વચ્ચે જોડી મુજબ અંતરનો નીચેનો મેટ્રિક્સ છેઃ આ ઉદાહરણમાં, તેનું સૌથી ઓછું મૂલ્ય છે, તેથી આપણે ઘટકોને ક્લસ્ટર કરીએ છીએ અને. પ્રથમ શાખાની લંબાઈનો અંદાજ ચાલો નોડને સૂચવીએ જેની સાથે અને હવે જોડાયેલા છે. સેટિંગ એ સુનિશ્ચિત કરે છે કે તત્વો અને તેનાથી સમાન અંતરે છે. આ અલ્ટ્રામેટ્રિસિટી પૂર્વધારણાની અપેક્ષા સાથે સુસંગત છે. શાખાઓ જોડાય છે અને પછી તેની લંબાઈ હોય છે (અંતિમ ડેંડ્રોગ્રામ જુઓ) પ્રથમ અંતર મેટ્રિક્સ અપડેટ આપણે પછી પ્રારંભિક નિકટતા મેટ્રિક્સને નવા નિકટતા મેટ્રિક્સમાં અપડેટ કરવા માટે આગળ વધીએ છીએ (નીચે જુઓ), જે કદમાં એક પંક્તિ અને એક સ્તંભ દ્વારા ઘટાડવામાં આવે છે. બોલ્ડ મૂલ્યો નવા અંતરને અનુરૂપ હોય છે, જેની ગણતરી પ્રથમ સમૂહના દરેક તત્વ અને બાકીના દરેક તત્વ વચ્ચેના લઘુતમ અંતરને જાળવી રાખીને કરવામાં આવે છેઃ તેમાંના ઇટાલિક મૂલ્યો મેટ્રિક્સ અપડેટથી પ્રભાવિત થતા નથી કારણ કે તેઓ પ્રથમ સમૂહમાં સામેલ ન હોય તેવા ઘટકો વચ્ચેના અંતરને અનુરૂપ હોય છે. બીજું પગલું બીજું ક્લસ્ટરિંગ હવે આપણે નવી અંતર મેટ્રિક્સથી શરૂ કરીને અગાઉની ત્રણ ક્રિયાઓનું પુનરાવર્તન કરીએ છીએઃ અહીં, અને તેના સૌથી નીચા મૂલ્યો છે, તેથી આપણે તત્વ સાથે અને તત્વ સાથે ક્લસ્ટરને જોડીએ છીએ. બીજી શાખાની લંબાઈનો અંદાજ ચાલો નોડને સૂચવીએ જેની સાથે, અને હવે જોડાયેલા છે. અલ્ટ્રામેટ્રિસિટી અવરોધને કારણે, શાખાઓ જોડાય છે અથવા જોડાય છે, અને જોડાય છે, અને તે પણ સમાન હોય છે અને નીચેની કુલ લંબાઈ ધરાવે છેઃ આપણે ગુમ થયેલી શાખાની લંબાઈને શોધી કાઢીએ છીએઃ (અંતિમ ડેન્ડ્રોગ્રામ જુઓ) બીજું અંતર મેટ્રિક્સ અપડેટ આપણે પછી મેટ્રિક્સને નવા અંતર મેટ્રિક્સમાં અપડેટ કરવા માટે આગળ વધીએ છીએ (નીચે જુઓ), કદમાં બે પંક્તિઓ અને બે સ્તંભો દ્વારા ઘટાડવામાં આવે છે કારણ કે તેની સાથે અને સાથે ક્લસ્ટરિંગઃ અંતિમ પગલું અંતિમ મેટ્રિક્સ છેઃ તેથી આપણે ક્લસ્ટર્સમાં જોડાઈએ છીએ અને. ચાલો (રુટ) નોડને દર્શાવીએ જેની સાથે અને હવે જોડાયેલા છે. શાખાઓ જોડાય છે અને પછી તેની લંબાઈ હોય છેઃ આપણે બાકીની શાખાની લંબાઈ શોધી કાઢીએ છીએઃ એક-જોડાણ ડેંડ્રોગ્રામ ડેંડ્રોગ્રામ હવે પૂર્ણ થઈ ગયો છે. તે અલ્ટ્રામેટ્રિક છે કારણ કે તમામ ટીપ્સ (,,,, અને) તેનાથી સમાન અંતરે છેઃ તેથી ડેંડ્રોગ્રામ તેના સૌથી ઊંડા નોડ દ્વારા મૂળ ધરાવે છે. અન્ય જોડાણો સિંગલ લિન્કેજ ક્લસ્ટરિંગ માટેનું નિષ્કપટ અલ્ગોરિધમ આવશ્યકપણે ઓછામાં ઓછા ફેલાયેલા વૃક્ષો માટે ક્રુસ્કલના અલ્ગોરિધમ જેવું જ છે. જો કે, સિંગલ લિન્કેજ ક્લસ્ટરિંગમાં, જે ક્રમમાં ક્લસ્ટરોની રચના થાય છે તે મહત્વપૂર્ણ છે, જ્યારે ઓછામાં ઓછા ફેલાયેલા વૃક્ષો માટે જે મહત્વનું છે તે બિંદુઓની જોડીનો સમૂહ છે જે અલ્ગોરિધમ દ્વારા પસંદ કરેલા અંતર બનાવે છે. વૈકલ્પિક જોડાણ યોજનાઓમાં સંપૂર્ણ જોડાણ ક્લસ્ટરિંગ, સરેરાશ જોડાણ ક્લસ્ટરિંગ (યુપીજીએમએ અને ડબલ્યુપીજીએમએ) અને વોર્ડની પદ્ધતિનો સમાવેશ થાય છે. એગ્લોમેરેટિવ ક્લસ્ટરિંગ માટેના નિષ્કપટ અલ્ગોરિધમમાં, અલ્ગોરિધમમાં આંતર-ક્લસ્ટર અંતરની ગણતરી કરવા માટે એક અલગ સૂત્રનો ઉપયોગ કરીને અલગ જોડાણ યોજનાનો અમલ કરી શકાય છે. જે સૂત્રને સમાયોજિત કરવું જોઈએ તે ઉપરોક્ત અલ્ગોરિધમ વર્ણનમાં બોલ્ડ ટેક્સ્ટનો ઉપયોગ કરીને પ્રકાશિત કરવામાં આવ્યું છે. જો કે, નીચે વર્ણવેલ એલ્ગોરિધમ્સ જેવા વધુ કાર્યક્ષમ એલ્ગોરિધમ્સ તમામ જોડાણ યોજનાઓને સમાન રીતે સામાન્ય બનાવતા નથી. ઝડપી અલ્ગોરિધમ્સ સિંગલ-લિન્કેજ ક્લસ્ટરિંગ માટેનું નિષ્કપટ અલ્ગોરિધમ સમજવું સરળ છે પરંતુ સમયની જટિલતા સાથે ધીમું છે. 1973માં, આર. સિબ્સને સમયની જટિલતા અને અવકાશની જટિલતા (બંને શ્રેષ્ઠ) સાથે એક અલ્ગોરિધમનો પ્રસ્તાવ મૂક્યો હતો, જેને સ્લિંક તરીકે ઓળખવામાં આવે છે. સ્લિંક અલ્ગોરિધમ બે કાર્યો દ્વારા ક્રમાંકિત વસ્તુઓના સમૂહ પર ક્લસ્ટરિંગનું પ્રતિનિધિત્વ કરે છે. આ બંને કાર્યો સૌથી નાના સમૂહને શોધીને નક્કી કરવામાં આવે છે જેમાં વસ્તુ અને ઓછામાં ઓછી એક મોટી સંખ્યાવાળી વસ્તુ બંને હોય છે. પ્રથમ કાર્ય, વસ્તુને સમૂહમાં સૌથી મોટી સંખ્યાવાળી વસ્તુ સાથે મેપ કરે છે. બીજું કાર્ય, વસ્તુને ક્લસ્ટરની રચના સાથે સંકળાયેલ અંતર સુધી મેપ કરે છે. આ વિધેયોને બે એરેમાં સંગ્રહિત કરવા કે જે દરેક આઇટમ નંબરને તેના કાર્ય મૂલ્ય સાથે મેપ કરે છે તે જગ્યા લે છે, અને આ માહિતી ક્લસ્ટરિંગને નક્કી કરવા માટે પૂરતી છે. સિબ્સન બતાવે છે તેમ, જ્યારે વસ્તુઓના સમૂહમાં નવી વસ્તુ ઉમેરવામાં આવે છે, ત્યારે સંવર્ધિત સમૂહ માટે નવા સિંગલ-લિંકેજ ક્લસ્ટરિંગનું પ્રતિનિધિત્વ કરતા અપડેટેડ કાર્યો, જે તે જ રીતે રજૂ થાય છે, તે જૂના ક્લસ્ટરિંગથી સમયસર બનાવી શકાય છે. સ્લિંક અલ્ગોરિધમ પછી વસ્તુઓ પર લૂપ કરે છે, એક પછી એક, તેમને ક્લસ્ટરિંગની રજૂઆતમાં ઉમેરે છે. એક વૈકલ્પિક અલ્ગોરિધમ, જે સમાન શ્રેષ્ઠ સમય અને અવકાશ મર્યાદામાં ચાલે છે, તે ન્યૂનતમ ફેલાયેલા વૃક્ષો માટે નિષ્કપટ અલ્ગોરિધમ અને ક્રુસ્કલના અલ્ગોરિધમ વચ્ચેની સમાનતા પર આધારિત છે. ક્રુસ્કલના અલ્ગોરિધમનો ઉપયોગ કરવાને બદલે, કોઈ વ્યક્તિ પ્રાઈમના અલ્ગોરિધમનો ઉપયોગ કરી શકે છે, જેમાં દ્વિસંગી ઢગલાઓ વગરની વિવિધતા હોય છે જે આપેલ વસ્તુઓ અને અંતરના લઘુતમ સ્પૅનિંગ ટ્રી (પરંતુ ક્લસ્ટરિંગ નહીં) નું નિર્માણ કરવા માટે સમય અને જગ્યા લે છે. પછી, ઓછામાં ઓછા ફેલાયેલા વૃક્ષની ધાર દ્વારા રચાયેલા વિરલ આલેખમાં ક્રુસ્કલના અલ્ગોરિધમનો ઉપયોગ કરવાથી વધારાના સમય અને જગ્યામાં ક્લસ્ટરિંગ ઉત્પન્ન થાય છે. ક્લસ્ટર વિશ્લેષણ પણ જુઓ સંપૂર્ણ-જોડાણ ક્લસ્ટરિંગ શ્રેણીબદ્ધ ક્લસ્ટરિંગ મોલેક્યુલર ઘડિયાળ પડોશી-જોડાયેલા યુપીજીએમએ ડબલ્યુ. પી. જી. એમ. એ. સંદર્ભો બાહ્ય કડીઓ મેટલેબ ક્લસ્ટર વિશ્લેષણ અલ્ગોરિધમ્સમાં ઉપયોગમાં લેવાતી કડીઓ