אלגוריתם קורי העכביש
אלגוריתם קורי העכביש (COBWEB) משמש עבור מערכת גדלה שבה קיימת היררכיה של קיבוץ קונספטואלי (conceptual clustering). שיטת קורי העכביש הומצאה על ידי פרופסור דאגלס. ה. פישר, אשר נכון לשנת 2017 עובד באוניברסיטת ואנדרבילט.[1][2]
אלגוריתם קורי העכביש מארגן תצפיות באופן הדרגתי לתוך עץ מסווג (classification tree). כל צומת סיווג בעץ מייצג מחלקה אשר מאופיינת על ידי חישוב הסתברותי. החישוב ההסתברותי מסכם את ההתפלגויות המותנות בתכונות של האובייקטים המסווגים תחת אותה צומת. עץ מסווג זה יכול לשמש כדי לחזות תכונות חסרות או את המחלקה של אובייקט חדש.[3]
ישנן ארבע פעולות בסיסיות שאלגוריתם קורי העכביש משתמש בהן כדי לבנות אשכולות מסווגים. כל תהליך שנבחר תלוי בקטגוריית השירות (Category of 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
קישורים חיצוניים
[עריכת קוד מקור | עריכה]- יישום של קורי עכביש בשפת פייתון.
הערות שוליים
[עריכת קוד מקור | עריכה]- ^ Fisher, Douglas (1987). "Knowledge acquisition via incremental conceptual clustering" (PDF). Machine Learning. 2 (2): 139–172. doi:10.1007/BF00114265.(הקישור אינו פעיל)
- ^ Fisher, Douglas H. (ביולי 1987). Improving inference through conceptual clustering. AAAI Conference. Proceedings of the 1987 AAAI Conferences. Seattle Washington. pp. 461–465.
{{cite conference}}: (עזרה) - ^ 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)