עיוות זמן דינמי מוסבר באמצעות ערכת נתונים של Python ו-HAR

הועלה מחדש על ידי אפלטון

עוקב: 0

מאמר זה פורסם כחלק מה- בלוגאת מדע הנתונים

היכרות עם גלישת זמן דינמית

סיווג סדרות הזמן הוא משימה נפוצה מאוד שבה יהיו לך נתונים מתחומים שונים כמו עיבוד אותות, IoT, פעילות אנושית ועוד, והמטרה הסופית היא לאמן מודל ספציפי כך שיוכל לחזות את המעמד של כל סדרת זמן עם דיוק כמעט מושלם. למערך הנתונים הנתון צריך להיות תווית של רצפי זמן כדי שהמודל שלנו יוכל לחזות במדויק את המחלקה של סדרת הזמן.

פתרון קלאסי אחד לבעיה זו הוא באמצעות השיטה של אלגוריתם K Nearest neighbor. כאן במאמר זה, אנו הולכים לדלג על הגישה הרגילה של מרחק אוקלידי ונשתמש ב- עיוות זמן דינמי or מדד DTW. שיטה זו אכן לוקחת בחשבון שכאשר אנו משווים שתי סדרות זמן שונות, הן עשויות להשתנות באורך ובמהירות.

הגישה לא כל כך מורכבת אלא משהו שהוא די בלעדי לאלגוריתם DTW או Dynamic Time Warping. כמה טעויות נפוצות עשויות לכלול כוונון ההיפרפרמטרים במודל KNN ופשוט התעלמות מחלק ה-DTW, אבל אסור לעשות זאת. חסרון מרכזי אחד של האלגוריתם הוא שמורכבות הזמן גדלה כמעט באופן אקספוננציאלי עבור מערכי נתונים ענקיים עם רצפים גדולים. ייתכן שלא ניתן יהיה להכשיר מודלים כאלה בפרק זמן סביר. ייתכן שיהיה צורך לבצע כמה שינויים נוספים באלגוריתם כדי להאיץ אותו, עליהם נדון בהמשך.

איך עיוות זמן דינמי עובד?

DTW או עיוות זמן דינמי הוא סוג דינמי של אלגוריתם תכנות שבו סוג אחד גדול של בעיה מחולק לתת-בעיות שונות, אם אפשר. ואז הפתרון של בעיות המשנה נשמר לשימוש מאוחר יותר במקום לחשב אותו שוב. זה די דומה ל תכנות דינמי אשר משמש במבני נתונים ואלגוריתמים ומכאן שזו ההגדרה הבסיסית של האלגוריתם.

אלה ששוכחים את העבר נידונים לחזור עליו" - ג'ורג' סנטיאנה

במאמר זה, נתמקד בחלק של מדעי הנתונים של האלגוריתם ונשתמש בפיתון כשפת הבסיס שלנו כדי להבין כיצד האלגוריתם עובד. אנו נשתמש במודול הספרייה המכונה "dtaiddistance” שיעזור לנו לחשב את המרחק בין שני גלי סינוס המוזזים זה מזה.

כדי להתקין את החבילה, השתמש בקוד הבא:

!pip התקנת dtaidistance

עבור סביבת מחברת או הסר את סימן הקריאה אם אתה מתקין באמצעות שורת פקודה

קוד :

מ-dtaidistance import dtw
מ-dtaidistance יבוא dtw_visualisation כ-dtwvis
ממדגם ייבוא אקראי
ייבוא numpy בתור np
x = np.arange(0, 20, .5)
s1 = np.sin(x)
s2 = np.sin(x - 1)
path = dtw.warping_path(s1, s2)
dtwvis.plot_warping(s1, s2, path)
distance = dtw.distance(s1, s2)

פלט:

האיור שלמעלה מציג את מרחק העיוות האופטימלי בין 2 גלי סינוס

האיור לעיל מציג את המרחק האופטימלי ביותר בין כל הנקודות בין 2 גלי הסינוס. ניתן גם לשרטט את מטריצת התכנות הדינמית או להיקרא גם מטריצת התכנות. זה יציג את כל נתיבי העיוות וכפי שמוצג בתמונה למטה.

קוד :

d, paths = dtw.warping_paths(s1, s2, window=20) best_path = dtw.best_path(paths) dtwvis.plot_warpingpaths(s1, s2, paths, best_path)

פלט:

מטריצת העלות

סוג זה של מטריצה נבנה גם אשר מיישמת אלגוריתם אחר המכונה אלגוריתם Needleman-Wunsch. אלגוריתם זה משמש גם ליישור חלבונים ורצפי נוקלאוטידים בביואינפורמטיקה. יחד עם זה, נעשה שימוש באלגוריתם אחר שהוא מרחק לבנשטיין. שני האלגוריתמים הללו שייכים לסיווג האלגוריתמים של משפחת תכנות דינמיות.

באיור השני, כל שיחה היא מספר המייצג את המרחק של כל שתי נקודות נתונים בהתאמה שמשווים. נקודת נתונים אחת לכל רצף. צבע כהה יותר מסמל מרחק נמוך יותר ואנו יכולים לאחזר את הנתיב האופטימלי ביותר אשר חולץ בצורה של קו אדום כפי שמוצג בתמונה. מורכבות הזמן של זה היא בדיוק O(m,n) כאשר m ו-n הם הרצפים המתאימים ובעלי עלות ריבועית. מקובל בעולם האמיתי שהרצפים גדולים ומודל KNN אינו אופטימלי לחלוטין, המודל הכולל יכול לקחת לא מעט זמן להתאמן.

במקרה שלנו, אנו מודעים לחלוטין להקשר לבעיה שלנו ולאופן שבו אלגוריתם עיוות הזמן הדינמי שלנו יעבוד, ומכאן גם נבצע אופטימיזציה של המודל כדי להפחית את הזמן הכולל שלוקח לאימון אותו. ברוב המקרים, אנו מוצאים שהמסלול האופטימלי הוא דרך האלכסון של המטריצה כפי שקורה גם בדוגמה שלנו. בעולם האמיתי, גם הסטת הפאזה המסיבית או העצומה אינה שכיחה, ומכאן שצפוי שהסטת הפאזה תהיה קרובה בערך אחת לשניה, אחרת העלות תהיה גבוהה מדי. ניתן להסיק את כל אלה משלב חקירת הנתונים וניתן לחלץ את התדרים החשובים גם באמצעות פורייה טרנספורמציה כדי לוודא שאין בעיות בנתונים.

בקוד האחרון, הצגנו את המטריצה באמצעות הפונקציה 'warping_paths()' אשר כברירת מחדל משתמשת בארגומנט אחד 'use_pruning=True' ומכאן שהפינה הימנית העליונה והשמאלית התחתונה נגזמת לצורך אופטימיזציה. המשמעות היא שאחרי עלות מסוימת, הערכים אינם מחושבים מכיוון שזה יהיה אינטנסיבי של מעבד וכבר מצאנו את התוצאה הרצויה שלנו. בגרסאות ישנות יותר של המודול או בגרסה שלפני 2.3.2, היה עליך להעביר את הפרמטר הזה במפורש לפונקציה. כעת נעבור לתרחיש מקרה אמיתי כדי להשתמש במודל שלנו

תיאור מקרה אמיתי להבנת גלישת זמן דינמית

זיהוי פעילות אנושית או מערך נתונים של HAR הוא מה שנשתמש כאן וניתן להוריד אותו מה- ספריית UCL המכיל נתוני סדרות זמן מתויגים מראש. נתונים אלה נלכדו בעזרת סמארטפון שנישא על ידי אדם וניתן לסווג את הפעולה לכמה פעילויות ספציפיות כמו ישיבה, הליכה, עמידה, שכיבה, הליכה_למטה או הליכה_מעלה. את כל אלה ניתן להסיק ממהירות הזווית והתאוצה הליניארית שניתן לקבל מחומרת הסמארטפון. כל תצפית היא נתונים המורכבים מ-561 תכונות וקטוריות עם משתנה תחום הזמן והתדירות ותווית ספציפית המציינת את הפעילות של אדם באותו רגע. המטרה שלנו כאן היא לבנות מודל שיכול לחזות כל פעילות של בן אדם באמצעות הנתונים מהסמארטפון.

קוד :

x_train_file = open(r'UCI HAR Dataset/train/X_train.txt', 'r')
y_train_file = open(r'UCI HAR Dataset/train/y_train.txt', 'r')
x_test_file = open(r'UCI HAR Dataset/test/X_test.txt', 'r')
y_test_file = open(r'UCI HAR Dataset/test/y_test.txt', 'r')
x_train = []
y_train = []
x_test = []
y_test = []
תוויות = {1:'הליכה', 2:'הליכה למעלה', 3:'הליכה למטה', 4:'יושב', 5:'עומד', 6:'שכב'}
עבור x ב-x_train_file: x_train.append([float(ts) עבור ts ב-x.split()])
עבור y ב-y_train_file: y_train.append(int(y.rstrip('n')))
עבור x ב-x_test_file: x_test.append([float(ts) עבור ts ב-x.split()])
עבור y ב-y_test_file: y_test.append(int(y.rstrip('n')))
x_train = np.array(x_train)
y_train = np.array(y_train)
x_test = np.array(x_test)
y_test = np.array(y_test)
colors = ['#D62728','#2C9F2C','#FD7F23','#1F77B4','#9467BD', '#8C564A','#7F7F7F','#1FBECF','#E377C2','# BCBD27']

idx=0

להלן נבדוק את שתי השיטות והחלק הזה חשוב שכן חלק אחד יראה את זמן הביצוע ללא אופטימיזציה והשני יהיה איתו.

קוד ללא אופטימיזציה:

עבור r in range(len(x_test)): distance = dtw.distance(x_train[idx], x_test[r])

זמן ביצוע של התא:

זמן קיר: 25 דקות 16 שניות

קוד עם אופטימיזציה:

עבור r in range(len(x_test)): distance = dtw.distance(x_train[idx], x_test[r], window=20, use_pruning='True')

זמן ביצוע של התא:

זמן קיר: 1 דקות 42 שניות

כפי שאתה יכול לראות את ההבדל המשמעותי במחשב הנייד שלי שמריץ מחברת Jupyter באופן מקורי על שבב i5 דור 8. לכן נשתמש באלגוריתם KNN עם k=20 וגודל חלון של 20 עבור פונקציית עיוות זמן דינמי. המשתנה 'idx' עוזר לאחסן את האינדקס של סדרת הזמן עבור ערכת הבדיקות שלנו.

כעת נגדיר פונקציה עבור המודל שלנו ונחזיר את התוצאה בהתבסס על מספר השכנים של ה-KNN שסופק וגם האינדקס של סדרת הזמן המתאימה של ערכת הבדיקות שלנו ולאחר מכן נחזיר אחת מהתוויות שיכולות להיות:

תוויות = { WALKING, WALKING_UPSTAIRS, WALKING_DOWNSTAIRS, STTING, STANDING, LAYING }

קוד פונקציונלי:

def classifyNN(k:int, idx:int) -> str: idxs=range(0,x_train.shape[0]) n=x_train.shape[0] distances=[] counters={} c=1; max_value=0 עבור r בטווח(n): distances.append(dtw.distance(x_test[idx], x_train[idxs[r]],window=10,use_pruning=True)) NN=sorted(range(len(distances) )), key=lambda i: מרחקים[i], reverse=False)[:k] עבור l ב-l labels.values(): מונים[l]=0 עבור r ב-NN: l=labels[y_train[r]] counters[l]+=1 if (counters[l])>max_value: max_value=counters[l] #print('NN(%d) has label %s' % (c,l)) c+=1 # תווית עם מפתחות תדירות מקסימלית = [k עבור k במונים אם מונים[k] == max_value] # מחזירה מדגם אקראי אחד במקרה שקיימת שוויון בין מספר תוויות החזר (sample(keys,1)[0])

מקרי מבחן

כאן נדגים כמה ממקרי הבדיקה לדוגמה, אך אתה יכול להרגיש חופשי להתנסות עם כל ערך 'idx' ולמצוא את התווית המתאימה למקרה המבחן הזה.

1. מקרה מבחן ראשון: עמידה

קוד להצגת הנתונים:

k=20 idx=3 plt.plot(x_test[idx], label=labels[y_test[idx]], color=colors[y_test[idx]-1], linewidth=2) plt.xlabel('Samples @50Hz' ) plt.legend(loc='upper left') plt.tight_layout()

פלט:

קוד למציאת תווית הבדיקה:

%%זְמַן
לסווגNN(k,idx)

פלט:

זמן קיר: 3 דקות 13 שניות 'בעמידה'

2. מקרה מבחן שני: ישיבה

קוד להצגת הנתונים:

k=20 idx=200 plt.plot(x_test[idx], label=labels[y_test[idx]], color=colors[y_test[idx]-1], linewidth=2) plt.xlabel('Samples @50Hz' ) plt.legend(loc='upper left') plt.tight_layout()

פלט:

קוד למציאת תווית הבדיקה:

%%זְמַן
לסווגNN(k,idx)

פלט:

זמן קיר: 3 דקות 15 שניות 'SITING'

3. מקרה מבחן שלישי: הליכה

קוד להצגת הנתונים:

k=20 idx=401 plt.plot(x_test[idx], label=labels[y_test[idx]], color=colors[y_test[idx]-1], linewidth=2) plt.xlabel('Samples @50Hz' ) plt.legend(loc='upper left') plt.tight_layout()

פלט:

קוד למציאת תווית הבדיקה:

%%זְמַן
לסווגNN(k,idx)

פלט:

זמן קיר: 3 דקות 9 שניות 'הליכה'

אז בכל הדוגמאות הללו, אנו יכולים לראות שהאלגוריתם הצליח לתייג נכון את סדרת הזמן ובעל דיוק רב. פונקציונליות החלונות גם מפחיתה מאוד את הזמן שלוקח למודל להתאמן ואם אתה לא מאמין לי, אתה יכול לשנות ידנית את ארגומנט החלון ולראות את ההבדל בזמן הנדרש לאימון המודל.

האם מקבילה היא אפשרות לאופטימיזציה של גלישת זמן דינמית?

ובכן, השאלה הכללית הבאה כאן היא לגבי הקבלה, שכן כאשר NumPy ופנדות מסגרת הנתונים עבדו על מערך הנתונים העצום והיה צורך לעשות משהו בזמן קצר יותר, Spark נוצר בין השאר כדי להשתמש בתרחיש הטוב ביותר של ריבוי מעבדים במכונה.

באופן דומה כאן אנו יכולים לראות שבצורה הנוכחית הזו של עיוות זמן דינמי, ההקבלה היא מאוד קשה ואני אעדכן אותה במאמר הבא אם אמצא שיטות, אבל אתה יכול לספק כמה אופטימיזציות אחרות לאלגוריתם כדי להפחית את המורכבות, אבל זה יהיה גם להשפיע על דיוק המודל. אז האתגר נותר לצמצם את מורכבות הזמן ללא הפחתה רבה ברמת הדיוק של המודל.

אפשרות אחת היא להאיץ את התהליך אם מחשבים את מרחקי זוג ה-DTW של כל נתוני סדרות הזמן במערך הנתונים וזה אכן משיג רמת מקביליות לפי הרעיון. זה יעזור לנו לבנות את מטריצת המרחק מהר יותר וגם הגדלת אפשרות הגיזום תאפשר לאימון להתעלם מנקודות נתונים נוספות, אבל זה אולי לא הפתרון האופטימלי בכל המקרים.

סיכום

ניתן להפוך את סיווג סדרות הזמן ליעיל מאוד על ידי שימוש בשילוב של שני אלגוריתמים KNN ו-DTW וכאן מערך הנתונים המשמש הוא אחד מני רבים תרחישים אפשריים שבהם ניתן להשתמש במודל זה כדי לסווג את הנתונים לתוויות שונות ועל ידי שינוי מקור הקלט ל- נתונים חיים או זרם נתוני קלט, אתה יכול לקבוע איזו פעילות משתמש עושה בזמן אמת. יש הרבה אפליקציות שמשתמשות בזה בזמן אמת כמו StepSetGo היא אפליקציה שמשלמת לך במטבע שלהם עבור הליכה. כך שאם אתה משתמש בדגם הזה ותשלוף את נתוני המשתמש ישירות מחיישני הסמארטפון, תוכל לקבוע את הפעילות של המשתמש באותו רגע.