مقدمة إلى سلاسل ماركوف مع أمثلة - سلاسل ماركوف مع بايثون

مقدمة لسلاسل ماركوف:

هل تساءلت يومًا عن كيفية تصنيف Google لصفحات الويب؟ إذا كنت قد أجريت البحث ، فيجب أن تعلم أنه يستخدم خوارزمية PageRank التي تستند إلى فكرة سلاسل ماركوف. ستساعدك هذه المقالة حول مقدمة إلى سلاسل ماركوف على فهم الفكرة الأساسية وراء سلاسل ماركوف وكيف يمكن تصميمها كحل لمشاكل العالم الحقيقي.

فيما يلي قائمة بالموضوعات التي سيتم تناولها في هذه المدونة:

1. ما هي سلسلة ماركوف؟
2. ما هي خاصية ماركوف؟
3. فهم سلاسل ماركوف بمثال
4. ما هي مصفوفة الانتقال؟
5. سلسلة ماركوف في بايثون
6. تطبيقات سلسلة ماركوف

للحصول على معرفة متعمقة حول علوم البيانات والتعلم الآلي باستخدام Python ، يمكنك التسجيل في البث المباشر بواسطة Edureka مع دعم على مدار الساعة طوال أيام الأسبوع وإمكانية الوصول مدى الحياة.

ما هي سلسلة ماركوف؟

قدم أندريه ماركوف سلاسل ماركوف لأول مرة في عام 1906. وشرح سلاسل ماركوف على النحو التالي:

عملية عشوائية تحتوي على متغيرات عشوائية ، تنتقل من حالة إلى أخرى اعتمادًا على افتراضات معينة وقواعد احتمالية محددة.

هذه عشوائية تنتقل المتغيرات من حالة إلى أخرى ، بناءً على خاصية رياضية مهمة تسمى عقار ماركوف.

هذا يقودنا إلى السؤال:

ما هي خاصية ماركوف؟

تنص خاصية ماركوف للوقت المنفصل على أن الاحتمال المحسوب لعملية عشوائية تنتقل إلى الحالة المحتملة التالية يعتمد فقط على الحالة والوقت الحاليين وهي مستقلة عن سلسلة الحالات التي سبقتها.

حقيقة أن الإجراء / الحالة المحتملة التالية لعملية عشوائية لا تعتمد على تسلسل الحالات السابقة ، تجعل سلاسل ماركوف كعملية بدون ذاكرة تعتمد فقط على الحالة / الإجراء الحالي للمتغير.

لنشتق هذا رياضيًا:

دع العملية العشوائية تكون ، {Xm، m = 0،1،2، ⋯}.

هذه العملية هي سلسلة ماركوف فقط إذا ،

سلسلة ماركوف - مقدمة لسلاسل ماركوف - إديوريكا

لجميع m و j و i و i0 و i1 و im & minus1

بالنسبة لعدد محدود من الحالات ، S = {0 ، 1 ، 2 ، ⋯ ، r} ، هذا يسمى سلسلة ماركوف المحدودة.

تمثل P (Xm + 1 = j | Xm = i) هنا احتمالات الانتقال للانتقال من حالة إلى أخرى. هنا ، نفترض أن احتمالات الانتقال مستقلة عن الوقت.

مما يعني أن P (Xm + 1 = j | Xm = i) لا تعتمد على قيمة 'm'. لذلك ، يمكننا تلخيص ،

صيغة سلسلة ماركوف - مقدمة لسلاسل ماركوف - إيدوريكا

إذن هذه المعادلة تمثل سلسلة ماركوف.

الآن دعونا نفهم ما هي بالضبط سلاسل ماركوف بمثال.

مثال على سلسلة ماركوف

قبل أن أقدم لك مثالاً ، دعنا نحدد ما هو نموذج ماركوف:

ما هو نموذج ماركوف؟

نموذج ماركوف هو نموذج عشوائي يقوم بنمذجة المتغيرات العشوائية بطريقة تتبع المتغيرات خاصية ماركوف.

الآن دعونا نفهم كيف يعمل نموذج ماركوف بمثال بسيط.

كما ذكرنا سابقًا ، تُستخدم سلاسل Markov في إنشاء النصوص وتطبيقات الإكمال التلقائي. في هذا المثال ، سنلقي نظرة على مثال جملة (عشوائية) ونرى كيف يمكن نمذجتها باستخدام سلاسل ماركوف.

مثال سلسلة ماركوف - مقدمة لسلاسل ماركوف - Edureka

الجملة أعلاه هي مثالنا ، وأنا أعلم أنه ليس لها معنى كبير (ليس من الضروري) ، إنها جملة تحتوي على كلمات عشوائية ، حيث:

1. مفاتيح تشير إلى الكلمات الفريدة في الجملة ، أي 5 مفاتيح (واحد ، اثنان ، حائل ، سعيد ، edureka)

2. الرموز تشير إلى العدد الإجمالي للكلمات ، أي 8 رموز.

للمضي قدمًا ، نحتاج إلى فهم تواتر حدوث هذه الكلمات ، يوضح الرسم البياني أدناه كل كلمة جنبًا إلى جنب مع رقم يشير إلى تكرار تلك الكلمة.

المفاتيح والترددات - مقدمة عن سلاسل ماركوف - Edureka

لذا يشير العمود الأيسر هنا إلى المفاتيح ويشير العمود الأيمن إلى الترددات.

من الجدول أعلاه ، يمكننا أن نستنتج أن مفتاح 'edureka' يأتي بمقدار 4x مثل أي مفتاح آخر. من المهم استنتاج هذه المعلومات لأنها يمكن أن تساعدنا في التنبؤ بالكلمة التي قد تحدث في وقت معين. إذا كنت سأخمن الكلمة التالية في جملة المثال ، فسأختار 'edureka' نظرًا لأنه يحتوي على أعلى احتمالية لحدوثها.

بالحديث عن الاحتمالية ، هناك مقياس آخر يجب أن تكون على دراية به وهو التوزيعات المرجحة.

في حالتنا ، التوزيع المرجح لـ 'edureka' هو 50٪ (4/8) لأن تردده هو 4 ، من إجمالي 8 رموز. بقية المفاتيح (واحد ، اثنان ، حائل ، سعيد) كلها لديها فرصة 1/8 لحدوثها (& asymp 13٪).

الآن بعد أن أصبح لدينا فهم للتوزيع الموزون وفكرة عن كيفية ظهور كلمات معينة بشكل متكرر أكثر من غيرها ، يمكننا المضي قدمًا في الجزء التالي.

فهم سلاسل ماركوف - مقدمة في سلاسل ماركوف - إديوريكا

في الشكل أعلاه ، أضفت كلمتين إضافيتين تدلان على بداية الجملة ونهايتها ، وستفهم لماذا فعلت ذلك في القسم أدناه.

الآن دعنا نحدد التردد لهذه المفاتيح أيضًا:

المفاتيح والترددات المحدثة - مقدمة إلى سلاسل ماركوف - Edureka

فلنقم الآن بإنشاء نموذج ماركوف. كما ذكرنا سابقًا ، يتم استخدام نموذج ماركوف لنمذجة المتغيرات العشوائية في حالة معينة بطريقة تعتمد فيها الحالات المستقبلية لهذه المتغيرات فقط على حالتها الحالية وليس حالاتها السابقة.

لذلك بشكل أساسي في نموذج ماركوف ، من أجل التنبؤ بالحالة التالية ، يجب علينا فقط النظر في الحالة الحالية.

في الرسم البياني أدناه ، يمكنك أن ترى كيف يؤدي كل رمز مميز في الجملة إلى رمز آخر. يوضح هذا أن الحالة المستقبلية (الرمز المميز التالي) تستند إلى الحالة الحالية (الرمز المميز الحالي). إذن هذه هي القاعدة الأساسية في نموذج ماركوف.

يوضح الرسم البياني أدناه وجود أزواج من الرموز حيث يؤدي كل رمز مميز في الزوج إلى الآخر في نفس الزوج.

أزواج سلسلة ماركوف - مقدمة لسلاسل ماركوف - إيدوريكا

في الرسم التخطيطي أدناه ، قمت بإنشاء تمثيل هيكلي يوضح كل مفتاح بمجموعة من الرموز المميزة التالية التي يمكن أن يقترن بها.

مجموعة من أزواج سلسلة ماركوف - مقدمة لسلاسل ماركوف - إديوريكا

لتلخيص هذا المثال ، فكر في سيناريو حيث سيتعين عليك تكوين جملة باستخدام مجموعة المفاتيح والرموز التي رأيناها في المثال أعلاه. قبل أن نمرر في هذا المثال ، هناك نقطة مهمة أخرى وهي أننا بحاجة إلى تحديد مقياسين أوليين:

1. توزيع احتمالي أولي (أي حالة البدء في الوقت = 0 ، (مفتاح 'البدء'))

2. احتمال الانتقال للقفز من حالة إلى أخرى (في هذه الحالة ، احتمال الانتقال من رمز مميز إلى آخر)

لقد حددنا التوزيع الموزون في البداية نفسها ، لذلك لدينا الاحتمالات والحالة الأولية ، فلنبدأ الآن في المثال.

• لذا ، لتبدأ بالرمز المميز الأولي هو [ابدأ]

• بعد ذلك ، لدينا رمز مميز واحد فقط ، أي [واحد]

• حاليًا ، تتكون الجملة من كلمة واحدة فقط ، أي 'واحد'

• من هذا الرمز المميز ، يكون الرمز المميز التالي المحتمل هو [edureka]

• تم تحديث الجملة إلى 'one edureka'

• من [edureka] يمكننا الانتقال إلى أي من الرموز المميزة التالية [two، hail، happy، end]

• هناك احتمال بنسبة 25٪ أن يتم اختيار 'اثنان' ، ومن المحتمل أن يؤدي ذلك إلى تكوين الجملة الأصلية (واحدة من edureka و 2 edureka hail edureka happy edureka). ومع ذلك ، إذا تم اختيار 'end' ، فستتوقف العملية وسننتهي بإنشاء جملة جديدة ، أي 'one edureka'.

امنح نفسك تربيتة على ظهرك لأنك قمت ببناء نموذج ماركوف وقمت بإجراء اختبار من خلاله. لتلخيص المثال أعلاه ، استخدمنا الحالة الحالية (الكلمة الحالية) لتحديد الحالة التالية (الكلمة التالية). وهذا بالضبط ما هي عملية ماركوف.

إنها عملية عشوائية حيث تنتقل المتغيرات العشوائية من حالة إلى أخرى بحيث تعتمد الحالة المستقبلية للمتغير على الحالة الحالية فقط.

دعنا ننتقل إلى الخطوة التالية ونرسم نموذج ماركوف لهذا المثال.

مخطط انتقال الحالة - مقدمة لسلاسل ماركوف - Edureka

يُعرف الشكل أعلاه باسم مخطط انتقال الحالة. سنتحدث أكثر عن هذا في القسم أدناه ، فقط تذكر الآن أن هذا الرسم البياني يوضح التحولات والاحتمالات من حالة إلى أخرى.

لاحظ أن كل شكل بيضاوي في الشكل يمثل مفتاحًا وأن الأسهم موجهة نحو المفاتيح المحتملة التي يمكن أن تتبعه. أيضا ، الأوزان على الأسهم تشير إلى الاحتمال أو التوزيع المرجح للانتقال من / إلى الدول المعنية.

كان هذا كل شيء عن كيفية عمل نموذج ماركوف. دعنا الآن نحاول فهم بعض المصطلحات المهمة في عملية ماركوف.

ما هي مصفوفة احتمالية الانتقال؟

ناقشنا في القسم أعلاه طريقة عمل نموذج ماركوف مع مثال بسيط ، والآن دعونا نفهم المصطلحات الرياضية في عملية ماركوف.

في عملية ماركوف ، نستخدم مصفوفة لتمثيل احتمالات الانتقال من حالة إلى أخرى. تسمى هذه المصفوفة مصفوفة الانتقال أو الاحتمالات. عادة ما يتم الإشارة إليه بواسطة P.

مصفوفة الانتقال - مقدمة لسلاسل ماركوف - إديوريكا

ملاحظة ، pij & ge0 ، و 'i' لجميع القيم هي ،

صيغة المصفوفة الانتقالية - مقدمة لسلاسل ماركوف - إديوريكا

اسمحوا لي أن أشرح هذا. بافتراض أن حالتنا الحالية هي 'أنا' ، يجب أن تكون الحالة التالية أو القادمة إحدى الحالات المحتملة. لذلك ، أثناء أخذ مجموع كل قيم k ، يجب أن نحصل على واحد.

ما هو مخطط انتقال الحالة؟

يتم تمثيل نموذج ماركوف بواسطة مخطط انتقال الحالة. يوضح الرسم البياني التحولات بين الحالات المختلفة في سلسلة ماركوف. دعونا نفهم مصفوفة الانتقال ومصفوفة انتقال الحالة مع مثال.

مثال على مصفوفة الانتقال

ضع في اعتبارك سلسلة ماركوف بثلاث حالات 1 و 2 و 3 والاحتمالات التالية:

مثال على مصفوفة الانتقال - مقدمة لسلاسل ماركوف - Edureka

مثال رسم تخطيطي لحالة الانتقال - مقدمة لسلاسل ماركوف - Edureka

يمثل الرسم البياني أعلاه مخطط انتقال الحالة لسلسلة ماركوف. هنا ، 1 و 2 و 3 هما الحالات الثلاث المحتملة ، وتمثل الأسهم التي تشير من حالة إلى الحالات الأخرى احتمالات الانتقال pij. عندما ، pij = 0 ، فهذا يعني أنه لا يوجد انتقال بين الحالة 'i' والحالة 'j'.

الآن بعد أن نحن تعرف على الرياضيات والمنطق وراء سلاسل ماركوف ، فلنقم بتشغيل عرض توضيحي بسيط ونفهم أين يمكن استخدام سلاسل ماركوف.

سلسلة ماركوف في بايثون

لتشغيل هذا العرض التوضيحي ، سأستخدم Python ، لذا إذا كنت لا تعرف Python ، فيمكنك تصفح المدونات التالية:

2. كيف تتعلم Python 3 من Scratch - دليل المبتدئين

فلنبدأ الآن في البرمجة!

مولد نص سلسلة ماركوف

عرض المشكلة: لتطبيق Markov Property وإنشاء نموذج Markov يمكنه إنشاء محاكاة نصية من خلال دراسة مجموعة بيانات كلام دونالد ترامب.

وصف مجموعة البيانات: يحتوي الملف النصي على قائمة بالخطب التي ألقاها دونالد ترامب في عام 2016.

منطق: قم بتطبيق خاصية ماركوف لتوليد خطاب دونالد ترامب من خلال النظر في كل كلمة مستخدمة في الخطاب ولكل كلمة ، قم بإنشاء قاموس للكلمات التي سيتم استخدامها بعد ذلك.

الخطوة الأولى: استيراد الحزم المطلوبة

استيراد numpy كـ np

الخطوة 2: اقرأ مجموعة البيانات

trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt'، encoding = 'utf8'). read () #display the data print (trump) SPEECH 1 ... شكرًا جزيلا. هذا لطيف جدا. أليس هو رجل عظيم. لا يحصل على صحافة عادلة ولا يحصل عليها. هذا ليس عدلاً. ويجب أن أخبركم أنني هنا ، وبقوة هنا ، لأنني أكن احترامًا كبيرًا لستيف كينج وأحترم أيضًا المواطنون المتحدون ، وديفيد والجميع ، وأحب أيضًا حفل الشاي. وكذلك أهل أيوا. لديهم شيء مشترك. الناس يعملون بجد....

الخطوة 3: قسّم مجموعة البيانات إلى كلمات فردية

corpus = trump.split () #Display the corpus print (corpus) 'strong،'، '،' but '،' not '،' strong '،' like '،' us. '،' Iran '،' has '،' المصنف '،' الرعب '، ...

بعد ذلك ، قم بإنشاء وظيفة تولد أزواجًا مختلفة من الكلمات في الخطابات. لتوفير مساحة ، سنستخدم كائن منشئ.

الخطوة 4: إنشاء أزواج للمفاتيح وكلمات المتابعة

كيفية إعداد الكسوف

def make_pairs (corpus): بالنسبة إلى i في النطاق (len (corpus) - 1): العائد (corpus [i] ، corpus [i + 1]) pairs = make_pairs (corpus)

بعد ذلك ، لنبدأ في تهيئة قاموس فارغ لتخزين أزواج الكلمات.

إذا كانت الكلمة الأولى في الزوج هي بالفعل مفتاح في القاموس ، فما عليك سوى إلحاق الكلمة المحتملة التالية بقائمة الكلمات التي تلي الكلمة. ولكن إذا لم تكن الكلمة مفتاحًا ، فقم بإنشاء إدخال جديد في القاموس وقم بتعيين مفتاح مساوٍ للكلمة الأولى في الزوج.

الخطوة 5: إلحاق القاموس

word_dict = {} لـ word_1 ، word_2 في أزواج: إذا كانت word_1 في word_dict.keys (): word_dict [word_1]. إلحاق (word_2) وإلا: word_dict [word_1] = [word_2]

بعد ذلك ، نختار كلمة من المجموعة بشكل عشوائي ، والتي ستبدأ سلسلة ماركوف.

الخطوة السادسة: بناء نموذج ماركوف

#randomly pick the first_word = np.random.choice (corpus) # اختر الكلمة الأولى ككلمة كبيرة بحيث لا تؤخذ الكلمة المختارة من بين جملة بينما first_word.islower (): # ابدأ السلسلة من سلسلة الكلمات المختارة = [الكلمة_الأولى] # تهيئة عدد الكلمات المحفزة n_words = 20

بعد الكلمة الأولى ، يتم أخذ عينات عشوائية من كل كلمة في السلسلة من قائمة الكلمات التي تبعت تلك الكلمة المحددة في خطابات ترامب الحية. هذا موضح في مقتطف الشفرة أدناه:

بالنسبة لـ i في النطاق (n_words): chain.append (np.random.choice (word_dict [chain [-1]]))

الخطوة 7: التنبؤات

أخيرًا ، دعنا نعرض النص المحفز.

#Join تُرجع السلسلة كطباعة سلسلة ('.join (chain)) عدد الأشخاص الرائعين. وهيلاري كلينتون لديها شعبنا وهذا عمل عظيم. ولن نتغلب على أوباما

إذن هذا هو النص الذي حصلت عليه من خلال التفكير في خطاب ترامب. قد لا يكون له معنى كبير ولكنه جيد بما يكفي لجعلك تفهم كيف يمكن استخدام سلاسل Markov لإنشاء نصوص تلقائيًا.

الآن دعونا نلقي نظرة على بعض التطبيقات الأخرى سلاسل ماركوف وكيف يتم استخدامها لحل مشاكل العالم الحقيقي.

تطبيقات سلسلة ماركوف

فيما يلي قائمة بالتطبيقات الواقعية لسلاسل Markov:

1. Google PageRank: يمكن اعتبار الويب بأكمله على أنه نموذج ماركوف ، حيث يمكن أن تكون كل صفحة ويب حالة ويمكن اعتبار الروابط أو المراجع بين هذه الصفحات على أنها انتقالات مع احتمالات. لذلك ، بغض النظر عن صفحة الويب التي تبدأ في تصفحها ، فإن فرصة الوصول إلى صفحة ويب معينة ، على سبيل المثال ، X هو احتمال ثابت.

2. كتابة توقع الكلمات: من المعروف أن سلاسل ماركوف تستخدم للتنبؤ بالكلمات القادمة. يمكن استخدامها أيضًا في الإكمال التلقائي والاقتراحات.

3. محاكاة Subreddit: من المؤكد أنك صادفت Reddit وكان لديك تفاعل على أحد سلاسل المحادثات أو subreddits الخاصة بهم. يستخدم Reddit محاكي subreddit يستهلك كمية هائلة من البيانات التي تحتوي على جميع التعليقات والمناقشات التي تجري عبر مجموعاتهم. من خلال استخدام سلاسل ماركوف ، ينتج المحاكي احتمالات كلمة بكلمة ، لإنشاء تعليقات وموضوعات.

4. منشئ النص: تُستخدم سلاسل ماركوف بشكل شائع لإنشاء نصوص وهمية أو إنتاج مقالات كبيرة وتجميع الخطب. يتم استخدامه أيضًا في مولدات الأسماء التي تراها على الويب.

الآن بعد أن عرفت كيفية حل مشكلة في العالم الحقيقي باستخدام Markov Chains ، أنا متأكد من أنك مهتم بمعرفة المزيد. فيما يلي قائمة بالمدونات التي ستساعدك على البدء بمفاهيم إحصائية أخرى:

بهذا نصل إلى نهاية مدونة مقدمة إلى Markov Chains. إذا كانت لديك أي استفسارات بخصوص هذا الموضوع ، فيرجى ترك تعليق أدناه وسنعاود الاتصال بك.

ترقبوا المزيد من المدونات حول التقنيات الشائعة.

إذا كنت تبحث عن تدريب منظم عبر الإنترنت في علوم البيانات ، فإن Edureka! برعاية خاصة البرنامج الذي يساعدك على اكتساب الخبرة في الإحصاء ، ومشاحنات البيانات ، وتحليل البيانات الاستكشافية ، وخوارزميات التعلم الآلي مثل K-Means Clustering ، و Decision Trees ، و Random Forest ، و Naive Bayes. سوف تتعلم مفاهيم السلاسل الزمنية واستخراج النص ومقدمة للتعلم العميق أيضًا. دفعات جديدة لهذه الدورة ستبدأ قريبًا !!