אלגוריתם קורי העכביש

תוכן שנמחק תוכן שנוסף

בשורה

גרסה מ־22:07, 31 בינואר 2017

אלגוריתם קורי העכביש (COBWEB) משמש עבור מערכת גדלה שבא קיימת היררכיה של קיבוץ קונספטואלי (conceptual clustering). שיטת קורי העכביש הומצאה על ידי פרופסור דאגלס. ה. פישר, אשר כרגע עובד באוניברסיטת ואנדרבילט.^[1]^[2]

קורי עכביש מארגן תצפיות באופן הדרגתי לתוך עץ מסווג (classification tree). כל צומת סיווג בעץ מייצגת מחלקה אשר מאופיינת על ידי חישוב הסתברותי, החישוב ההסתברותי מסכם את ההתפלגויות המותנות בתכונות של האובייקטים המסווגים תחת אותה צומת. עץ מסווג זה יכול לשמש כדי לחזות תכונות חסרות או את המחלקה של אובייקט חדש.^[3]

ישנן ארבע פעולות בסיסיות שאלגוריתם קורי העכביש משתמש בהן כדי לבנות אשכולות מסווגים. כל תהליך שנבחר תלוי בקטגורית השירות (category utility) של הסיווג המושגת על ידי יישום אלגוריתם זה. תהלכי הביצוע הם:

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

COBWEB(root, record):

Input: A COBWEB node root, an instance to insert record

if root has no children then

children := {copy(root)}

newcategory(record) \\ adds child with record’s feature values.

insert(record, root) \\ update root’s statistics

else

insert(record, root)

for child in root’s children do

calculate Category Utility for insert(record, child),

set best1, best2 children w. best CU.

end for

if newcategory(record) yields best CU then

newcategory(record)

else if merge(best1, best2) yields best CU then

merge(best1, best2)

COBWEB(root, record)

else if split(best1) yields best CU then

split(best1)

COBWEB(root, record)

else

COBWEB(best1, record)

end if

end

קישורים חיצוניים

יישום של קורי עכביש בשפת פייטון.

מקורות

תבנית:Reflist

^ Fisher, Douglas (1987). "Knowledge acquisition via incremental conceptual clustering" (PDF). Machine Learning. 2 (2): 139–172. doi:10.1007/BF00114265.
^ {{cite conference}}: Empty citation (עזרה)
^ William Iba and Pat Langley. "Cobweb models of categorization and probabilistic concept formation". In Emmanuel M. Pothos and Andy J. Wills, (ed.). Formal approaches in categorization. Cambridge: Cambridge University Press. pp. 253–273. ISBN 9780521190480.{{cite book}}: תחזוקה - ציטוט: extra punctuation (link)

[1] Fisher, Douglas (1987). "Knowledge acquisition via incremental conceptual clustering" (PDF). Machine Learning. 2 (2): 139–172. doi:10.1007/BF00114265.

[2] {{cite conference}}: Empty citation (עזרה)

[3] William Iba and Pat Langley. "Cobweb models of categorization and probabilistic concept formation". In Emmanuel M. Pothos and Andy J. Wills, (ed.). Formal approaches in categorization. Cambridge: Cambridge University Press. pp. 253–273. ISBN 9780521190480.{{cite book}}: תחזוקה - ציטוט: extra punctuation (link)

[1]

[2]

[3]