R में हाइरार्किकल क्लस्टरिंग

क्लस्टरिंग के लिए प्री-प्रोसेसिंग ऑपरेशंस

शुरू करने से पहले कुछ बातों का ध्यान रखना चाहिए।

• स्केलिंग

क्लस्टरिंग प्रक्रिया शुरू करने के लिए अपने फीचर मानों के स्केल को सामान्यीकृत करना आवश्यक है। ऐसा इसलिए क्योंकि प्रत्येक ऑब्ज़र्वेशन के फीचर मान n-आयामी स्पेस (जहाँ n फीचर्स की संख्या है) में निर्देशांकों के रूप में दर्शाए जाते हैं और फिर इन निर्देशांकों के बीच की दूरियाँ निकाली जाती हैं। यदि ये निर्देशांक सामान्यीकृत नहीं हैं, तो यह गलत परिणामों की ओर ले जा सकता है।

उदाहरण के लिए, मान लें आपके पास तीन लोगों की ऊँचाई और वजन का डेटा है: A (6ft, 75kg), B (6ft,77kg), C (8ft,75kg)। यदि आप इन फीचर्स को एक द्वि-आयामी निर्देशांक प्रणाली, ऊँचाई और वजन, में दर्शाएँ और इनके बीच यूक्लिडियन दूरी निकालें, तो निम्नलिखित युग्मों के बीच दूरी होगी:

A-B : 2 इकाइयाँ

A-C : 2 इकाइयाँ

दूरी मेट्रिक बताता है कि A-B और A-C दोनों युग्म समान हैं, जबकि वास्तविकता में वे स्पष्ट रूप से समान नहीं हैं! युग्म A-B, युग्म A-C से अधिक समान है। इसलिए पहले इन मानों को स्केल करना और फिर दूरी निकालना महत्वपूर्ण है।

फीचर मानों को सामान्यीकृत करने के कई तरीके हैं; आप सभी फीचर मानों (x(i)) के पूरे स्केल को [0,1] के बीच मानकीकृत करने पर विचार कर सकते हैं (जिसे मिन-मैक्स नॉर्मलाइज़ेशन कहते हैं) और इसके लिए निम्न रूपांतरण लागू करें:

$ x(s) = x(i) - min(x)/(max(x) - min (x)) $

इसके लिए आप R का normalize() फ़ंक्शन उपयोग कर सकते हैं या आप इस तरह अपना फ़ंक्शन लिख सकते हैं:

standardize <- function(x){(x-min(x))/(max(x)-min(x))}

स्केलिंग का अन्य प्रकार निम्न रूपांतरण से प्राप्त किया जा सकता है:

$ x(s) = x(i)-mean(x) / sd(x) $

जहाँ sd(x) फीचर मानों का मानक विचलन है। इससे आपके फीचर मानों का वितरण औसत 0 और मानक विचलन 1 वाला हो जाएगा। आप यह R के scale() फ़ंक्शन से कर सकते हैं।

• मिसिंग वैल्यू इम्प्यूटेशन

अपने डेटासेट में मौजूद missing/null/inf मानों से पहले ही निपटना भी महत्वपूर्ण है। ऐसे मानों से निपटने के कई तरीके हैं: उन्हें हटाना, या mean, median, mode से इम्प्यूट करना, या कुछ उन्नत रिग्रेशन तकनीकों का उपयोग करना। R में मिसिंग वैल्यू इम्प्यूटेशन के लिए कई पैकेज और फ़ंक्शंस हैं, जैसे impute(), Amelia, Mice, Hmisc आदि। आप इस ट्यूटोरियल में Amelia के बारे में पढ़ सकते हैं।

हाइरार्किकल क्लस्टरिंग एल्गोरिदम

हाइरार्किकल एग्लोमेरेटिव क्लस्टरिंग में मुख्य क्रिया बार-बार दो सबसे नज़दीकी क्लस्टर्स को मिलाकर बड़ा क्लस्टर बनाना है। पहले तीन मुख्य प्रश्नों के उत्तर ज़रूरी हैं:

• एक से अधिक बिंदुओं वाले क्लस्टर का प्रतिनिधित्व कैसे करें?
• क्लस्टर्स की "नज़दीकी" कैसे निर्धारित करें?
• क्लस्टर्स को मिलाना कब बंद करें?

आशा है कि इस ट्यूटोरियल के अंत तक आप इन सभी प्रश्नों के उत्तर दे पाएँगे। हाइरार्किकल क्लस्टरिंग लागू करने से पहले इसके काम करने के तरीके पर नज़र डालें:

1. यह हर दो ऑब्ज़र्वेशन पॉइंट के बीच की दूरी की गणना करके एक दूरी मैट्रिक्स में सहेजना शुरू करता है।
2. फिर यह हर पॉइंट को उसके अपने क्लस्टर में रखता है।
3. इसके बाद दूरी मैट्रिक्स से दूरी के आधार पर सबसे नज़दीकी बिंदुओं के युग्मों को मिलाना शुरू करता है और परिणामस्वरूप क्लस्टर्स की संख्या 1 से घट जाती है।
4. फिर नए क्लस्टर और पुराने क्लस्टर्स के बीच की दूरी पुनर्गणित करता है और उन्हें एक नए दूरी मैट्रिक्स में सहेजता है।
5. अंत में, चरण 2 और 3 को तब तक दोहराता है जब तक सभी क्लस्टर्स एक ही क्लस्टर में न मिल जाएँ।

क्लस्टर्स के बीच दूरी मापने के कई तरीके हैं ताकि क्लस्टरिंग के नियम तय किए जा सकें, और इन्हें प्रायः लिंकेंज मेथड्स कहा जाता है। कुछ सामान्य लिंकेंज मेथड्स हैं:

• Complete-linkage: मर्ज करने से पहले क्लस्टर्स के बीच अधिकतम दूरी की गणना करता है।

• Single-linkage: मर्ज करने से पहले क्लस्टर्स के बीच न्यूनतम दूरी की गणना करता है। यह लिंकेंज आपके डेटासेट में उच्च मूल्यों का पता लगाने में काम आ सकता है जो आउट्लायर हो सकते हैं, क्योंकि वे अंत में मर्ज होंगे।

• Average-linkage: मर्ज करने से पहले क्लस्टर्स के बीच औसत दूरी की गणना करता है।

• Centroid-linkage: क्लस्टर 1 और क्लस्टर 2 के सेन्ट्रॉइड ढूँढता है और मर्ज करने से पहले उनके बीच की दूरी की गणना करता है।

लिंकेंज मेथड का चयन पूरी तरह आप पर निर्भर करता है और कोई सख्त नियम नहीं है जो हमेशा अच्छे परिणाम देगा। अलग-अलग लिंकेंज मेथड्स अलग-अलग क्लस्टर्स की ओर ले जाते हैं।

डेंड्रोग्राम

हाइरार्किकल क्लस्टरिंग में, आप ऑब्जेक्ट्स को एक पदानुक्रम में वर्गीकृत करते हैं जो पेड़ जैसे आरेख के समान होता है जिसे डेंड्रोग्राम कहते हैं। विभाजन या मर्ज की दूरी (जिसे ऊँचाई कहा जाता है) नीचे दिए गए डेंड्रोग्राम के y-अक्ष पर दिखाई जाती है।

ऊपर के चित्र में, पहले 4 और 6 दूरी में सबसे नज़दीक होने के कारण एक क्लस्टर, मान लें क्लस्टर 1, में संयोजित होते हैं, इसके बाद बिंदु 1 और 2, मान लें क्लस्टर 2। उसके बाद 5 उसी क्लस्टर 1 में मर्ज होता है, फिर 3, जिससे दो क्लस्टर्स बनते हैं। अंत में दोनों क्लस्टर्स एक ही क्लस्टर में मर्ज होते हैं और यहीं क्लस्टरिंग प्रक्रिया रुकती है।

अब तक आपके मन में यह प्रश्न आया होगा कि क्लस्टर्स का मर्ज करना कब रोकना चाहिए? यह आपके पास उपलब्ध डोमेन ज्ञान पर निर्भर करता है। उदाहरण के लिए, यदि आप फुटबॉल खिलाड़ियों को मैदान पर उनकी पोज़िशन के आधार पर क्लस्टर कर रहे हैं, जो दूरी गणना के लिए उनके निर्देशांकों का प्रतिनिधित्व करेगा, तो आपको पहले से पता है कि अंत में केवल 2 क्लस्टर्स होने चाहिए क्योंकि एक फुटबॉल मैच में केवल दो टीमें खेलती हैं।

लेकिन कभी-कभी आपके पास वह जानकारी भी नहीं होती। ऐसे मामलों में, क्लस्टर्स की संख्या का अनुमान लगाने के लिए आप डेंड्रोग्राम के परिणामों का लाभ उठा सकते हैं। आप डेंड्रोग्राम को उस ऊँचाई पर एक क्षैतिज रेखा से काटते हैं जहाँ रेखा ऊपर-नीचे अधिकतम दूरी तय कर सकती है बिना किसी मर्जिंग पॉइंट को काटे। ऊपर के मामले में यह 1.5 और 2.5 की ऊँचाइयों के बीच होगा, जैसा दिखाया गया है:

यदि आप दिखाए अनुसार कट लगाते हैं, तो आपके पास केवल दो क्लस्टर्स रह जाएँगे।

ध्यान दें कि कट केवल ऐसे स्थानों पर लगाना आवश्यक नहीं है; आप अपनी मनचाही क्लस्टर्स की संख्या के अनुसार किसी भी बिंदु को कट पॉइंट चुन सकते हैं। उदाहरण के लिए, 1.5 से नीचे और 1 से ऊपर का कट आपको 3 क्लस्टर्स देगा।

ध्यान दें यह क्लस्टर्स की संख्या तय करने का कोई सख्त नियम नहीं है। आप Silhouette प्लॉट, एल्बो प्लॉट, या Dunn's इंडेक्स, Hubert's gamma आदि जैसे कुछ संख्यात्मक मापों पर भी विचार कर सकते हैं, जो क्लस्टर्स की संख्या (k) के साथ त्रुटि में भिन्नता दिखाते हैं, और आप वह k चुनते हैं जहाँ त्रुटि सबसे कम हो।

क्लस्टर्स की गुणवत्ता मापना

शायद किसी भी अनसुपर्वाइज्ड लर्निंग कार्य का सबसे महत्वपूर्ण भाग परिणामों का विश्लेषण है। किसी भी एल्गोरिदम और पैरामीटर सेट्स का उपयोग करके क्लस्टरिंग करने के बाद आपको सुनिश्चित करना होता है कि आपने इसे सही किया है। लेकिन यह कैसे निर्धारित करें?

इसे करने के कई उपाय हैं, शायद सबसे लोकप्रिय है Dunn's Index। Dunn's इंडेक्स, न्यूनतम इंटर-क्लस्टर दूरी और अधिकतम इंट्रा-क्लस्टर डायामीटर के अनुपात के बराबर होता है। किसी क्लस्टर का डायामीटर उसके दो सबसे दूरस्थ बिंदुओं के बीच की दूरी है। अच्छी तरह से अलग-अलग और सघन क्लस्टर्स पाने के लिए आपको उच्च Dunn's इंडेक्स का लक्ष्य रखना चाहिए।

हाइरार्किकल क्लस्टरिंग व्यवहार में

अब आप अपने अर्जित ज्ञान को वास्तविक दुनिया की समस्या हल करने में लागू करेंगे।

आप seeds डेटासेट पर हाइरार्किकल क्लस्टरिंग लागू करेंगे। यह डेटासेट गेहूँ की तीन विभिन्न किस्मों: Kama, Rosa और Canadian के कर्नेल्स के ज्यामितीय गुणों के मापों से बना है। इसमें बीजों के गुण जैसे क्षेत्रफल, परिमाप, असिमेट्री गुणांक आदि का वर्णन करने वाले वेरिएबल्स हैं। प्रत्येक गेहूँ की किस्म के लिए 70 ऑब्ज़र्वेशन हैं। आप डेटासेट के विवरण यहाँ पा सकते हैं।

read.csv() फ़ंक्शन के साथ डेटासेट को एक डेटा फ़्रेम में इम्पोर्ट करके शुरू करें।

ध्यान दें कि फ़ाइल में कोई हेडर नहीं है और यह टैब-सेपरेटेड है। परिणामों की पुनरुत्पादनशीलता बनाए रखने के लिए आपको set.seed() फ़ंक्शन का उपयोग करना होगा।

set.seed(786)
file_loc <- 'seeds.txt'
seeds_df <- read.csv(file_loc,sep = '\t',header = FALSE)संचालित द्वारा

चूँकि डेटासेट में कोई कॉलम नाम नहीं है, आप डेटा विवरण से स्वयं कॉलम नाम देंगे।

feature_name <- c('area','perimeter','compactness','length.of.kernel','width.of.kernal','asymmetry.coefficient','length.of.kernel.groove','type.of.seed')
colnames(seeds_df) <- feature_nameसंचालित द्वारा

डेटासेट के बारे में कुछ बुनियादी उपयोगी जानकारी जैसे इसके आयाम, डेटा प्रकार और वितरण, NAs की संख्या आदि इकट्ठा करना उचित है। आप R में str(), summary() और is.na() फ़ंक्शंस का उपयोग करके ऐसा करेंगे।

str(seeds_df)
summary(seeds_df)
any(is.na(seeds_df))संचालित द्वारा

ध्यान दें कि इस डेटासेट में सभी कॉलम संख्यात्मक मान हैं। इस डेटासेट में कोई मिसिंग वैल्यू नहीं है जिससे आपको क्लस्टरिंग से पहले निपटना पड़े। लेकिन फीचर्स के स्केल अलग-अलग हैं और आपको उन्हें सामान्यीकृत करना होगा। साथ ही, डेटा लेबल्ड है और आपके पास पहले से जानकारी है कि कौन-सा ऑब्ज़र्वेशन गेहूँ की किस किस्म से संबंधित है।

अब आप लेबल्स को एक अलग वेरिएबल में सहेजेंगे और क्लस्टरिंग करने के लिए अपने डेटासेट से type.of.seed कॉलम को निकाल देंगे। बाद में आप सच्चे लेबल्स का उपयोग करके देखेंगे कि आपकी क्लस्टरिंग कितनी अच्छी रही।

seeds_label <- seeds_df$type.of.seed
seeds_df$type.of.seed <- NULL
str(seeds_df)संचालित द्वारा

जैसा कि आप देखेंगे, आपने अपने डेटासेट से सच्चे लेबल वाला कॉलम हटा दिया है।

अब आप अपनी सभी कॉलम वैल्यूज़ को स्केल करने के लिए R के scale() फ़ंक्शन का उपयोग करेंगे।

seeds_df_sc <- as.data.frame(scale(seeds_df))
summary(seeds_df_sc)संचालित द्वारा

ध्यान दें कि सभी कॉलम का औसत 0 और मानक विचलन 1 है। अब जब आपने अपने डेटा का प्री-प्रोसेसिंग कर लिया है, तो दूरी मैट्रिक्स बनाने का समय है। चूँकि यहाँ सभी मान सतत संख्यात्मक हैं, आप euclidean दूरी विधि का उपयोग करेंगे।

dist_mat <- dist(seeds_df_sc, method = 'euclidean')संचालित द्वारा

इस बिंदु पर आपको तय करना चाहिए कि आप कौन-सी लिंकेंज विधि का उपयोग करना चाहते हैं और हाइरार्किकल क्लस्टरिंग करना जारी रखें। आप सभी प्रकार की लिंकेंज विधियाँ आज़मा सकते हैं और बाद में तय कर सकते हैं कि कौन-सी बेहतर रही। यहाँ आप average लिंकेंज विधि के साथ आगे बढ़ेंगे।

आप hclust() के साथ बनाए गए हाइरार्किकल क्लस्टर ऑब्जेक्ट को प्लॉट करके अपना डेंड्रोग्राम बनाएँगे। आप method आर्ग्युमेंट के माध्यम से लिंकेंज विधि निर्दिष्ट कर सकते हैं।

hclust_avg <- hclust(dist_mat, method = 'average')
plot(hclust_avg)संचालित द्वारा

ध्यान दें कि डेंड्रोग्राम कैसे बनता है और हर डेटा पॉइंट अंततः एक ही क्लस्टर में मिल जाता है, जिसकी ऊँचाई (दूरी) y-अक्ष पर दिखाई जाती है।

अगला, आप इच्छित क्लस्टर्स की संख्या बनाने के लिए डेंड्रोग्राम को काट सकते हैं। चूँकि इस मामले में आपको पहले से पता है कि गेहूँ के केवल तीन प्रकार हो सकते हैं, आप क्लस्टर्स की संख्या k = 3 चुनेंगे, या जैसा कि आप डेंड्रोग्राम में देख सकते हैं h = 3 पर आपको तीन क्लस्टर्स मिलते हैं। आप R के cutree() फ़ंक्शन का उपयोग करेंगे और hclust_avg को एक पैरामीटर तथा दूसरे पैरामीटर के रूप में h = 3 या k = 3 देंगे।

cut_avg <- cutree(hclust_avg, k = 3)संचालित द्वारा

यदि आप डेंड्रोग्राम पर क्लस्टर्स को दृश्य रूप में देखना चाहते हैं, तो आप R के abline() फ़ंक्शन से कट रेखा खींच सकते हैं और rect.hclust() फ़ंक्शन से प्रत्येक क्लस्टर के लिए वृक्ष पर आयताकार खंड सुपरइम्पोज़ कर सकते हैं, जैसा कि निम्न कोड में दिखाया गया है:

plot(hclust_avg)
rect.hclust(hclust_avg , k = 3, border = 2:6)
abline(h = 3, col = 'red')संचालित द्वारा

अब आप तीन अलग-अलग रंगों के बक्सों में घिरे तीन क्लस्टर्स देख सकते हैं। आप dendextend लाइब्रेरी के color_branches() फ़ंक्शन का उपयोग करके अलग-अलग रंगों की शाखाओं के साथ अपना वृक्ष भी विज़ुअलाइज़ कर सकते हैं।

याद रखें कि आप R में install.packages('package_name', dependencies = TRUE) कमांड का उपयोग करके कोई पैकेज इंस्टॉल कर सकते हैं।

suppressPackageStartupMessages(library(dendextend))
avg_dend_obj <- as.dendrogram(hclust_avg)
avg_col_dend <- color_branches(avg_dend_obj, h = 3)
plot(avg_col_dend)संचालित द्वारा

अब आप dplyr पैकेज के mutate() से मूल डेटा फ़्रेम में प्राप्त क्लस्टर परिणामों को cluster नाम के कॉलम के अंतर्गत जोड़ेंगे और count() फ़ंक्शन से देखेंगे कि प्रत्येक क्लस्टर में कितने ऑब्ज़र्वेशन असाइन हुए।

suppressPackageStartupMessages(library(dplyr))
seeds_df_cl <- mutate(seeds_df, cluster = cut_avg)
count(seeds_df_cl,cluster)संचालित द्वारा

आप देख पाएँगे कि प्रत्येक क्लस्टर में कितने ऑब्ज़र्वेशन असाइन हुए। ध्यान दें कि वास्तव में लेबल्ड डेटा में आपके पास गेहूँ की प्रत्येक किस्म के लिए 70 ऑब्ज़र्वेशन थे।

अक्सर क्लस्टरिंग के आधार पर दो फीचर्स के बीच के ट्रेंड का मूल्यांकन किया जाता है ताकि क्लस्टर-वार डेटा से अधिक उपयोगी इनसाइट्स निकाली जा सकें। एक अभ्यास के रूप में, आप ggplot2 पैकेज की मदद से गेहूँ के perimeter और area के बीच क्लस्टर-वार ट्रेंड का विश्लेषण कर सकते हैं।

suppressPackageStartupMessages(library(ggplot2))
ggplot(seeds_df_cl, aes(x=area, y = perimeter, color = factor(cluster))) + geom_point()संचालित द्वारा

ध्यान दें कि गेहूँ की सभी किस्मों के लिए उनके परिमाप और क्षेत्रफल के बीच एक रैखिक संबंध प्रतीत होता है।

चूँकि इस डेटासेट के लिए आपके पास सच्चे लेबल पहले से हैं, आप table() फ़ंक्शन का उपयोग करके अपनी क्लस्टरिंग के परिणामों का क्रॉस-चेक भी कर सकते हैं।

table(seeds_df_cl$cluster,seeds_label)संचालित द्वारा

यदि आप बने हुए टेबल पर नज़र डालें, तो आपको स्पष्ट रूप से 55 या उससे अधिक तत्वों वाले तीन समूह दिखेंगे। समग्र रूप से, आप कह सकते हैं कि आपके क्लस्टर्स बीजों के विभिन्न प्रकारों का पर्याप्त प्रतिनिधित्व करते हैं क्योंकि मूल रूप से प्रत्येक गेहूँ की किस्म के लिए 70 ऑब्ज़र्वेशन थे। बड़े समूह क्लस्टर्स और वास्तविक प्रकारों के बीच अनुरूपता दर्शाते हैं।

ध्यान दें कि कई मामलों में आपके पास सच्चे लेबल वास्तव में नहीं होते। ऐसे मामलों में, जैसा कि पहले चर्चा की गई, आप Dunn's इंडेक्स को अधिकतम करने जैसे अन्य उपाय अपना सकते हैं। आप clValid लाइब्रेरी के dunn() फ़ंक्शन से dunn's इंडेक्स की गणना कर सकते हैं। साथ ही, आप अन्य किसी मशीन लर्निंग एल्गोरिदम की तरह ट्रेन और टेस्ट सेट बनाकर और जहाँ सच्चे लेबल हों वहाँ क्लस्टरिंग करके परिणामों का क्रॉस-वैलिडेशन भी कर सकते हैं।

K-Means क्लस्टरिंग एल्गोरिदम से तुलना

आपने शायद k-means क्लस्टरिंग एल्गोरिदम के बारे में सुना होगा; यदि नहीं, तो यह ट्यूटोरियल देखें। दोनों एल्गोरिदम के बीच कई बुनियादी अंतर हैं, यद्यपि अलग-अलग मामलों में कोई भी दूसरे से बेहतर प्रदर्शन कर सकता है। कुछ अंतर इस प्रकार हैं:

• उपयोग की गई दूरी: हाइरार्किकल क्लस्टरिंग वस्तुतः किसी भी दूरी मेट्रिक को संभाल सकती है, जबकि k-means यूक्लिडियन दूरी पर निर्भर करता है।
• परिणामों की स्थिरता: k-means अपने इनिशियलाइज़ेशन में एक रैंडम स्टेप लेता है, जिससे प्रक्रिया को पुनः चलाने पर अलग परिणाम मिल सकते हैं। हाइरार्किकल क्लस्टरिंग में ऐसा नहीं होता।
• क्लस्टर्स की संख्या: जहाँ k-means में सही क्लस्टर्स की संख्या निकालने के लिए आप एल्बो प्लॉट्स, Silhouette प्लॉट आदि का उपयोग कर सकते हैं, वहीं हाइरार्किकल में भी आप ये सभी उपयोग कर सकते हैं, साथ ही डेंड्रोग्राम का अतिरिक्त लाभ उठा सकते हैं।
• कम्प्यूटेशनल जटिलता: K-means, हाइरार्किकल क्लस्टरिंग की तुलना में कम कम्प्यूटेशनल महँगा है और बड़े डेटासेट्स पर भी उचित समय में चलाया जा सकता है, जो इसके अधिक लोकप्रिय होने का मुख्य कारण है।

निष्कर्ष

बधाई हो! आप इस ट्यूटोरियल के अंत तक आ चुके हैं। आपने सीखा कि अपने डेटा का प्री-प्रोसेसिंग कैसे करें, हाइरार्किकल क्लस्टरिंग की बुनियादें, इसके दूरी मैट्रिक्स और लिंकेंज मेथड्स, और R में इसका उपयोग कैसे करें। आपने यह भी जाना कि हाइरार्किकल क्लस्टरिंग k-means एल्गोरिदम से कैसे भिन्न है। बहुत बढ़िया! लेकिन सीखने के लिए हमेशा और भी बहुत कुछ है। मैं सुझाव दूँगा कि आप हमारा Unsupervised Learning in R कोर्स देखें।