r लेवेनशेटिन दूरी के साथ पाठ क्लस्टरिंग




matlab cluster-analysis (4)

मेरे पास एक सेट (2k - 4k) छोटे तारों (3-6 वर्ण) हैं और मैं उन्हें क्लस्टर करना चाहता हूं। चूंकि मैं तारों का उपयोग करता हूं, क्लस्टरिंग (विशेष रूप से स्ट्रिंग क्लस्टरिंग) कैसे काम करता है पर पिछले उत्तर ? , मुझे सूचित किया कि लेवेनशेटिन दूरी तारों के लिए दूरी समारोह के रूप में उपयोग करने के लिए अच्छा है। इसके अलावा, चूंकि मुझे पहले से पता नहीं है कि क्लस्टर की संख्या, पदानुक्रमित क्लस्टरिंग जाने का तरीका है और के-साधन नहीं है।

हालांकि मुझे इसके अमूर्त रूप में समस्या मिलती है, मुझे नहीं पता कि वास्तव में ऐसा करने का आसान तरीका क्या है। उदाहरण के लिए, MATLAB या R कस्टम फ़ंक्शन (लेवेनशेटिन दूरी) के साथ पदानुक्रमित क्लस्टरिंग के वास्तविक कार्यान्वयन के लिए बेहतर विकल्प है। दोनों सॉफ़्टवेयर के लिए, कोई आसानी से लेवेनशेटिन दूरी कार्यान्वयन पा सकता है। क्लस्टरिंग हिस्सा कठिन लगता है। उदाहरण के लिए MATLAB में क्लस्टरिंग टेक्स्ट सभी तारों के लिए दूरी सरणी की गणना करता है, लेकिन मुझे समझ में नहीं आता कि वास्तव में क्लस्टरिंग प्राप्त करने के लिए दूरी सरणी का उपयोग कैसे करें। क्या आप में से कोई भी गुरु मुझे कस्टम फ़ंक्शन के साथ MATLAB या R में पदानुक्रमित क्लस्टरिंग को कार्यान्वित करने का तरीका दिखा सकता है?


ELKI में ELKI दूरी शामिल है, और उन्नत क्लस्टरिंग एल्गोरिदम की विस्तृत पसंद प्रदान करती है, उदाहरण के लिए OPTICS क्लस्टरिंग।

फ़ेलिक्स स्टाहल्बर्ग द्वारा टेक्स्ट क्लस्टरिंग समर्थन का योगदान उनके काम के हिस्से के रूप में किया गया था:

स्टाहल्बर्ग, एफ।, श्लीपे, टी।, वोगल, एस, और शल्ट्ज, टी।
क्रॉस-भाषाई शब्द-से-फोनेम संरेखण के माध्यम से शब्द विभाजन।
स्पोकन लैंग्वेज टेक्नोलॉजी वर्कशॉप (एसएलटी), 2012 आईईईई। आईईईई, 2012।

हम निश्चित रूप से अतिरिक्त योगदान की सराहना करेंगे।


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

अक्सर ओएमए तीन चरणों में किया जाता है। सबसे पहले, आप अपने अनुक्रमों को परिभाषित करते हैं। आपके विवरण से मैं मान सकता हूं कि प्रत्येक पत्र एक अलग "राज्य" है, एक अनुक्रम में बिल्डिंग ब्लॉक। दूसरा, आप अपने डेटासेट में सभी अनुक्रमों के बीच की दूरी की गणना करने के लिए कई एल्गोरिदमों में से एक को नियोजित करेंगे, इस प्रकार दूरी मैट्रिक्स प्राप्त करेंगे। अंत में, आप उस दूरी मैट्रिक्स को क्लस्टरिंग एल्गोरिदम में खिलाएंगे, जैसे कि पदानुक्रमित क्लस्टरिंग या मेडोइड्स (पीएएम) के आसपास विभाजन, जो कि क्लस्टर की गुणवत्ता पर अतिरिक्त जानकारी के कारण लोकप्रियता प्राप्त करता है। उत्तरार्द्ध अनुक्रम विश्लेषण में कई व्यक्तिपरक चरणों में से एक क्लस्टर की संख्या की पसंद में आपको मार्गदर्शन करता है।

R में सबसे बड़ी पैकेज के साथ सबसे सुविधाजनक पैकेज TraMineR , वेबसाइट here पाई जा सकती here । इसकी उपयोगकर्ता मार्गदर्शिका बहुत ही सुलभ है, और डेवलपर्स एसओ पर भी कम या ज्यादा सक्रिय हैं।

आपको क्लस्टर की संख्या के फैसले को छोड़कर क्लस्टरिंग सबसे मुश्किल हिस्सा नहीं है। TraMineR लिए मार्गदर्शिका से पता चलता है कि वाक्यविन्यास बहुत कठोर है, और परिणाम दृश्य अनुक्रम ग्राफ के आधार पर व्याख्या करना आसान है। उपयोगकर्ता मार्गदर्शिका से यहां एक उदाहरण दिया गया है:

clusterward1 <- agnes(dist.om1, diss = TRUE, method = "ward")

dist.om1 ओएमए द्वारा प्राप्त दूरी मैट्रिक्स है, क्लस्टर सदस्यता clusterward1 ऑब्जेक्ट में निहित है, जो आप जो कुछ भी कर सकते हैं वह कर सकते हैं: साजिश, वैरिएबल के रूप में रिकोडिंग आदि। diss=TRUE विकल्प इंगित करता है कि डेटा ऑब्जेक्ट असमानता है ( या दूरी) मैट्रिक्स। आसान, आह? सबसे कठिन विकल्प (वाक्य रचनात्मक रूप से नहीं, बल्कि पद्धतिगत रूप से) आपके विशेष आवेदन के लिए उपयुक्त सही दूरी एल्गोरिदम चुनना है। एक बार आपके पास यह हो जाने के बाद, पसंद को औचित्य देने में सक्षम होने के बाद, बाकी काफी आसान है। सौभाग्य!


यदि आप अपनी समस्या को हल करने के लिए आंशिक क्लस्टरिंग (जो निश्चित रूप से तेज़ होगा) का उपयोग करने के बारे में स्पष्ट स्पष्टीकरण चाहते हैं, तो इस पेपर को जांचें: क्लस्टरिंग एल्गोरिदम का उपयोग कर प्रभावी वर्तनी जांच विधियां। https://www.researchgate.net/publication/255965260_Effective_Spell_Checking_Methods_Using_Clustering_Algorithms?ev=prf_pub

लेखकों ने आईके-मीन्स के संशोधित (पीएएम-जैसे) संस्करण का उपयोग करके एक शब्दकोश को क्लस्टर करने का तरीका बताया है।

शुभकामनाएँ!


यह थोड़ा सा सरल हो सकता है, लेकिन यहां एक कोड उदाहरण है जो आर में लेवेनशेटिन दूरी के आधार पर पदानुक्रमित क्लस्टरिंग का उपयोग करता है।

set.seed(1)
rstr <- function(n,k){   # vector of n random char(k) strings
  sapply(1:n,function(i){do.call(paste0,as.list(sample(letters,k,replace=T)))})
}

str<- c(paste0("aa",rstr(10,3)),paste0("bb",rstr(10,3)),paste0("cc",rstr(10,3)))
# Levenshtein Distance
d  <- adist(str)
rownames(d) <- str
hc <- hclust(as.dist(d))
plot(hc)
rect.hclust(hc,k=3)
df <- data.frame(str,cutree(hc,k=3))

इस उदाहरण में, हम 3 समूहों में कृत्रिम रूप से 30 यादृच्छिक चार (5) तारों का एक सेट बनाते हैं ("aa", "bb", और "cc" से शुरू होते हैं)। हम adist(...) का उपयोग कर Levenshtein दूरी मैट्रिक्स की गणना करते हैं, और हम hclust(...) का उपयोग कर hclust(...) क्लस्टरिंग चलाते हैं। फिर हमने cutree(...) को तीन समूहों में cutree(...) साथ काट दिया और क्लस्टर आईडी को मूल तारों में जोड़ दिया।





hierarchical-clustering