2011-12-28 16 views
9

समस्या आसन्न तार के बीच कम है:छंटाई तार इतना है कि आलोचनात्मक दूरी

मैं एन (~ 100k-1m) प्रत्येक डी तार (जैसे 2000) वर्ण लंबा और एक कम वर्णमाला के साथ (जैसे 3 संभव पात्रों)। मैं इन तारों को क्रमबद्ध करना चाहता हूं कि आसन्न तारों के बीच कुछ संभावित परिवर्तन हैं (उदाहरण के लिए हथौड़ा दूरी कम है)। समाधान सबसे अच्छा संभव नहीं है लेकिन बेहतर के करीब होना चाहिए।

उदाहरण

N=4 
D=5 
//initial strings 
1. aaacb 
2. bacba 
3. acacb 
4. cbcba 

//sorted so that hamming distance between adjacent strings is low 
1. aaacb 
3. acacb (Hamming distance 1->3 = 1) 
4. cbcba (Hamming distance 3->4 = 4) 
2. bacba (Hamming distance 4->2 = 2) 

समस्या

के बारे में विचार मैं यह एक गैर तुच्छ समस्या यह है बुरा विचार है। यदि हम प्रत्येक स्ट्रिंग को नोड के रूप में सोचते हैं और किनारों के रूप में अन्य तारों की दूरी के बारे में सोचते हैं, तो हम एक यात्रा विक्रेता की समस्या को देख रहे हैं। स्ट्रिंग्स की बड़ी संख्या का मतलब है कि पहले जोड़ी की दूरी की गणना पहले से ही संभावित रूप से अक्षम है, मुझे लगता है कि समस्या को Canadian Traveller Problem की तरह कुछ और बदलना है।

फिलहाल मेरी समाधान एक VP tree उपयोग करने के लिए समस्या

curr_string = a randomly chosen string from full set 
while(tree not empty) 
    found_string = find nearest string in tree 
    tree.remove(found_string) 
    sorted_list.add(curr_string) 
    curr_string = found_string 

लेकिन प्रारंभिक परिणाम गरीब होने के लिए प्रकट करने के लिए एक लालची निकटतम पड़ोसी प्रकार समाधान खोजने के लिए किया गया है। तारों को धक्का देना ताकि अधिक समान लोग निकट हो जाएं, लेकिन मुझे यह पता नहीं है कि यह कितना अच्छा समाधान प्रदान करेगा या यह इस आकार के डेटा को कितना अच्छा करेगा।

उत्तर

2

भले ही आप इस समस्या को यात्रा विक्रेता समस्या (टीएसपी) के समान मानते हैं, मुझे विश्वास है कि हैमिंग दूरी त्रिभुज असमानता (हैमिंग (ए, बी) + हैमिंग (बी, सी) ≤ हैमिंग (ए, सी)), तो आप केवल वास्तव में ΔTSP (मेट्रिक यात्रा विक्रेता समस्या) से निपट रहे हैं, जिसके लिए कई एल्गोरिदम हैं जो आदर्श परिणाम पर अच्छे अनुमान देते हैं। विशेष रूप से, Christofides algorithm आपको न्यूनतम 1.5x न्यूनतम संभव लंबाई का मार्ग प्रदान करेगा।

1

हाँ यह एक Traveling salesman problem है, लेकिन मैं TSP source code library के तहत दर्जन कार्यक्रमों में से किसी 1M अंक सीधे ऊपर कर सकते हैं, एक प्लग-इन मीट्रिक के साथ पता नहीं है।

एक संभव 2-चरण दृष्टिकोण:

1) 50 समूहों एक Nearest neighbor search साथ में 1M अंक अलग हो गए। 50 क्लस्टर केंद्रों पर टीएसपी करें।

2) 2 निकटतम केंद्रों के बीच सभी 1 एम - 50 अंक डालें; 1 एम/50 की प्रत्येक स्ट्रिंग पर टीएसपी करें। यहां "50" 100 या 1000 हो सकता है। यदि 1000 बहुत बड़ा है, तो रिकर्स करें: 1000 प्रत्येक 30 ~ 30 क्लस्टर में विभाजित करें।

के-साधन 1 एम अंक, क्लस्टर कर सकते हैं लेकिन फिर से मुझे प्लग-इन मीट्रिक के साथ तेज़ कार्यान्वयन की जानकारी नहीं है। तथापि scikit-learn clustering

एन अंक की एक केन्द्रक को खोजने के लिए एक जो कम से कम देखें, | सेंटर - सभी दूसरों |, आप afaik हे (एन^2) को हरा कर सकते हैं केवल द्वारा के बेतरतीब नमूने का सबसे अच्छा लेने कहें sqrt (एन) - पर्याप्त होना चाहिए। (या गूगल/तेजी से अनुमानित सेंट्रॉइड पर एक अलग सवाल पूछें)।

पहले पूरे प्रवाह में स्मृति पहुंच को बचाने के लिए डेटा को कसकर पैक करें। इस मामले में, 00 01 10 के रूप में एक बी सी को एन्कोड करें (प्रत्येक जोड़ी = 1 के बीच दूरी को हम्मिंग करना): 2000 x 2 बिट्स = 500 बाइट्स। Fwiw, न्यूनतम हैमिंगडिस्ट (4k बिट्स, 10k x 4k) ढूंढना मेरे मैक पीपीसी पर ~ 40 एमसीसी लेता है।