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

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

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

== [[सूचना दूरी]] ==
हम मान लेते हैं कि जिन वस्तुओं के बारे में एक-एक बातें होती हैं वे 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>                               
:<math>|p| = \max \{K(x\mid y),K(y\mid x)\}</math>
लघुगणक योजक शर्तों तक जिसे अनदेखा किया जा सकता है। इस सूचना दूरी को [[मीट्रिक (गणित)]] दिखाया गया है (यह लघुगणक योगात्मक शब्द तक मीट्रिक असमानताओं को संतुष्ट करता है), सार्वभौमिक है (यह प्रत्येक संघणात्मक दूरी को गणना के रूप में, उदाहरण के लिए सुविधाओं से लेकर एक निरंतर योगात्मक शब्द तक, परिकलित करता है)।<ref name="BGLVZ98"/>                 
=== सामान्यीकृत सूचना दूरी (समानता मीट्रिक) ===
सूचना दूरी निरपेक्ष है, लेकिन अगर हम समानता व्यक्त करना चाहते हैं, तो हम सापेक्ष में अधिक रुचि रखते हैं। उदाहरण के लिए, यदि 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>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> संपीडक 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"/>
:एनसीडी वास्तव में कंप्रेसर Z के साथ पैरामीट्रिज्ड दूरी की एक श्रेणी है और बेहतर Z है, एनसीडी एनआईडी के जितना करीब है, परिणाम और बेहतर हैं।<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>{{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>                          
== सामान्यीकृत गूगल दूरी ==

{{main|सामान्यीकृत गूगल दूरी}}

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

* [[Word2vec]]

== संदर्भ ==

{{Reflist}}


== बाहरी संबंध ==

* [[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

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