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

From Vigyanwiki
(सामान्यीकृत संपीड़न दूरी)
No edit summary
 
(9 intermediate revisions by 6 users not shown)
Line 1: Line 1:
सामान्य संपीड़न दूरी ((NCD) दो वस्तुओं के बीच [[समानता (गणित)]] को मापने का एक तरीका है, चाहे वह दो दस्तावेज हों, दो अक्षर हों, दो ईमेल हों, दो संगीत स्कोर हों, दो भाषाएं हों, दो कार्यक्रम हों, दो तस्वीरें हों, दो सिस्टम हों, दो जीनोम हों। इस तरह का मापन अनुप्रयोग पर निर्भर या मनमाना नहीं होना चाहिए। दो वस्तुओं के बीच समानता के लिए एक उचित परिभाषा यह है कि उन्हें एक दूसरे में बदलना कितना मुश्किल है।
'''सामान्यीकृत संपीड़न दूरी''' (NCD) दो वस्तुओं के बीच [[समानता (गणित)]] को मापने का एक तरीका है, चाहे वह दो दस्तावेज हों, दो अक्षर हों, दो ईमेल हों, दो संगीत स्कोर हों, दो भाषाएं हों, दो कार्यक्रम हों, दो तस्वीरें हों, दो प्रणाली हों, दो जीनोम हों। इस तरह का मापन अनुप्रयोग पर निर्भर या स्वेच्छित नहीं होना चाहिए। दो वस्तुओं के बीच समानता के लिए उचित परिभाषा यह है कि उन्हें एक दूसरे में बदलना कितना मुश्किल है।


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


== [[सूचना दूरी]] ==
== [[सूचना दूरी]] ==
हम मान लेते हैं कि जिन वस्तुओं के बारे में एक-एक बातें होती हैं वे 0s और1s के परिमित स्ट्रिंग्स हैं. इस प्रकार हमारा अर्थ है [[स्ट्रिंग समानता]] है। प्रत्येक कंप्यूटर फ़ाइल इस प्रपत्र की है, अर्थात यदि कोई ऑब्जेक्ट किसी कंप्यूटर में फ़ाइल है तो यह इस प्रपत्र का है. कोई भी स्ट्रिंग के बीच जानकारी की दूरी निर्धारित कर सकता है <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> संपीडक Z (उदाहरण के लिए [[gzip]], [[bzip2]], [["PPMZ"]]) साथ संपीड़ित किया गया ताकि एनआईडी को आसानी से लागू किया जा सके।<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"/>
:एनसीडी वास्तव में कंप्रेसर Z के साथ पैरामीट्रिज्ड दूरी की एक श्रेणी है और बेहतर Z है, एनसीडी एनआईडी के जितना करीब है, परिणाम और बेहतर हैं।<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="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 प्रमुख विधियों के साथ उनकी संपीड़न विधि की तुलना करते हुए, उन्होंने विषम आंकड़े को क्लस्टर करने और विसंगति का पता लगाने और क्लस्टरिंग डोमेन आंकड़े में प्रतिस्पर्धात्मकता के लिए संपीड़न विधि की श्रेष्ठता स्थापित की।


शोर के लिए मजबूत आंकड़े होने का एनसीडी का एक फायदा है।<ref>{{cite journal|title= सामान्यीकृत संपीड़न दूरी शोर के लिए प्रतिरोधी है|journal=IEEE Transactions on Information Theory |volume=53 |issue=5 |pages=1895–1900 |doi=10.1109/TIT.2007.894669 |date=2011-09-27 |last1=Cebrian |first1=M. |last2=Alfonseca |first2=M. |last3=Ortega |first3=A. |citeseerx=10.1.1.158.2463 |s2cid=15691266 }}</ref> हालाँकि, हालांकि एनसीडी पैरामीटर-मुक्त प्रतीत होता है, व्यावहारिक प्रश्नों में एनसीडी और अन्य संभावित समस्याओं की गणना में किस कंप्रेसर का उपयोग करना शामिल है।<ref>{{cite web|url=http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.cis/1175791028 |title=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 |publisher=Projecteuclid.org |access-date=2012-11-03}}</ref>
ध्वनि के लिए मजबूत आंकड़े होने का एनसीडी का एक लाभ है।<ref>{{cite journal|title= सामान्यीकृत संपीड़न दूरी शोर के लिए प्रतिरोधी है|journal=IEEE Transactions on Information Theory |volume=53 |issue=5 |pages=1895–1900 |doi=10.1109/TIT.2007.894669 |date=2011-09-27 |last1=Cebrian |first1=M. |last2=Alfonseca |first2=M. |last3=Ortega |first3=A. |citeseerx=10.1.1.158.2463 |s2cid=15691266 }}</ref> यद्यपि, एनसीडी पैरामीटर-मुक्त प्रतीत होता है, व्यावहारिक प्रश्नों में सम्मिलित हैं जो एनसीडी और अन्य संभावित समस्याओं की कंप्यूटिंग में उपयोग करने के लिए कंप्रेसर का उपयोग करते हैं।<ref>{{cite web|url=http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.cis/1175791028 |title=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 |publisher=Projecteuclid.org |access-date=2012-11-03}}</ref>                  


===  '''सामान्यीकृत सापेक्ष संपीड़न (एनआरसी) के साथ तुलना''' ===
स्ट्रिंग के दूसरे के सापेक्ष जानकारी को मापने के लिए सापेक्ष अर्द्ध-दूरी (एनआरसी) पर निर्भर रहने की आवश्यकता है।<ref>{{cite journal|title=सार्वभौमिक वर्गीकरण के लिए आवेदन के साथ अलग-अलग अनुक्रमों के बीच सापेक्ष एंट्रॉपी का एक उपाय|volume=39|number=4|doi=10.1109/18.243444 |journal=IEEE Transactions on Information Theory |pages=1270–1279 |year=1993 | last1 = Ziv | first1 = J. | last2 = Merhav | first2 = N.}}</ref> ये ऐसे उपाय हैं जिन्हें समरूपता और त्रिभुज असमानता दूरी गुणों का सम्मान करने की आवश्यकता नहीं है। यद्यपि एनसीडी और एनआरसी बहुत समान दिखते हैं, लेकिन वे अलग-अलग सवालों को संबोधित करते हैं। एनसीडी माप देती है कि दोनों स्ट्रिंग्स कितने समान हैं, ज्यादातर सूचना सामग्री का उपयोग करते हुए, जबकि एनआरसी किसी लक्ष्य स्ट्रिंग के उस अंश को इंगित करता है जिसे किसी अन्य स्ट्रिंग से जानकारी का उपयोग करके नहीं बनाया जा सकताl तुलना के लिए, प्राइमेट जीनोमों के विकास के लिए अनुप्रयोग के साथ, देखें।<ref>{{cite journal|title=प्राइमेट जीनोम के विकास के लिए आवेदन के साथ संपीड़न-आधारित उपायों की तुलना|volume=20|number=6|doi=10.3390/e20060393 |bibcode=2018Entrp..20..393P|journal=Entropy |pages=393 |year=2018 | last1 = Pratas | first1 = Diogo | last2 = Silva | first2 = Raquel M. | last3 = Pinho | first3 = Armando J.|pmid=33265483|pmc=7512912|doi-access=free }} [[File:CC-BY icon.svg|50px]] Material was copied from this source, which is available under a [https://creativecommons.org/licenses/by/4.0/ Creative Commons Attribution 4.0 International License].</ref>                         
== सामान्यीकृत गूगल दूरी ==


=== सामान्यीकृत सापेक्ष संपीड़न (NRC) === के साथ तुलना
{{main|सामान्यीकृत गूगल दूरी}}
एक स्ट्रिंग की जानकारी को दूसरे के सापेक्ष मापने के लिए सापेक्ष अर्ध-दूरी (एनआरसी) पर भरोसा करने की आवश्यकता है।<ref>{{cite journal|title=सार्वभौमिक वर्गीकरण के लिए आवेदन के साथ अलग-अलग अनुक्रमों के बीच सापेक्ष एंट्रॉपी का एक उपाय|volume=39|number=4|doi=10.1109/18.243444 |journal=IEEE Transactions on Information Theory |pages=1270–1279 |year=1993 | last1 = Ziv | first1 = J. | last2 = Merhav | first2 = N.}}</ref> ये ऐसे उपाय हैं जिन्हें समरूपता और त्रिभुज असमानता दूरी गुणों का सम्मान करने की आवश्यकता नहीं है। हालांकि एनसीडी और एनआरसी बहुत समान दिखते हैं, लेकिन वे अलग-अलग सवालों को संबोधित करते हैं। एनसीडी मापता है कि दोनों तार कितने समान हैं, ज्यादातर सूचना सामग्री का उपयोग करते हुए, जबकि एनआरसी एक लक्ष्य स्ट्रिंग के अंश को इंगित करता है जिसे किसी अन्य स्ट्रिंग से जानकारी का उपयोग करके नहीं बनाया जा सकता है। तुलना के लिए, प्राइमेट जीनोम के विकास के लिए आवेदन के साथ, देखें।<ref>{{cite journal|title=प्राइमेट जीनोम के विकास के लिए आवेदन के साथ संपीड़न-आधारित उपायों की तुलना|volume=20|number=6|doi=10.3390/e20060393 |bibcode=2018Entrp..20..393P|journal=Entropy |pages=393 |year=2018 | last1 = Pratas | first1 = Diogo | last2 = Silva | first2 = Raquel M. | last3 = Pinho | first3 = Armando J.|pmid=33265483|pmc=7512912|doi-access=free }} [[File:CC-BY icon.svg|50px]] Material was copied from this source, which is available under a [https://creativecommons.org/licenses/by/4.0/ Creative Commons Attribution 4.0 International License].</ref>


 
वस्तुओं को शाब्दिक रूप से दिया जा सकता है, जैसे शाब्दिक चार-अक्षर वाला [[माउस जीनोम डेटाबेस|माउस जीनोम आंकड़े बेस]], या टॉल्स्टॉय द्वारा [[युद्ध और शांति]] का शाब्दिक पाठ। सरलता के लिए हम यह मान लेते हैं कि वस्तु के सभी अर्थ शाब्दिक वस्तु द्वारा ही निरुपित होता है। वस्तुओं को नाम से भी दिया जा सकता है, जैसे माउस के चार-अक्षर जीनोम, या टॉल्स्टॉय द्वारा 'युद्ध और शांति' का पाठ। ऐसी वस्तुएँ भी हैं जिन्हें शाब्दिक रूप से नहीं दिया जा सकता है, बल्कि केवल नाम से, और जो मानव जाति में सामान्य ज्ञान की पृष्ठभूमि में अपने संदर्भों से अपना अर्थ प्राप्त करती हैं, जैसे "घर" या "लाल."।
== सामान्यीकृत Google दूरी ==
हम [[शब्दार्थ समानता]] में रुचि रखते हैं। वेब से गूगल द्वारा लौटाए गए पृष्ठ-हिट गिनती से प्राप्त कोड-वर्ड की लंबाई का उपयोग करते हुए, हम एनसीडी सूत्र का उपयोग करते हुए और डेटा खनन, पाठ समझ, वर्गीकरण, और अनुवाद के लिए गूगल को एक कम्प्रेसर के रूप में उपयोगी देखते हुए एक शब्दार्थ दूरी प्राप्त करते हैं। जिसे [[सामान्यीकृत Google दूरी|सामान्यीकृत गूगल  दूरी]] (एनजीडी) कहा जाने वाला एसोसिएटेड एनसीडी को पुनः के रूप में लिखा जा सकता हैl
 
{{main|Normalized Google distance}}
 
वस्तुओं को शाब्दिक रूप से दिया जा सकता है, जैसे शाब्दिक चार-अक्षर वाला [[माउस जीनोम डेटाबेस]], या टॉल्स्टॉय द्वारा [[युद्ध और शांति]] का शाब्दिक पाठ। सरलता के लिए हम यह मान लेते हैं कि वस्तु के सभी अर्थ शाब्दिक वस्तु द्वारा ही दर्शाए जाते हैं। वस्तुओं को नाम से भी दिया जा सकता है, जैसे माउस के चार-अक्षर जीनोम, या टॉल्स्टॉय द्वारा 'युद्ध और शांति' का पाठ। ऐसी वस्तुएँ भी हैं जिन्हें शाब्दिक रूप से नहीं दिया जा सकता है, लेकिन केवल नाम से, और जो मानव जाति में सामान्य ज्ञान की पृष्ठभूमि में अपने संदर्भों से अपना अर्थ प्राप्त करती हैं, जैसे कि घर या लाल।
हम [[शब्दार्थ समानता]] में रुचि रखते हैं। वेब से Google द्वारा लौटाए गए पेज-हिट काउंट्स से प्राप्त कोड-वर्ड की लंबाई का उपयोग करते हुए, हम एनसीडी फॉर्मूले का उपयोग करके सिमेंटिक दूरी प्राप्त करते हैं और Google को डेटा माइनिंग, टेक्स्ट कॉम्प्रिहेंशन, वर्गीकरण और अनुवाद के लिए उपयोगी कंप्रेसर के रूप में देखते हैं। संबद्ध NCD, जिसे [[सामान्यीकृत Google दूरी]] (NGD) कहा जाता है, को फिर से लिखा जा सकता है
:<math> NGD(x,y)= \frac{ \max \{\log f(x), \log f(y)\} - \log f(x,y) }{ \log N - \min\{\log f(x), \log f(y) \}}, </math>
:<math> NGD(x,y)= \frac{ \max \{\log f(x), \log f(y)\} - \log f(x,y) }{ \log N - \min\{\log f(x), \log f(y) \}}, </math>
कहाँ <math>f(x)</math> खोज शब्द वाले पृष्ठों की संख्या को दर्शाता है <math>x</math>, और <math>f(x,y)</math> दोनों वाले पृष्ठों की संख्या को दर्शाता है <math>x</math> और <math>y</math>,) जैसा कि Google या किसी भी खोज इंजन द्वारा लौटाया गया है जो समग्र पृष्ठ संख्या लौटाने में सक्षम है। जो नंबर <math>N</math> अनुक्रमित पृष्ठों की संख्या पर सेट किया जा सकता है, हालांकि प्रत्येक पृष्ठ को उसमें शामिल खोज शब्दों या वाक्यांशों की संख्या के अनुसार गिनना अधिक उचित है। अंगूठे के नियम के अनुसार पृष्ठों की संख्या को एक हजार से गुणा किया जा सकता है...<ref>{{cite journal|title=R.L. Cilibrasi, P.M.B. Vitanyi, The Google Similarity Distance, IEEE Trans. Knowledge and Data Engineering, 19:3(2007), 370-383 |journal=IEEE Transactions on Knowledge and Data Engineering |volume=19 |issue=3 |pages=370–383 |doi=10.1109/TKDE.2007.48 |date=2011-09-27 |last1=Cilibrasi |first1=R. L. |last2=Vitanyi |first2=P. M. B. |arxiv=cs/0412098 |s2cid=59777 }}</ref>
जहां <math>f(x)</math> खोज शब्द वाले पृष्ठों की संख्या को दर्शाता है <math>x</math>, और <math>f(x,y)</math> दोनों वाले पृष्ठों की संख्या को दर्शाता है <math>x</math> और <math>y</math>,) जैसा कि गूगल या किसी भी खोज इंजन द्वारा लौटाया गया है या कोई भी खोज इंजन जो एकीकृत पृष्ठ गणना को लौटाने में सक्षम है। जो संख्या <math>N</math> अनुक्रमित पृष्ठों की संख्या पर सेट किया जा सकता है, यद्यपि यद्यपि इसमें सम्मिलित खोज शब्दों या वाक्यांशों की संख्या के अनुसार प्रत्येक पृष्ठ की गणना करना अधिक उचित हैl जैसा कि अंगूठे के नियम के अनुसार पृष्ठों की संख्या को एक हजार से गुणा किया जा सकता है।..<ref>{{cite journal|title=R.L. Cilibrasi, P.M.B. Vitanyi, The Google Similarity Distance, IEEE Trans. Knowledge and Data Engineering, 19:3(2007), 370-383 |journal=IEEE Transactions on Knowledge and Data Engineering |volume=19 |issue=3 |pages=370–383 |doi=10.1109/TKDE.2007.48 |date=2011-09-27 |last1=Cilibrasi |first1=R. L. |last2=Vitanyi |first2=P. M. B. |arxiv=cs/0412098 |s2cid=59777 }}</ref>
 
 
== यह भी देखें ==
== यह भी देखें ==


Line 43: Line 38:


== संदर्भ ==
== संदर्भ ==
<!--- See http://en.wikipedia.org/wiki/Wikipedia:Footnotes on how to create references using <ref></ref> tags which will then appear here automatically -->
 
{{Reflist}}
{{Reflist}}


Line 51: Line 46:
* [[arxiv:1301.3781|Efficient Estimation of Word Representations in Vector Space]]
* [[arxiv:1301.3781|Efficient Estimation of Word Representations in Vector Space]]
* [[Ming Li|M. Li]] and [[Paul Vitanyi|P. Vitanyi]], An Introduction to Kolmogorov Complexity and Its Applications,Springer-Verlag, New York,  4th Edition 2019
* [[Ming Li|M. Li]] and [[Paul Vitanyi|P. Vitanyi]], An Introduction to Kolmogorov Complexity and Its Applications,Springer-Verlag, New York,  4th Edition 2019
[[Category: सांख्यिकीय दूरी]]


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:CS1 errors]]
[[Category:Created On 24/04/2023]]
[[Category:Created On 24/04/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:सांख्यिकीय दूरी]]

Latest revision as of 11:01, 31 August 2023

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

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

सूचना दूरी

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

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

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

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

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

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

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

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

अनुप्रयोग

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

प्रदर्शन

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

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

सामान्यीकृत सापेक्ष संपीड़न (एनआरसी) के साथ तुलना

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

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

Main article: सामान्यीकृत गूगल दूरी

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

जहां खोज शब्द वाले पृष्ठों की संख्या को दर्शाता है , और दोनों वाले पृष्ठों की संख्या को दर्शाता है और ,) जैसा कि गूगल या किसी भी खोज इंजन द्वारा लौटाया गया है या कोई भी खोज इंजन जो एकीकृत पृष्ठ गणना को लौटाने में सक्षम है। जो संख्या अनुक्रमित पृष्ठों की संख्या पर सेट किया जा सकता है, यद्यपि यद्यपि इसमें सम्मिलित खोज शब्दों या वाक्यांशों की संख्या के अनुसार प्रत्येक पृष्ठ की गणना करना अधिक उचित हैl जैसा कि अंगूठे के नियम के अनुसार पृष्ठों की संख्या को एक हजार से गुणा किया जा सकता है।..[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 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 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=255039’