सामान्यीकृत संपीड़न दूरी: Difference between revisions

From Vigyanwiki
(Created page with "सामान्यीकृत संपीड़न दूरी (NCD) दो वस्तुओं के बीच समानता (गणित) को माप...")
 
(सामान्यीकृत संपीड़न दूरी)
Line 1: Line 1:
सामान्यीकृत संपीड़न दूरी (NCD) दो वस्तुओं के बीच [[समानता (गणित)]] को मापने का एक तरीका है, चाहे वह दो दस्तावेज़ हों, दो अक्षर हों, दो ईमेल हों, दो संगीत स्कोर हों, दो भाषाएँ हों, दो कार्यक्रम हों, दो चित्र हों, दो सिस्टम हों, दो जीनोम हों, कुछ नाम है। ऐसा माप अनुप्रयोग पर निर्भर या मनमाना नहीं होना चाहिए। दो वस्तुओं के बीच समानता की एक उचित परिभाषा यह है कि उन्हें एक दूसरे में बदलना कितना कठिन है।
सामान्य संपीड़न दूरी ((NCD) दो वस्तुओं के बीच [[समानता (गणित)]] को मापने का एक तरीका है, चाहे वह दो दस्तावेज हों, दो अक्षर हों, दो ईमेल हों, दो संगीत स्कोर हों, दो भाषाएं हों, दो कार्यक्रम हों, दो तस्वीरें हों, दो सिस्टम हों, दो जीनोम हों। इस तरह का मापन अनुप्रयोग पर निर्भर या मनमाना नहीं होना चाहिए। दो वस्तुओं के बीच समानता के लिए एक उचित परिभाषा यह है कि उन्हें एक दूसरे में बदलना कितना मुश्किल है।


इसका उपयोग [[क्लस्टर विश्लेषण]] के लिए सूचना पुनर्प्राप्ति और [[डेटा खनन]] में किया जा सकता है।
इसका उपयोग [[क्लस्टर विश्लेषण]] के लिए सूचना पुनर्प्राप्ति और [[डेटा खनन]] में किया जा सकता है।      


== [[सूचना दूरी]] ==
== [[सूचना दूरी]] ==
हम मानते हैं कि जिन वस्तुओं के बारे में बात की जाती है वे सीमित बाइनरी अनुक्रम हैं। इस प्रकार हमारा मतलब [[स्ट्रिंग समानता]] है। हर कंप्यूटर फाइल इसी फॉर्म की होती है, यानी अगर कंप्यूटर में कोई ऑब्जेक्ट फाइल है तो वह इस फॉर्म की होती है। कोई तार के बीच सूचना दूरी को परिभाषित कर सकता है <math>x</math> और <math>y</math> सबसे छोटे कार्यक्रम की लंबाई के रूप में <math>p</math> जो गणना करता है <math>x</math> से <math>y</math> और इसके विपरीत। यह सबसे छोटा प्रोग्राम एक निश्चित प्रोग्रामिंग भाषा में है। तकनीकी कारणों से [[ट्यूरिंग मशीनें]] की सैद्धांतिक धारणा का उपयोग किया जाता है। इसके अलावा, की लंबाई व्यक्त करने के लिए <math>p</math> [[कोलमोगोरोव जटिलता]] की धारणा का उपयोग करता है। फिर दिखाया गया है <ref name="BGLVZ98">
हम मान लेते हैं कि जिन वस्तुओं के बारे में एक-एक बातें होती हैं वे 0s और1s के परिमित स्ट्रिंग्स हैं. इस प्रकार हमारा अर्थ है [[स्ट्रिंग समानता]] है। प्रत्येक कंप्यूटर फ़ाइल इस प्रपत्र की है, अर्थात यदि कोई ऑब्जेक्ट किसी कंप्यूटर में फ़ाइल है तो यह इस प्रपत्र का है. कोई भी स्ट्रिंग के बीच जानकारी की दूरी निर्धारित कर सकता है <math>x</math> और <math>y</math> सबसे छोटे कार्यक्रम की लंबाई के रूप में <math>p</math> जो गणना करता है <math>x</math> से <math>y</math> और इसके विपरीत। यह सबसे छोटा प्रोग्राम एक निश्चित प्रोग्रामिंग भाषा में है। तकनीकी कारणों से [[ट्यूरिंग मशीनें]] की सैद्धांतिक धारणा का उपयोग किया जाता है। इसके अलावा, की लंबाई व्यक्त करने के लिए <math>p</math> [[कोलमोगोरोव जटिलता]] की धारणा का उपयोग करता है। फिर दिखाया गया है <ref name="BGLVZ98">
[http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=681318&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D681318 C.H. Bennett, P. Gacs, M. Li, P.M.B. Vitányi, and W. Zurek, Information Distance, IEEE Trans. Inform. Theory, IT-44:4(1998) 1407–1423]</ref>
[http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=681318&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D681318 C.H. Bennett, P. Gacs, M. Li, P.M.B. Vitányi, and W. Zurek, Information Distance, IEEE Trans. Inform. Theory, IT-44:4(1998) 1407–1423]</ref>                              
:<math>|p| = \max \{K(x\mid y),K(y\mid x)\}</math>
:<math>|p| = \max \{K(x\mid y),K(y\mid x)\}</math>
लघुगणक योगात्मक पदों तक जिन्हें अनदेखा किया जा सकता है। यह सूचना दूरी एक [[मीट्रिक (गणित)]] के रूप में दिखाई गई है
लघुगणक योजक शर्तों तक जिसे अनदेखा किया जा सकता है. इस सूचना दूरी को [[मीट्रिक (गणित)]] दिखाया गया है (यह लघुगणक योगात्मक शब्द तक मीट्रिक असमानताओं को संतुष्ट करता है)
(यह एक लघुगणक योगात्मक शब्द तक मीट्रिक असमानताओं को संतुष्ट करता है), सार्वभौमिक है (यह छोटा करता है)
( सार्वभौमिक है (यह एक निरंतर ऐडिटिव शब्द तक सुविधाओं से उदाहरण के लिए गणना के रूप में प्रत्येक संकलित दूरी को कम करता है)।<ref name="BGLVZ98"/>                
प्रत्येक गणना योग्य दूरी, उदाहरण के लिए गणना की गई सुविधाओं से लेकर एक निरंतर योजक अवधि तक)।<ref name="BGLVZ98"/>
 
 
 
=== सामान्यीकृत सूचना दूरी (समानता मीट्रिक) ===
=== सामान्यीकृत सूचना दूरी (समानता मीट्रिक) ===
सूचना दूरी निरपेक्ष है, लेकिन अगर हम समानता व्यक्त करना चाहते हैं, तो हम रिश्तेदार में अधिक रुचि रखते हैं। उदाहरण के लिए, यदि 1,000,000 लंबाई के दो तार 1000 बिट्स से भिन्न होते हैं, तो हम मानते हैं कि वे तार 1000 बिट्स के दो स्ट्रिंग्स की तुलना में अपेक्षाकृत अधिक समान हैं जो 1000 बिट्स से भिन्न हैं। इसलिए हमें समानता मीट्रिक प्राप्त करने के लिए सामान्यीकृत करने की आवश्यकता है। इस तरह से सामान्यीकृत सूचना दूरी (एनआईडी) प्राप्त होती है,
सूचना दूरी निरपेक्ष है, लेकिन अगर हम समानता व्यक्त करना चाहते हैं, तो हम रिश्तेदार में अधिक रुचि रखते हैं। उदाहरण के लिए, यदि 1,000,000 लंबाई के दो तार 1000 बिट्स से भिन्न होते हैं, तो हम मानते हैं कि वे तार 1000 बिट्स के दो स्ट्रिंग्स की तुलना में अपेक्षाकृत अधिक समान हैं जो 1000 बिट्स से भिन्न हैं। इसलिए हमें समानता मीट्रिक प्राप्त करने के लिए सामान्यीकृत करने की आवश्यकता है। इस तरह से सामान्यीकृत सूचना दूरी (एनआईडी) प्राप्त होती है,
:<math> NID(x,y) = \frac{ \max\{K{(x\mid y)},K{(y\mid x)}\} }{ \max \{K(x),K(y)\}}, </math>
:<math> NID(x,y) = \frac{ \max\{K{(x\mid y)},K{(y\mid x)}\} }{ \max \{K(x),K(y)\}}, </math>
कहाँ <math>K(x\mid y)</math> की [[एल्गोरिथम जानकारी]] है <math>x</math> दिया गया <math>y</math> इनपुट के रूप में। एनआईडी को 'समानता मीट्रिक' कहा जाता है। समारोह के बाद से <math>NID(x,y)</math> मीट्रिक दूरी माप के लिए बुनियादी आवश्यकताओं को पूरा करने के लिए दिखाया गया है।<ref name="Li04">{{cite journal|title=M. Li, X. Chen, X. Li, B. Ma, P.M.B. Vitanyi, The similarity metric, IEEE Trans. Inform. Th., 50:12(2004), 3250–3264 |journal=IEEE Transactions on Information Theory |volume=50 |issue=12 |pages=3250–3264 |doi=10.1109/TIT.2004.838101 |date=2011-09-27 |last1=Li |first1=Ming |last2=Chen |first2=Xin |last3=Li |first3=Xin |last4=Ma |first4=Bin |last5=Vitanyi |first5=P. M. B. |s2cid=221927 }}</ref><ref name="CV05">{{cite journal|title=आर. सिलिब्रासी, पी.एम.बी. कॉल, संपीड़न द्वारा क्लस्टरिंग|journal=IEEE Transactions on Information Theory |volume=51 |issue=4 |pages=1523–1545 |doi=10.1109/TIT.2005.844059 |date=2011-09-27 |last1=Cilibrasi |first1=R. |last2=Vitanyi |first2=P. M. B. |arxiv=cs/0312044 |s2cid=911 }}</ref> हालाँकि, यह गणना योग्य या अर्ध-गणना योग्य भी नहीं है।<ref>{{cite journal| doi=10.1016/j.jcss.2010.06.018 | volume=77 | issue=4 | title=सामान्यीकृत सूचना दूरी की अनुपयुक्तता| year=2011 | journal=Journal of Computer and System Sciences | pages=738–742 | last1 = Terwijn | first1 = Sebastiaan A. | last2 = Torenvliet | first2 = Leen | last3 = Vitányi | first3 = Paul M.B.| s2cid=10831035 | url=https://ir.cwi.nl/pub/19043 | doi-access=free }}</ref>
कहाँ <math>K(x\mid y)</math> की [[एल्गोरिथम जानकारी]] है <math>x</math> दिया गया <math>y</math> इनपुट के रूप में। एनआईडी को 'समानता मीट्रिक' कहा जाता है। समारोह के बाद से <math>NID(x,y)</math> मीट्रिक दूरी माप के लिए बुनियादी आवश्यकताओं को पूरा करने के लिए दिखाया गया है।<ref name="Li04">{{cite journal|title=M. Li, X. Chen, X. Li, B. Ma, P.M.B. Vitanyi, The similarity metric, IEEE Trans. Inform. Th., 50:12(2004), 3250–3264 |journal=IEEE Transactions on Information Theory |volume=50 |issue=12 |pages=3250–3264 |doi=10.1109/TIT.2004.838101 |date=2011-09-27 |last1=Li |first1=Ming |last2=Chen |first2=Xin |last3=Li |first3=Xin |last4=Ma |first4=Bin |last5=Vitanyi |first5=P. M. B. |s2cid=221927 }}</ref><ref name="CV05">{{cite journal|title=आर. सिलिब्रासी, पी.एम.बी. कॉल, संपीड़न द्वारा क्लस्टरिंग|journal=IEEE Transactions on Information Theory |volume=51 |issue=4 |pages=1523–1545 |doi=10.1109/TIT.2005.844059 |date=2011-09-27 |last1=Cilibrasi |first1=R. |last2=Vitanyi |first2=P. M. B. |arxiv=cs/0312044 |s2cid=911 }}</ref> हालाँकि, यह गणना योग्य या अर्ध-गणना योग्य भी नहीं है।<ref>{{cite journal| doi=10.1016/j.jcss.2010.06.018 | volume=77 | issue=4 | title=सामान्यीकृत सूचना दूरी की अनुपयुक्तता| year=2011 | journal=Journal of Computer and System Sciences | pages=738–742 | last1 = Terwijn | first1 = Sebastiaan A. | last2 = Torenvliet | first2 = Leen | last3 = Vitányi | first3 = Paul M.B.| s2cid=10831035 | url=https://ir.cwi.nl/pub/19043 | doi-access=free }}</ref>
== सामान्यीकृत संपीड़न दूरी ==
== सामान्यीकृत संपीड़न दूरी ==
जबकि एनआईडी मीट्रिक की गणना नहीं की जा सकती है, इसमें अनुप्रयोगों की बहुतायत है। बस अनुमान लगाया जा रहा है <math>K</math> वास्तविक दुनिया कंप्रेशर्स द्वारा, के साथ <math>Z(x)</math> फ़ाइल की बाइनरी लंबाई है <math>x</math> एनआईडी को लागू करना आसान बनाने के लिए कंप्रेसर जेड (उदाहरण के लिए [[gzip]], [[bzip2]], [[आंशिक मिलान द्वारा भविष्यवाणी]]) के साथ संपीड़ित।<ref name="Li04" />सामान्यीकृत संपीड़न दूरी (एनसीडी) प्राप्त करने के लिए [[पॉल विटानी]] और [[रूडी सिलिब्रासी]] ने एनआईडी को फिर से लिखा
जबकि एनआईडी मीट्रिक की गणना नहीं की जा सकती है, इसमें अनुप्रयोगों की बहुतायत है। बस अनुमान लगाया जा रहा है <math>K</math> वास्तविक दुनिया कंप्रेशर्स द्वारा, के साथ <math>Z(x)</math> फ़ाइल की बाइनरी लंबाई है <math>x</math> एनआईडी को लागू करना आसान बनाने के लिए कंप्रेसर जेड (उदाहरण के लिए [[gzip]], [[bzip2]], [[आंशिक मिलान द्वारा भविष्यवाणी]]) के साथ संपीड़ित।<ref name="Li04" />सामान्यीकृत संपीड़न दूरी (एनसीडी) प्राप्त करने के लिए [[पॉल विटानी]] और [[रूडी सिलिब्रासी]] ने एनआईडी को फिर से लिखा
: : : : : : : : : : : : : : : : : : : : : : : : :<math> NCD_Z(x,y) = \frac{Z(xy) - \min \{Z(x),Z(y)\}}{\max \{Z(x),Z(y)\}}. </math><ref name="CV05"/>एनसीडी वास्तव में कंप्रेसर जेड के साथ पैरामीट्रिज्ड दूरी का एक परिवार है। बेहतर जेड है, एनसीडी एनआईडी के जितना करीब है, और बेहतर परिणाम हैं।<ref name="CV05"/>
: : : : : : : : : : : : : : : : : : : : : : : : :<math> NCD_Z(x,y) = \frac{Z(xy) - \min \{Z(x),Z(y)\}}{\max \{Z(x),Z(y)\}}. </math><ref name="CV05"/>एनसीडी वास्तव में कंप्रेसर जेड के साथ पैरामीट्रिज्ड दूरी का एक परिवार है। बेहतर जेड है, एनसीडी एनआईडी के जितना करीब है, और बेहतर परिणाम हैं।<ref name="CV05"/>
=== अनुप्रयोग ===
=== अनुप्रयोग ===
भाषा और फाइलोजेनेटिक पेड़ों को पूरी तरह से स्वचालित रूप से पुनर्निर्माण करने के लिए सामान्यीकृत संपीड़न दूरी का उपयोग किया गया है।<ref name="Li04"/><ref name="CV05"/>इसका उपयोग सामान्य क्लस्टर विश्लेषण के नए अनुप्रयोगों और स्वैच्छिक डोमेन में प्राकृतिक डेटा के [[सांख्यिकीय वर्गीकरण]] के लिए भी किया जा सकता है,<ref name="CV05"/>विषम डेटा के क्लस्टरिंग के लिए,<ref name="CV05"/>और डोमेन में विसंगति का पता लगाने के लिए।<ref name="Ke04">{{cite book|title=E. Keogh, S. Lonardi, and C.A. Ratanamahatana. "Towards parameter-free data mining." In Conference on Knowledge Discovery in Data: Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, vol. 22, no. 25, pp. 206–215. 2004 |pages=206 |doi=10.1145/1014052.1014077 |publisher=Dl.acm.org |date=2004-08-22 |chapter=Towards parameter-free data mining |last1=Keogh |first1=Eamonn |last2=Lonardi |first2=Stefano |last3=Ratanamahatana |first3=Chotirat Ann |isbn=978-1581138887 |s2cid=1616057 }}</ref> एनआईडी और एनसीडी संगीत वर्गीकरण सहित कई विषयों पर लागू किए गए हैं,<ref name="CV05"/>नेटवर्क ट्रैफ़िक और क्लस्टर कंप्यूटर वर्म्स और वायरस का विश्लेषण करने के लिए,<ref>{{cite journal|url=http://iospress.metapress.com/content/y3q582341n5l8ux2/ |title=S. Wehner,Analyzing worms and network traffic using compression, Journal of Computer Security, 15:3(2007), 303–320 |publisher=Iospress.metapress.com |access-date=2012-11-03}}</ref> लेखकत्व एट्रिब्यूशन,<ref>{{cite journal|title=आधुनिक लेखकत्व एट्रिब्यूशन विधियों का एक सर्वेक्षण|doi=10.1002/asi.21001|volume=60 |issue = 3|journal=Journal of the American Society for Information Science and Technology |pages=538–556 |year=2009 | last1 = Stamatatos | first1 = Efstathios|citeseerx=10.1.1.207.3310}}</ref> जीन अभिव्यक्ति की गतिशीलता,<ref>{{cite journal|title= मैक्रोफेज में जीन एक्सप्रेशन डायनेमिक्स क्रिटिकलिटी प्रदर्शित करता है|doi=10.1073/pnas.0711525105 |pmid= 18250330|volume=105 |issue= 6|journal=Proceedings of the National Academy of Sciences |pages=1897–1900 |year=2008 | last1 = Nykter | first1 = M.|pmc=2538855 |bibcode=2008PNAS..105.1897N |doi-access=free }}</ref> उपयोगी बनाम बेकार स्टेम सेल की भविष्यवाणी करना,<ref>{{cite journal|title= तंत्रिका पूर्वज कोशिका भाग्य की कम्प्यूटेशनल भविष्यवाणी|volume=7 |issue= 3|doi=10.1038/nmeth.1424 |pmid= 20139969|journal=Nature Methods |pages=213–218 |year=2010 | last1 = Cohen | first1 = Andrew R|hdl= 1866/4484|s2cid=18652440 |hdl-access= free }}</ref> महत्वपूर्ण नेटवर्क,<ref>{{cite journal|title=M. Nykter, N.D. Price, A. Larjo, T. Aho, S.A. Kauffman, O. Yli-Harja1, and I. Shmulevich, Critical networks exhibit maximal information diversity in structure-dynamics relationships, Phys. Rev. Lett. 100, 058702 (2008) |journal=Physical Review Letters |volume=100 |issue=5 |pages=058702 |doi=10.1103/PhysRevLett.100.058702 |pmid=18352443 |year=2008 |last1=Nykter |first1=Matti |last2=Price |first2=Nathan D. |last3=Larjo |first3=Antti |last4=Aho |first4=Tommi |last5=Kauffman |first5=Stuart A. |last6=Yli-Harja |first6=Olli |last7=Shmulevich |first7=Ilya |arxiv=0801.3699 |s2cid=5760862 }}</ref> छवि पंजीकरण,<ref>{{cite book|title=M. Feixas, I. Boada, M. Sbert, Compression-based Image Registration. Proc. IEEE International Symposium on Information Theory, 2006. 436–440 |pages=436–440 |doi=10.1109/ISIT.2006.261706 |publisher=Ieeexplore.ieee.org |date= July 2006|chapter=Compression-based Image Registration |last1=Bardera |first1=Anton |last2=Feixas |first2=Miquel |last3=Boada |first3=Imma |last4=Sbert |first4=Mateu |isbn=978-1-4244-0505-3 |hdl=10256/3052 |s2cid=12549455 }}</ref> प्रश्न-उत्तर प्रणाली।<ref>{{cite book|title=X Zhang, Y Hao, X Zhu, M Li, Information distance from a question to an answer, Proc. 13th ACM SIGKDD international conference on Knowledge discovery and data mining, 2007, 874–883 |pages=874 |doi=10.1145/1281192.1281285 |publisher=Dl.acm.org |isbn=9781595936097 |chapter=Information distance from a question to an answer |year=2007 |last1=Zhang |first1=Xian |last2=Hao |first2=Yu |last3=Zhu |first3=Xiaoyan |last4=Li |first4=Ming |last5=Cheriton |first5=David R. |s2cid=3040254 }}</ref>
भाषा और फाइलोजेनेटिक पेड़ों को पूरी तरह से स्वचालित रूप से पुनर्निर्माण करने के लिए सामान्यीकृत संपीड़न दूरी का उपयोग किया गया है।<ref name="Li04"/><ref name="CV05"/>इसका उपयोग सामान्य क्लस्टर विश्लेषण के नए अनुप्रयोगों और स्वैच्छिक डोमेन में प्राकृतिक डेटा के [[सांख्यिकीय वर्गीकरण]] के लिए भी किया जा सकता है,<ref name="CV05"/>विषम डेटा के क्लस्टरिंग के लिए,<ref name="CV05"/>और डोमेन में विसंगति का पता लगाने के लिए।<ref name="Ke04">{{cite book|title=E. Keogh, S. Lonardi, and C.A. Ratanamahatana. "Towards parameter-free data mining." In Conference on Knowledge Discovery in Data: Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, vol. 22, no. 25, pp. 206–215. 2004 |pages=206 |doi=10.1145/1014052.1014077 |publisher=Dl.acm.org |date=2004-08-22 |chapter=Towards parameter-free data mining |last1=Keogh |first1=Eamonn |last2=Lonardi |first2=Stefano |last3=Ratanamahatana |first3=Chotirat Ann |isbn=978-1581138887 |s2cid=1616057 }}</ref> एनआईडी और एनसीडी संगीत वर्गीकरण सहित कई विषयों पर लागू किए गए हैं,<ref name="CV05"/>नेटवर्क ट्रैफ़िक और क्लस्टर कंप्यूटर वर्म्स और वायरस का विश्लेषण करने के लिए,<ref>{{cite journal|url=http://iospress.metapress.com/content/y3q582341n5l8ux2/ |title=S. Wehner,Analyzing worms and network traffic using compression, Journal of Computer Security, 15:3(2007), 303–320 |publisher=Iospress.metapress.com |access-date=2012-11-03}}</ref> लेखकत्व एट्रिब्यूशन,<ref>{{cite journal|title=आधुनिक लेखकत्व एट्रिब्यूशन विधियों का एक सर्वेक्षण|doi=10.1002/asi.21001|volume=60 |issue = 3|journal=Journal of the American Society for Information Science and Technology |pages=538–556 |year=2009 | last1 = Stamatatos | first1 = Efstathios|citeseerx=10.1.1.207.3310}}</ref> जीन अभिव्यक्ति की गतिशीलता,<ref>{{cite journal|title= मैक्रोफेज में जीन एक्सप्रेशन डायनेमिक्स क्रिटिकलिटी प्रदर्शित करता है|doi=10.1073/pnas.0711525105 |pmid= 18250330|volume=105 |issue= 6|journal=Proceedings of the National Academy of Sciences |pages=1897–1900 |year=2008 | last1 = Nykter | first1 = M.|pmc=2538855 |bibcode=2008PNAS..105.1897N |doi-access=free }}</ref> उपयोगी बनाम बेकार स्टेम सेल की भविष्यवाणी करना,<ref>{{cite journal|title= तंत्रिका पूर्वज कोशिका भाग्य की कम्प्यूटेशनल भविष्यवाणी|volume=7 |issue= 3|doi=10.1038/nmeth.1424 |pmid= 20139969|journal=Nature Methods |pages=213–218 |year=2010 | last1 = Cohen | first1 = Andrew R|hdl= 1866/4484|s2cid=18652440 |hdl-access= free }}</ref> महत्वपूर्ण नेटवर्क,<ref>{{cite journal|title=M. Nykter, N.D. Price, A. Larjo, T. Aho, S.A. Kauffman, O. Yli-Harja1, and I. Shmulevich, Critical networks exhibit maximal information diversity in structure-dynamics relationships, Phys. Rev. Lett. 100, 058702 (2008) |journal=Physical Review Letters |volume=100 |issue=5 |pages=058702 |doi=10.1103/PhysRevLett.100.058702 |pmid=18352443 |year=2008 |last1=Nykter |first1=Matti |last2=Price |first2=Nathan D. |last3=Larjo |first3=Antti |last4=Aho |first4=Tommi |last5=Kauffman |first5=Stuart A. |last6=Yli-Harja |first6=Olli |last7=Shmulevich |first7=Ilya |arxiv=0801.3699 |s2cid=5760862 }}</ref> छवि पंजीकरण,<ref>{{cite book|title=M. Feixas, I. Boada, M. Sbert, Compression-based Image Registration. Proc. IEEE International Symposium on Information Theory, 2006. 436–440 |pages=436–440 |doi=10.1109/ISIT.2006.261706 |publisher=Ieeexplore.ieee.org |date= July 2006|chapter=Compression-based Image Registration |last1=Bardera |first1=Anton |last2=Feixas |first2=Miquel |last3=Boada |first3=Imma |last4=Sbert |first4=Mateu |isbn=978-1-4244-0505-3 |hdl=10256/3052 |s2cid=12549455 }}</ref> प्रश्न-उत्तर प्रणाली।<ref>{{cite book|title=X Zhang, Y Hao, X Zhu, M Li, Information distance from a question to an answer, Proc. 13th ACM SIGKDD international conference on Knowledge discovery and data mining, 2007, 874–883 |pages=874 |doi=10.1145/1281192.1281285 |publisher=Dl.acm.org |isbn=9781595936097 |chapter=Information distance from a question to an answer |year=2007 |last1=Zhang |first1=Xian |last2=Hao |first2=Yu |last3=Zhu |first3=Xiaoyan |last4=Li |first4=Ming |last5=Cheriton |first5=David R. |s2cid=3040254 }}</ref>
=== प्रदर्शन ===
=== प्रदर्शन ===
डाटामाइनिंग समुदाय के शोधकर्ता एनसीडी और वैरिएंट को पैरामीटर-फ्री, फीचर-फ्री [[डेटा खनन]] टूल के रूप में उपयोग करते हैं।<ref name="Ke04"/>एक समूह ने प्रयोगात्मक रूप से अनुक्रम बेंचमार्क की एक विशाल विविधता पर बारीकी से संबंधित मीट्रिक का परीक्षण किया है। पिछले एक दशक में 7 प्रमुख डेटा-खनन सम्मेलनों में पाई गई 51 प्रमुख विधियों के साथ उनकी संपीड़न विधि की तुलना करते हुए, उन्होंने विषम डेटा को क्लस्टर करने और विसंगति का पता लगाने और क्लस्टरिंग डोमेन डेटा में प्रतिस्पर्धात्मकता के लिए संपीड़न विधि की श्रेष्ठता स्थापित की।
डाटामाइनिंग समुदाय के शोधकर्ता एनसीडी और वैरिएंट को पैरामीटर-फ्री, फीचर-फ्री [[डेटा खनन]] टूल के रूप में उपयोग करते हैं।<ref name="Ke04"/>एक समूह ने प्रयोगात्मक रूप से अनुक्रम बेंचमार्क की एक विशाल विविधता पर बारीकी से संबंधित मीट्रिक का परीक्षण किया है। पिछले एक दशक में 7 प्रमुख डेटा-खनन सम्मेलनों में पाई गई 51 प्रमुख विधियों के साथ उनकी संपीड़न विधि की तुलना करते हुए, उन्होंने विषम डेटा को क्लस्टर करने और विसंगति का पता लगाने और क्लस्टरिंग डोमेन डेटा में प्रतिस्पर्धात्मकता के लिए संपीड़न विधि की श्रेष्ठता स्थापित की।

Revision as of 23:30, 29 April 2023

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

इसका उपयोग क्लस्टर विश्लेषण के लिए सूचना पुनर्प्राप्ति और डेटा खनन में किया जा सकता है।

सूचना दूरी

हम मान लेते हैं कि जिन वस्तुओं के बारे में एक-एक बातें होती हैं वे 0s और1s के परिमित स्ट्रिंग्स हैं. इस प्रकार हमारा अर्थ है स्ट्रिंग समानता है। प्रत्येक कंप्यूटर फ़ाइल इस प्रपत्र की है, अर्थात यदि कोई ऑब्जेक्ट किसी कंप्यूटर में फ़ाइल है तो यह इस प्रपत्र का है. कोई भी स्ट्रिंग के बीच जानकारी की दूरी निर्धारित कर सकता है और सबसे छोटे कार्यक्रम की लंबाई के रूप में जो गणना करता है से और इसके विपरीत। यह सबसे छोटा प्रोग्राम एक निश्चित प्रोग्रामिंग भाषा में है। तकनीकी कारणों से ट्यूरिंग मशीनें की सैद्धांतिक धारणा का उपयोग किया जाता है। इसके अलावा, की लंबाई व्यक्त करने के लिए कोलमोगोरोव जटिलता की धारणा का उपयोग करता है। फिर दिखाया गया है [1]

लघुगणक योजक शर्तों तक जिसे अनदेखा किया जा सकता है. इस सूचना दूरी को मीट्रिक (गणित) दिखाया गया है (यह लघुगणक योगात्मक शब्द तक मीट्रिक असमानताओं को संतुष्ट करता है) ( सार्वभौमिक है (यह एक निरंतर ऐडिटिव शब्द तक सुविधाओं से उदाहरण के लिए गणना के रूप में प्रत्येक संकलित दूरी को कम करता है)।[1]

सामान्यीकृत सूचना दूरी (समानता मीट्रिक)

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

कहाँ की एल्गोरिथम जानकारी है दिया गया इनपुट के रूप में। एनआईडी को 'समानता मीट्रिक' कहा जाता है। समारोह के बाद से मीट्रिक दूरी माप के लिए बुनियादी आवश्यकताओं को पूरा करने के लिए दिखाया गया है।[2][3] हालाँकि, यह गणना योग्य या अर्ध-गणना योग्य भी नहीं है।[4]

सामान्यीकृत संपीड़न दूरी

जबकि एनआईडी मीट्रिक की गणना नहीं की जा सकती है, इसमें अनुप्रयोगों की बहुतायत है। बस अनुमान लगाया जा रहा है वास्तविक दुनिया कंप्रेशर्स द्वारा, के साथ फ़ाइल की बाइनरी लंबाई है एनआईडी को लागू करना आसान बनाने के लिए कंप्रेसर जेड (उदाहरण के लिए gzip, bzip2, आंशिक मिलान द्वारा भविष्यवाणी) के साथ संपीड़ित।[2]सामान्यीकृत संपीड़न दूरी (एनसीडी) प्राप्त करने के लिए पॉल विटानी और रूडी सिलिब्रासी ने एनआईडी को फिर से लिखा

: : : : : : : : : : : : : : : : : : : : : : : :[3]एनसीडी वास्तव में कंप्रेसर जेड के साथ पैरामीट्रिज्ड दूरी का एक परिवार है। बेहतर जेड है, एनसीडी एनआईडी के जितना करीब है, और बेहतर परिणाम हैं।[3]

अनुप्रयोग

भाषा और फाइलोजेनेटिक पेड़ों को पूरी तरह से स्वचालित रूप से पुनर्निर्माण करने के लिए सामान्यीकृत संपीड़न दूरी का उपयोग किया गया है।[2][3]इसका उपयोग सामान्य क्लस्टर विश्लेषण के नए अनुप्रयोगों और स्वैच्छिक डोमेन में प्राकृतिक डेटा के सांख्यिकीय वर्गीकरण के लिए भी किया जा सकता है,[3]विषम डेटा के क्लस्टरिंग के लिए,[3]और डोमेन में विसंगति का पता लगाने के लिए।[5] एनआईडी और एनसीडी संगीत वर्गीकरण सहित कई विषयों पर लागू किए गए हैं,[3]नेटवर्क ट्रैफ़िक और क्लस्टर कंप्यूटर वर्म्स और वायरस का विश्लेषण करने के लिए,[6] लेखकत्व एट्रिब्यूशन,[7] जीन अभिव्यक्ति की गतिशीलता,[8] उपयोगी बनाम बेकार स्टेम सेल की भविष्यवाणी करना,[9] महत्वपूर्ण नेटवर्क,[10] छवि पंजीकरण,[11] प्रश्न-उत्तर प्रणाली।[12]

प्रदर्शन

डाटामाइनिंग समुदाय के शोधकर्ता एनसीडी और वैरिएंट को पैरामीटर-फ्री, फीचर-फ्री डेटा खनन टूल के रूप में उपयोग करते हैं।[5]एक समूह ने प्रयोगात्मक रूप से अनुक्रम बेंचमार्क की एक विशाल विविधता पर बारीकी से संबंधित मीट्रिक का परीक्षण किया है। पिछले एक दशक में 7 प्रमुख डेटा-खनन सम्मेलनों में पाई गई 51 प्रमुख विधियों के साथ उनकी संपीड़न विधि की तुलना करते हुए, उन्होंने विषम डेटा को क्लस्टर करने और विसंगति का पता लगाने और क्लस्टरिंग डोमेन डेटा में प्रतिस्पर्धात्मकता के लिए संपीड़न विधि की श्रेष्ठता स्थापित की।

शोर के लिए मजबूत आंकड़े होने का एनसीडी का एक फायदा है।[13] हालाँकि, हालांकि एनसीडी पैरामीटर-मुक्त प्रतीत होता है, व्यावहारिक प्रश्नों में एनसीडी और अन्य संभावित समस्याओं की गणना में किस कंप्रेसर का उपयोग करना शामिल है।[14]


=== सामान्यीकृत सापेक्ष संपीड़न (NRC) === के साथ तुलना एक स्ट्रिंग की जानकारी को दूसरे के सापेक्ष मापने के लिए सापेक्ष अर्ध-दूरी (एनआरसी) पर भरोसा करने की आवश्यकता है।[15] ये ऐसे उपाय हैं जिन्हें समरूपता और त्रिभुज असमानता दूरी गुणों का सम्मान करने की आवश्यकता नहीं है। हालांकि एनसीडी और एनआरसी बहुत समान दिखते हैं, लेकिन वे अलग-अलग सवालों को संबोधित करते हैं। एनसीडी मापता है कि दोनों तार कितने समान हैं, ज्यादातर सूचना सामग्री का उपयोग करते हुए, जबकि एनआरसी एक लक्ष्य स्ट्रिंग के अंश को इंगित करता है जिसे किसी अन्य स्ट्रिंग से जानकारी का उपयोग करके नहीं बनाया जा सकता है। तुलना के लिए, प्राइमेट जीनोम के विकास के लिए आवेदन के साथ, देखें।[16]


सामान्यीकृत Google दूरी

Main article: Normalized Google distance

वस्तुओं को शाब्दिक रूप से दिया जा सकता है, जैसे शाब्दिक चार-अक्षर वाला माउस जीनोम डेटाबेस, या टॉल्स्टॉय द्वारा युद्ध और शांति का शाब्दिक पाठ। सरलता के लिए हम यह मान लेते हैं कि वस्तु के सभी अर्थ शाब्दिक वस्तु द्वारा ही दर्शाए जाते हैं। वस्तुओं को नाम से भी दिया जा सकता है, जैसे माउस के चार-अक्षर जीनोम, या टॉल्स्टॉय द्वारा 'युद्ध और शांति' का पाठ। ऐसी वस्तुएँ भी हैं जिन्हें शाब्दिक रूप से नहीं दिया जा सकता है, लेकिन केवल नाम से, और जो मानव जाति में सामान्य ज्ञान की पृष्ठभूमि में अपने संदर्भों से अपना अर्थ प्राप्त करती हैं, जैसे कि घर या लाल। हम शब्दार्थ समानता में रुचि रखते हैं। वेब से Google द्वारा लौटाए गए पेज-हिट काउंट्स से प्राप्त कोड-वर्ड की लंबाई का उपयोग करते हुए, हम एनसीडी फॉर्मूले का उपयोग करके सिमेंटिक दूरी प्राप्त करते हैं और Google को डेटा माइनिंग, टेक्स्ट कॉम्प्रिहेंशन, वर्गीकरण और अनुवाद के लिए उपयोगी कंप्रेसर के रूप में देखते हैं। संबद्ध NCD, जिसे सामान्यीकृत Google दूरी (NGD) कहा जाता है, को फिर से लिखा जा सकता है

कहाँ खोज शब्द वाले पृष्ठों की संख्या को दर्शाता है , और दोनों वाले पृष्ठों की संख्या को दर्शाता है और ,) जैसा कि Google या किसी भी खोज इंजन द्वारा लौटाया गया है जो समग्र पृष्ठ संख्या लौटाने में सक्षम है। जो नंबर अनुक्रमित पृष्ठों की संख्या पर सेट किया जा सकता है, हालांकि प्रत्येक पृष्ठ को उसमें शामिल खोज शब्दों या वाक्यांशों की संख्या के अनुसार गिनना अधिक उचित है। अंगूठे के नियम के अनुसार पृष्ठों की संख्या को एक हजार से गुणा किया जा सकता है...[17]


यह भी देखें

संदर्भ

  1. ↑ 1.0 1.1 C.H. Bennett, P. Gacs, M. Li, P.M.B. Vitányi, and W. Zurek, Information Distance, IEEE Trans. Inform. Theory, IT-44:4(1998) 1407–1423
  2. ↑ 2.0 2.1 2.2 Li, Ming; Chen, Xin; Li, Xin; Ma, Bin; Vitanyi, P. M. B. (2011-09-27). "M. Li, X. Chen, X. Li, B. Ma, P.M.B. Vitanyi, The similarity metric, IEEE Trans. Inform. Th., 50:12(2004), 3250–3264". IEEE Transactions on Information Theory. 50 (12): 3250–3264. doi:10.1109/TIT.2004.838101. S2CID 221927.
  3. ↑ 3.0 3.1 3.2 3.3 3.4 3.5 3.6 Cilibrasi, R.; Vitanyi, P. M. B. (2011-09-27). "आर. सिलिब्रासी, पी.एम.बी. कॉल, संपीड़न द्वारा क्लस्टरिंग". IEEE Transactions on Information Theory. 51 (4): 1523–1545. arXiv:cs/0312044. doi:10.1109/TIT.2005.844059. S2CID 911.
  4. ↑ Terwijn, Sebastiaan A.; Torenvliet, Leen; Vitányi, Paul M.B. (2011). "सामान्यीकृत सूचना दूरी की अनुपयुक्तता". Journal of Computer and System Sciences. 77 (4): 738–742. doi:10.1016/j.jcss.2010.06.018. S2CID 10831035.
  5. ↑ 5.0 5.1 Keogh, Eamonn; Lonardi, Stefano; Ratanamahatana, Chotirat Ann (2004-08-22). "Towards parameter-free data mining". E. Keogh, S. Lonardi, and C.A. Ratanamahatana. "Towards parameter-free data mining." In Conference on Knowledge Discovery in Data: Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, vol. 22, no. 25, pp. 206–215. 2004. Dl.acm.org. p. 206. doi:10.1145/1014052.1014077. ISBN 978-1581138887. S2CID 1616057.
  6. ↑ "S. Wehner,Analyzing worms and network traffic using compression, Journal of Computer Security, 15:3(2007), 303–320". Iospress.metapress.com. Retrieved 2012-11-03. {{cite journal}}: Cite journal requires |journal= (help)
  7. ↑ Stamatatos, Efstathios (2009). "आधुनिक लेखकत्व एट्रिब्यूशन विधियों का एक सर्वेक्षण". Journal of the American Society for Information Science and Technology. 60 (3): 538–556. CiteSeerX 10.1.1.207.3310. doi:10.1002/asi.21001.
  8. ↑ Nykter, M. (2008). "मैक्रोफेज में जीन एक्सप्रेशन डायनेमिक्स क्रिटिकलिटी प्रदर्शित करता है". Proceedings of the National Academy of Sciences. 105 (6): 1897–1900. Bibcode:2008PNAS..105.1897N. doi:10.1073/pnas.0711525105. PMC 2538855. PMID 18250330.
  9. ↑ Cohen, Andrew R (2010). "तंत्रिका पूर्वज कोशिका भाग्य की कम्प्यूटेशनल भविष्यवाणी". Nature Methods. 7 (3): 213–218. doi:10.1038/nmeth.1424. hdl:1866/4484. PMID 20139969. S2CID 18652440.
  10. ↑ Nykter, Matti; Price, Nathan D.; Larjo, Antti; Aho, Tommi; Kauffman, Stuart A.; Yli-Harja, Olli; Shmulevich, Ilya (2008). "M. Nykter, N.D. Price, A. Larjo, T. Aho, S.A. Kauffman, O. Yli-Harja1, and I. Shmulevich, Critical networks exhibit maximal information diversity in structure-dynamics relationships, Phys. Rev. Lett. 100, 058702 (2008)". Physical Review Letters. 100 (5): 058702. arXiv:0801.3699. doi:10.1103/PhysRevLett.100.058702. PMID 18352443. S2CID 5760862.
  11. ↑ Bardera, Anton; Feixas, Miquel; Boada, Imma; Sbert, Mateu (July 2006). "Compression-based Image Registration". M. Feixas, I. Boada, M. Sbert, Compression-based Image Registration. Proc. IEEE International Symposium on Information Theory, 2006. 436–440. Ieeexplore.ieee.org. pp. 436–440. doi:10.1109/ISIT.2006.261706. hdl:10256/3052. ISBN 978-1-4244-0505-3. S2CID 12549455.
  12. ↑ Zhang, Xian; Hao, Yu; Zhu, Xiaoyan; Li, Ming; Cheriton, David R. (2007). "Information distance from a question to an answer". X Zhang, Y Hao, X Zhu, M Li, Information distance from a question to an answer, Proc. 13th ACM SIGKDD international conference on Knowledge discovery and data mining, 2007, 874–883. Dl.acm.org. p. 874. doi:10.1145/1281192.1281285. ISBN 9781595936097. S2CID 3040254.
  13. ↑ Cebrian, M.; Alfonseca, M.; Ortega, A. (2011-09-27). "सामान्यीकृत संपीड़न दूरी शोर के लिए प्रतिरोधी है". IEEE Transactions on Information Theory. 53 (5): 1895–1900. CiteSeerX 10.1.1.158.2463. doi:10.1109/TIT.2007.894669. S2CID 15691266.
  14. ↑ "M. Cebrián, M. Alfonseca, and A. Ortega, Common pitfalls using the normalized compression distance: what to watch out for in a compressor, Commun. Inf. Syst. 5:4(2005), 367–384". Projecteuclid.org. Retrieved 2012-11-03.
  15. ↑ Ziv, J.; Merhav, N. (1993). "सार्वभौमिक वर्गीकरण के लिए आवेदन के साथ अलग-अलग अनुक्रमों के बीच सापेक्ष एंट्रॉपी का एक उपाय". IEEE Transactions on Information Theory. 39 (4): 1270–1279. doi:10.1109/18.243444.
  16. ↑ Pratas, Diogo; Silva, Raquel M.; Pinho, Armando J. (2018). "प्राइमेट जीनोम के विकास के लिए आवेदन के साथ संपीड़न-आधारित उपायों की तुलना". Entropy. 20 (6): 393. Bibcode:2018Entrp..20..393P. doi:10.3390/e20060393. PMC 7512912. PMID 33265483. CC-BY icon.svg Material was copied from this source, which is available under a Creative Commons Attribution 4.0 International License.
  17. ↑ Cilibrasi, R. L.; Vitanyi, P. M. B. (2011-09-27). "R.L. Cilibrasi, P.M.B. Vitanyi, The Google Similarity Distance, IEEE Trans. Knowledge and Data Engineering, 19:3(2007), 370-383". IEEE Transactions on Knowledge and Data Engineering. 19 (3): 370–383. arXiv:cs/0412098. doi:10.1109/TKDE.2007.48. S2CID 59777.


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=सामान्यीकृत_संपीड़न_दूरी&oldid=154076’