صفحه 1:
صفحه 2:
5
دانشگاه صنعتي امير كبير otal gh
بهينه سازى كشف اطلاعات از مستندات نيمهساختيافته XML
Optimizing Information Discovery
from Semi-Structured XML Documents
دانشجو
مینا ملكي
استاد راهنما
دکتر احمد عبداللهزاده بارفروش
!يهنن 1385
صفحه 3:
gta ER
ضرورت انجام پژوهش
هدف پژوهش
طبقه بندي مستندات
روش هاي وزن دهي ويژگي
روش وزن دهي ويژگي پيشنهادي ۳6066
روش وزن دهي ويژگي پيشنهادي ۵
سیستم طبقه بندي کننده مستندات نیمه ساختیافته 60
مشخصات بستر آزمايشگاهي پیاده سازي شده
نتایج ارزيابيهاي انجام شده
صاج حاحص ضاح حاص شاك
نتیجه گیری. دستاوردهای پروژه. پیشنهاد کارهای آبنده
مشاه سست هایهوشت.
مينا ملكي- بهيته سازي كشف اطلاعات از مستندات نيمه ساختيافته 20001 nO
صفحه 4:
fl ۱ @
اشرورت نجام يزوهض 0
4 ساختيافته ؟
مستندات نیمه ساختیافته با
]لت کیدزن ند
کشف خود کار اطلاعات ازمستندات نیمه ساختيافته ,21۷11
کشف خودکار دانشهاي جدید, الگوهاء
ارتباطات در مجموعه وسيعي از مستندات متن کاوی
ae ale خلاصه سازي
مس ههور IML sb Ss AS glo کي
صفحه 5:
بهبود كارايي طبقه بندي کننده
بهبود کشف اطلاعات از مستندات نیمه ساختیافته 20
۰ تشخیص معناي کلمات مبهم
221 70 تت اراد سس بان هشیر
مينا ملكي- يهيته سازي كشف اطلاعات از مستددات نيمه ساختيافته .0861 RAT
صفحه 6:
fl
D={d, ...روت “ ِ =
C={G, O,..-Gyt تصميم گيري
1 رك
ay = 0 0 G © | aa 9 1
آذآ فازهاي طبقه بندي
۴ فاز آموزشي ساخت مدل با استفاده از مستندات آموزشي
© فار آزمايشي > استفاده از مدل بر روي مستندات آزمايشي
آزمایشگا سيستع هاي موشمند
مينا ملكي- يهينه سازي كشف اطلاعات از مستندات نيمه ساختيافته .0861 CT
صفحه 7:
پیش پردازش مستندات
# شاخص بندي مستندات
* تیدیل مستندات به برداري از کلمات تشکیل دهنده
۳ 7 * آستانه يابي تکرار مستندات (015)
انتخاب ويژگي (IG) tes oe? 8
* کاهش ایعد بردار کلمات ۰ **قدرت ويژگي (۳5) * روش هاي مبتني بر 1۳
IDE *#*روش هاي مبتني بر © Sa
2 7 وزن دهي ويزكي *
> تعیین میزان اهمیت. و قدرث کلمات انتخاب شنده در متمایز کزدن هر مستند از سایر مستندات
لق طبقه بندي مستندات **طبقه بندي کننده هاي بیزین
طبقه بندي مستندا *#نزدیکترین 16 همسایه (KNN)
© اعمال الكوريتم طبقه بندي بر روي بردار *درخت هاي تصميم گيري
*”شبكه هاي عصبي
** ماشين هاي بردارهاي يشتيبان (SVM)
آزمایشگا سيستع هاي موشمند
مينا ملكي- يهيته سازي كشف اطلاعات از مستددات نيمه ساختيافته .0861 RAT
كلمات انتخاب و وزن دهي شده مستندات
صفحه 8:
1 0 ا] الگوهاي آماري رخداد کلمات | با
eS. 6 | سیستم هاي خبره ما
8 إدرخت هاي تصميم كيري | )و همکارلن
2 | روش KOO بو و همكزلن
4 | الگوریتم اس اس
ارائه الكوريتم جديد 4 ا طبقه بندي کننده بیزین سا و همکزلن
Cn OAS ge alee | موز ]روش Obie erm] WEP yen
رجات ی 6 | شبكه هاي عصبي باس
OO | 1998 سیر
niga ge ail!
LCT 1040, میا ملکي-هینهسازي کشف اطلاعت از مستدات نیمه ساخیافته
صفحه 9:
fl @
oT)
بهبود روش وزن دهي ويژگي براي بالابردن كارايي طبقه بندي کننده
مستندات نیمه ساختیافته ,21
مينا ملكي- يهيته سازي كشف اطلاعات از مستددات نيمه ساختيافته .0861 مسسمدسمد ممه he
صفحه 10:
fl @
tis هاي وزن دهي BD
افآ وزن دهي ويزكي
(ولا...رزلا") - ee dG 2 04:6 اكر
تعداد پيژگيهايمتمایز در کلمجموعة
+۷ وززههيپيژگي ,ا در مستند 0
أن روش هاي متداول وزن دهي ويژگي
© روشهاي مبتني بر 1۳
> تابعي از توزیع ويژگي در هر يك از مستندات
۴ روشهاي مبتني » IDF
< تابعي از توزیع ويژگي در مجموعه مستندات
# روش هاي بر اطلاعات طبقات
> تابعي از توزيع ويزكي در طبقات
deD
santa glo ges dCs)
AT 0861. مينا ملكي- يهينه سازي كشف اطلاعات از مستندات نيمه ساختيافته
صفحه 11:
ایده: افزایش وزن دهي ويژگي با افزایش فرکانس ويژگي در هر مستند.
ب يف8 - رط
مينا ملكي- يهيته سازي كشف اطلاعات از مستددات نيمه ساختيافته .0861
<b,
=the a =|? | اد
4,€vectoof d,
نام روش
۳
1
1+ 016, 0( ret
wah | a TOTES ATT
ape | Me =ITRE, ay =I
6 Wig = Sparc, dq) 2۳۲,۹۳۳ 153۵ | دوس 6
تسش
صفحه 12:
ایده: کاهش وزن ويژگي با افزایش ف رکانس ويژگي در مجموعه مستندات D
fal
=i لیم
10: Wy =idft;,, d;) OS EO
ree Wa =thidgft,, d) =tht,, d)*idht,, d)
: ___tfidtt,, d)
were 31 TS tid ft, Ay
اط| تعداد کل مستندات مجموعه ط
|(,۶)| تعداد مستنداتی از مجموعه ظ دارای ویژگی ۸
fal
santa glo ges dCs)
RAT 0841. أطلاعات از مستندات نيمه ساختيافته
مین كيت يهينة لوي “كد
صفحه 13:
ها روش ۲۳۳۳"
© سال 2005 توسط آقاي 1.810
|e بو rf{t,,¢;) =lo
المع مقاط إل
رسک
[(ره ,/۳2۷] تعداد مستنداتی از مجموعه 72 و طبقه ره دارای ویژگی »1
I
4+ تعدد مستداتی از مجموعد 0 و طبقه اى غير از طبقه ره داراى ويذكى genres EDs 0)
( مه ماد( مزاآلا
Whi = TFRR ty, dj) <
یه( من رل
ره طبقه مستند ,4
آزمایشگا سيستع هاي موشمند
مينا ملكي- يهينه سازي كشف اطلاعات از مستندات نيمه ساختيافته .0861 — AT
صفحه 14:
اه )© )© @
TFCRF
*: تعداد مستندات فاقد ويژگي > از كلاس ,©
: تعداد مستندات داراي ويژگي >« از كلاس ,©
> تعداد مستندات داراي ويژگي 5 از کلاس غیر و6
تعداد مستندات فاقد ويژگي > از كلاس غير ,©
وسسسسسسسسسسسس سس
مينا ملكي- يهيته سازي كشف اطلاعات از مستددات نيمه ساختيافته .0861
age
صفحه 15:
fl
(ast) TFCRE
ندا روش هاي وزن دهي ويزكي مبتني بر ”11(1
a+b+c+d
bee ‘|
|
|
N
idi =] =]
107 عع لماك
وزن در (1)- وزن 2 در (2) -وزن ۲ در (3) - وزن > در (4)
2 روش 7۳0/7
T(x q) =loq 2+?
2
»4 ©) © @
1 وزن > در (4)< وزن ع در (3) < وزن > در (1) < وزن > در (2)
ae ie)
صفحه 16:
(acts) TFCRE
روش وزن دهي ويژگي TFRF
وزن ۲ (الف) <وزن 2 (ب) < وزن 2 (ج) < وزن ۲ (د)
1
۱
5 .
سوک بیس fl روش وزن دهي ويزكي منطقي
\
QO © | افش
SD اراد سس بان هشیر
مينا ملكي- يهيته سازي كشف اطلاعات از مستددات نيمه ساختيافته .0861 مسد وموم he
صفحه 17:
fl rox 17
| (زه |
لت = positiveRk, G)
|X) | 5
نت رو crfValué,,
negativeR&, c;) الفط ا
negativeRf, G) = Pinal
هگ
زعم کر
pe, )| تعداد مستندات طبقه ره لاره: 64 تعداد مستندات طبقه ره دارای ویژگی 4
لمم رانک سس مان بش
مينا ملكي- يهينه سازي كشف اطلاعات از مستندات نيمه ساختيافته .0861 TT I
صفحه 18:
o
رن
ها مثال: طبقه بندي مقالات علمي برچسب گذاري شده ۱0
۴ فرکانس ويژگي در "عنوان " ! بار
۴ روش وزن دهي ويژگي 1
100+2+1=103 a
20939 روش
Sl مساله: تعیین میزان اهمیت (وزن) اجزاء مستند نیمه سا
راه حل 1: فرایند مکاشفه اي در تعیین میزان اهمیت هر جزء JLs Bir) 2004(
Sl راه حل2: طبقه بندي کننده متا (0۳۳۸۳) سال 2004 و 2006)
فا راه حل 3: روش وزن دهي ویژگی LOPE ادي (۳۳() در سال 2007)
le gine dala) موشمند
مينا ملكي- يهينه سازي كشف اطلاعات از مستندات نيمه ساختيافته .0861 I
صفحه 19:
a o
660, ایده: وزن دهي ويژگي براساس اطلاعات ساختاري مستندات نیمه ساختيافته Gl
HOD تکنيك: توجه به چگالی هر يك از اجزاء تشکیل دهنده مستند
مجتنومه أچزآه موجود: در مستییات :1/167 تجیوی: 9 يه...روا- ير
۷ تعداد کل مستندات مجموعه 1 N
(:© ررك مي ب 5 /1- (رع انال
08 مجموعه کل ویژگیهای متمایز در D له ماع 1د
x
(رء..4.)# 2 لآ ميانكين كل كلمات موجود در جزء ره مجموعه ظ
۵۱۳1۳۵6۵۸ < (4 1716 < با
آزمایشگا سيستع هاي موشمند
مينا ملكي- يهيته سازي كشف اطلاعات از مستددات نيمه ساختيافته .0861 سس
صفحه 20:
پردازشگر لو
واحد طبقه بندي کننده ماه ید
مستندات نیمه ساختيافته XO)
سس سح
ریت OT — (poy aoa cea ue
صفحه 21:
0030
زیر سیستم وزن دهی ویزقی
صفحه 22:
fl @
رتم پالنده ستندات
الآ وظیفه: در
افت و پالايش مجموعه مستندات 26۲ ورودي جهت تعیین مجموعه 1
20 ورودي: مستندات نیمه ساختیافته Gl
1( خروجی: مستندات پالایش شده 60 به عنوان مجموعه Gl
لآ مولفه ها
ae ""حاوي اطلاعات معنايي مهم نیستند.
v
© حذف کننده برچسب هاي غیر ضروري
© بررسي کننده ساختار مستندات /60(
# انتخاب کننده مستندات Sree) ous CAL XML
سس سح
ریت OT — (poy aoa cea ue
صفحه 23:
وظیفه: پردازش مجموعه مستندات 7 جهت استخراج ويژگي هاي مهم با حفظ
اطلاعات ساختاري
a
ورودي: مجموعه مستندات 1
a
خروجی: مجموعه مستندات 2 شاخص بندي شده
a
مولفه ها
۲ شاخص بندي مستندات و استخراج کلمات با حفظ اطلاعات مکانه
© تحلیلگر لغوي ساختاري VY
احذف اعداد و علائم نگارشي
سازنده پایگاه داده ۲ یکسان سازي شکل حروف
حذف کلمات توقف ريشه يابيشده
۴ پالاینده لغوي
Y gH ريشه يابي کلمات
ss ts)
la موشمند
عينا ملكي- يهينه سازي كشف اطلاعات از مستندات نيمه ساختياقت RFT AML
صفحه 24:
ژگی ها (دامم
قالب مستندات شاخص بندي شده
تعداد آتعداد
[vn 1 « ) اسسشتتس] | مستسا | | مت ) هه
كك
تعلاد
30 تعداد
سس ناسا تكرار ويذكي در برجسب
آزمایشگا سيستع هاي موشمند
مينا ملكي- يهينه سازي كشف اطلاعات از مستندات نيمه ساختيافته .0861 سس A
صفحه 25:
fl
GI وظیفه: کاهش ابعاد ويژگي هاي تشکیل دهنده مستندات و انتخاب بهترین آذ
SP Sho 3 5 3 تن
اث ورودي: جداول يايكاه داده حاوي ويژگي هاي شاخص بندي شده ساختاري
SI خروجي: ليستي از ويژگي هاي انتخاب شده
500
زمولند ها لاتعريف حد آأستانه بانين وبال
© فیلتر کننده ويژگي ها حذف ويژگي هاي نادر > اشکال املائي یا ذهن خلاق نویسنده (
حذف ويژگي هاي وافر > کلمه توقف حذف نشده
Saas 2ت
۳77 ل
OT — (poy aoa cea ue ریت
صفحه 26:
fl @
Sis ليرسيستم وزن
أذ وظيفه: تعيين ميزان اهميت هر يك از ويزكي هاي مستند در متمايز كردن آن
تند از ساير مستندات
اذ ورودي: برداري از ويزكي هاي انتخاب شده به همراه اطلاعات شاخص بندي
نها
6
a خروجي: بردار ويژگي هاي وزن دهي شده
آزمیشگاه سست ها
أطلاعات از مستندات نيمه ساختيافته .3081
صفحه 27:
a Oo
ده ريش 777909989
برنامه نويسي ۸0 با بیش از 6500 خط کد
تا پیاده سازي در چارچوب 0090 به
> 7 مستندات ورودي»0 GI
لمم رانک سس مان بش
مينا ملكي- يهينه سازي كشف اطلاعات از مستندات نيمه ساختيافته .0861 TT I
صفحه 28:
fl
حه اه رت مدمه همه اه دح مد 65 ‘Sibisame Ficepacrick at aftuapacdgwa:edu, or Macy Grossien
سوریو و مس ce or coe ویک هگ
۳
مينا ملكي- يهينه سازي كشف اطلاعات از مستندات نيمه ساختيافته .0861
صفحه 29:
fl @
(Hines جوم سسا
SS! شامل 12107 مقاله علمی از 18 مجله ان
5 تا 2002 به فرمت 20
ات تاریخچه
انجمن کامپیوتر 16008 از سال
ها برچسب هاي مستندات fx
۴ برچسب هاي پایه
< حفظ برچسب ابتداانها و محتویات
عع ست 0
اپ اي کشت را هه بخ 200 هو
صفحه 30:
a
5 تا 2002 به فرمت 20
@
nei aD
شامل 12107 مقاله علمی از 18 مجله انتشارات انجمن کامپیوتر 16008 از سال
fl
= + | حت جاب | مراجع
لا برچسب هاي مستندات »9 a
ate he? [Epp 8 = إن | أدرس وب
برچسب هاي پایه name Ol pl syle | volo | *
معط | شماره جاب | Sods امحل کارا
۰ ب هاي حذف شدني 9 مت
> حن ۳ at | رافك Ste | ET math, hath
حذف برجسب ابتدااانتها و محتويات
ak i |i, footnote | درداتي
poetry | شمر ee
2h | super wee) | ab
| تریخ اروزه ماه سای a | ade
مس — Ee
مينا ملكي- يهينه سازي كشف اطلاعات از مستندات نيمه ساختيافته .0861
و
صفحه 31:
fl
شامل 12107 مقاله علمی از 18 مجله انتشارات انجمن کامپیوتر 10090 از سال
5 تا 2002 به فرمت 20
a
7 تاريخجه : دانشكاه «محاف<0 آلمان Gl
ل برجسب هاي مستئدات سد اماه مهاه 71060 | مد | ارات
item-bold, 5
item-both, ۰
tie] <p> | برچسب هاي پایه عسي مويو نفدي
itenrandash,itenvavaapara, item
roman, iene, هاي حذف شدني ey ©
بت ی ۳ 5
برچسب هاي تبدیل شدني ۴
تبديل برجسب ابتدا/ انتها مبدا به مقصدا تاد >
<emp> | nbediunicizht,sepsmalleaps,
te typewriter font
ی
آزمایشگا سيستع هاي موشمند
مينا ملكي- يهينه سازي كشف اطلاعات از مستندات نيمه ساختيافته .0861 TT
صفحه 32:
fl
[SI شامل 12107 مقاله علمی از 18 مجله انت
5 تا 2002 به فرمت 20
انجمن کامپیوتر 1600 از سال
a
اد" برچسب هاي مستندات few
۴ برچسب هاي پایه
۴ برچسب هاي حذف شدني
برچننب شروع مقاله
é روز ی
برچسب هاي تبدیل شدني 5 | اطلاعات تبتر
برچسب هاي ساختاري oe. | MTNA hdd
۳ ۳ ار
جذف برچسب ابتدا/ انتها ۱17 EL. BE. | 7
cde. انیس نا انا
mumerictbrace, bullet sie)
santa glo ges dCs)
TT 0861. مينا ملكي- يهينه سازي كشف اطلاعات از مستندات نيمه ساختيافته
صفحه 33:
49
مجموعه مستندات ووورمن 12720
te
td
tg
مينا ملكي- يهيته سازي كشف اطلاعات از مستددات نيمه ساختيافته .0861
ieee transactions on knowledge and data engineenng,
ieee transactions on pattern analysis and machine intelligence
ieee ttansactions on computers
ieee transactions on parallel and distributed systems
ieee transactions on visualization and computer graphics
ieee transactions on software engineering,
ivr te ayo
1
VA
صفحه 34:
پیاده سازي در چارچوب ۳۸( به زبان برنامه نويسي (4 با بیش از 6500 خط کد
> مستندات ورودي»1161 GI
ان الگوریتم طبقه بندي کننده GOD €
5
یشگا سستی های هوشت.
مينا ملكي- يهينه سازي كشف اطلاعات از مستندات نيمه ساختيافته .0861 TT I
وسسسسسسسسسسسس —
صفحه 35:
ban Gl
102,۰۰۰ فحات plar gag leg
در فضاي بعدي که نمونههاي مثبت و
منفی را با بیشترین حاشیه از هم جدا کنند.
2
مزاياي 000:
© بهترین الگوریتم طبقه بددي مستندات
© قابلیت کار با تعداد ويژگي هايي زياد
* عدم تاثیر تعداد ويژگي بر كارايي الگوریتم
© يايداري
پیاده سازي توسط (10808000ما
مينا ملكي- يهينه سازي كشف اطلاعات از مستندات نيمه ساختيافته .0861
صفحه 36:
ازي شده
Gl پیاده سازي در چارچوب 0۳ به زبان برنامه نويسى 0 با بيش از 6500 خط كد
GI مستندات ورودي 1261 ->
أذ الكوريتم طبقه بندي کننده 600 >
)06( روش انتخاب ويژگي > آستانه يابي فرکانس مستندات SI
221 70 تت اراد سس بان هشیر
مينا ملكي- يهينه سازي كشف اطلاعات از مستندات نيمه ساختيافته .0861 TT
صفحه 37:
fl @
DE 55088)
دلیل انتخاب
۰ سادگي
۴ هزینه محاسباتي پائین
۰ دقت و كارايي معادل بهترین روش هاي انتخاب ويژگي نظیر 16
@ مناسب در حوزه طبقه بندي مستندات
2
2
ایده: ظاهر شدن ویژگی در تعداد مستندات > بالا بودن ارزش معنايي ويژگي
یکدیگر (بعد از حذف کلمات توقف)
Sl راهکار: شمارش تعداد مستندات داراي ويژگي
آزمایشگا سيستع هاي موشمند
مينا ملكي- يهينه سازي كشف اطلاعات از مستندات نيمه ساختيافته .0861 HT
صفحه 38:
ان مستندات ورودي(0 12 >
2 الگوریتم طبقه بندي کننده GOO €
BI روش انتخاب ويژگي؟00) >
نا روشهاي وزن دهي ویژگی گمبتني بر ۳ +مبتني بر+ ۳00 + ۳ + 10
“LODE 1 5 1
a
تقسیم بتدي مستندات به نسبت 3/2 آموزشي و 3/1 آزمايشي
@
تعداد کلمات توقف بعد از تکمیل 1392 کلمه 00726 > کلمه توقف ريشه یابی شده
ماگنه اي کشت هت از نات WO es و
صفحه 39:
میانگین میکرو میانگین ماکرو
PCs) 3
id TP; 3
LPC) dpe ED
E
5 | رمعم +ررعم 2 ا
A
TRe)+TNe,) 1 1 ۳
LTR) 5 8 7 +13 + رعرع بجيجج- (كفه
Re = i 2 3 (رعد 7 5 7 7
___TAG) 1 a :
ل FNC,)) +“ متیر Pre,) “TR,)+ FAG,)
م مج را ير 7
are 66-7
a I | SEED
عبن ملكي يهينه سازي كشف اطلاعات از مستندات نيمه ساختيفته 2084 — ۳۳
صفحه 40:
اثیر فیلتر کردن ويژگي ها
# حد آستانه پائین ۶:10 کل تعداد مستندات
تعداد مستندات تعداد ويزكى ها es کاهش
مجموعه 10 بی فیلتر با فيلتر ویژگی ها
INN mut ۱۸3 ۱۸۰
YAY ۱3۹3 he 1۸۳
YAR Yast ۳:۳۶ vy.
, —————— NS
عينا ملكي- يهينه سازي كشف اطلاعات از مستندات نيمه ساختياقت HT AML
صفحه 41:
a Oo
قد ارزيابي روش وزن دهي ويژگي ۱,)9/۳6۴
أقآ 180 مستند ورودي
تا بدون فیلتر
دأ میانگین تعداد کلمات در هر برچسب و وزن برچسب
# عنوان: 5 ويژگي گوزن برچسب عنوان 2/0
۴ چکیده: 40 ویژگی > وزن برچسب چکیده 09/0
* کلمات کليدي: 11 ويژگي وزن برچسب کلمات كليدي 025/0"
۴ متن: 439 ويژگي گ وزن برچسب متن 002/0
۳77 ل
ih اس (poy aoa cea ue ریت
صفحه 42:
fl @
a ab ای ارييهاي انجام
LOVE ارزيابي روش وزن دهي ويژگي GI
* تعداد مستندات: 80.
۴ تعداد کل ويژگي ها:ژ
؟ بهترین مقدار ,مه
> :1 درصد
> :۱۸/۲ درصد
علو عتشييد
مينا ملكي- يهينه سازي كشف اطلاعات از مستندات نيمه ساختيافته .0861 TT I
صفحه 43:
fl @
لابج ارزيابي هاي انجام شده مس
2 ارزیابی روش وزن دهی ویژگی ۱,۳6۴
ae ee سس[
oh —letee belie beg gg ی aaa
a SD سس بان هش
مينا ملكي- يهينه سازي كشف اطلاعات از مستندات نيمه ساختيافته .0861 NT
صفحه 44:
TF
SD
0861. مينا ملكي- يهيته سازي كشف اطلاعات از مستددات نيمه ساختيافته
یت
ارزیابی روش وزن دهی ویژگی ۱,۳۵۴
صفحه 45:
* تعداد مستندات: 20
* تعداد ویژگی:16434
۴ :
> 73/0 يه ازاي 8000 ويژگي
:Gparck ©
> 7670 به ازاي 2000 ويژگي
Micro Average F,
4
‘a 5000 10000 ۰ 15088 ۰ ۰ 20000 ۰۰ ۵
سم of Features
مينا ملكي- يهيته سازي كشف اطلاعات از مستددات نيمه ساختيافته .0861
ae ie)
صفحه 46:
> 0 به ازاي 2000 ويژگي
TPCRE ©
> 933 /0 به ازاي 4000 ويژگي
10000 15000 2000 ۹
Number of Features
TERE
هد norm FIDE
هو سوت
سب[
عه
0
0۳0
Micro Average F,
SD اراد سس بان هشیر
مينا ملكي- يهيته سازي كشف اطلاعات از مستددات نيمه ساختيافته .0861 مسد وموم he
صفحه 47:
49
202000 تعداد مستندات بر روى روش st Sl
معبارهای
101
TFRF
we
مانگین
ماكرو
A
sare
saree
۳-1
bite | Sie مانگن
مكرو | ميكرو | ماكز | ميكرو
»م | ۲ | | me
sa an
و | | carer | arse | arr
حصي | حي | var [eases | حم
مياتكين | مبانگین a
میکرو | ماکرو میکرو
مام Re
ادليه | لمحي | دحي | تحني | كريد
sae | حب | vas [vas [sve
یی | ومقي. | جمد | حير | ند
مينا ملكي- يهينه سازي كشف اطلاعات از مستندات نيمه ساختيافته .0861
arr
۳
wr
aan
arene
صفحه 48:
ان تاثیر فیلتر کردن ويژگي ها بر روش ۳6۳066۴"
معیارهای
تعداه کر اوزیابی
مجیوعه 2
AB set
ل
ak
A
ve
با فیلتر
sar
“ay
vary
۹۹
۳
“ae
۳
۲
sar
aoe
sar
لحل
sar
۳
sar
sara
any
aye
ary
av any
yaar,
۸۳
rare
yan
صفحه 49:
fl @
بهبود كارايي طبقهبندي کننده مستندات نیمه ساختیافته 160 (حدود 5 الي 9
درصد) با بکار گيري روش وزن دهي ويژگي ۲
عت طبقفزندی کتنذه نیمه ساختیافته(0 در رسیدن به
يي با بكارگيري روش وزن دهي ويژگي ۵
Gl بهبود کارايي طبقهبندي کننده مستندات (حدود 5 درصد) با بكارگيري روش وزن
دهي ويزگي ۳00
Gl عدم وابسته بودن کارايی روش طبقهبندي کننده مستندات مبتني بر 00۹6 با
۱ Gl
تعداد مستندات ورودي
9489 افزایش سرعت محاسباتي با کاهش تعداد ويژگي ها (83 در 360 مستند و Gl
در 720 مستند) >کاهش ناچیز کارايي طبقهبندي کننده مستندات مبتني بر
)004/0 (حدود 0۴
آزمایشگا سيستع هاي موشمند
مينا ملكي- يهيته سازي كشف اطلاعات از مستددات نيمه ساختيافته .0861 سس
صفحه 50:
fl @
(ax sass
أذ ارائه روش جديدي براي طبقهبندي مستندات نیمه ساختيافته :20
دا طراحي و پیاده سازي چارچوبي جهت ارزيلبي اجزاء مختلف سیستم طبقهبندي کننده
مستندات نیمه ساختيافته
GI طراحي و پیاده سازي يك تحلیلگر لغوي ساختاري براي شاخص بندي کردن مستندات
نیمه ساختيافته با حفظ اطلاعات ساختاري ويژگيهاي تشکیل دهنده آنها
I ارائه روش جديدي براي وزن دهي برچسب ها و ان اهمیت هر يك از اجزاء
رائه روشي جدید براي وزن دهي ويژگيهاي مستتقات نیمه ساختیافته براساس
موقعیت ويژگي ()
أن اائه روش جدید براي وزن دهي ويژگي براساس اطلاعات طبقات (00)
اد بكارگيري روش وزن دهي ويژگي اسمح۵ در حوزه طبقهبندي مستندات
اتنا ارائه ليست كاملي از كلمات توقف + ايده جدید به منظور دستيابي به بهینه ترین لیست
كلمات توقف
آزمایشگا سيستع هاي موشمند
مينا ملكي- يهيته سازي كشف اطلاعات از مستددات نيمه ساختيافته .0861 — Oh
صفحه 51:
fl @
eat lst تاد
ال بهبود نحوه وزن دهی اجزاء مستندات نیمه ساختیافته
انآ ترکیب روش هاي وزن دهي ويژگي
ارائه روش جديدي براي انتخاب ويژگي از مستندات نیمه ساختيافته
استفاده از (0:76) براي تولید برداري از ويژگيهاي مفهومي
آزمایشگا سيستع هاي موشمند
مينا ملكي- يهينه سازي كشف اطلاعات از مستندات نيمه ساختيافته .0861 TT
صفحه 52:
fl
[Bl 1. ete, Dakar Lewrany OeBran Ud, Dow York, 8, C89.
[Bl تمسق 0: tere, Okra Formas Reread, OO reer, Oru York 1, 488.
,اف Dar Ora: Orenge wal Teakeanes, Darya aon مامت :0 بسا لا
[Bl ©, ©. Greens. Gov, Orbe be herent br Orr Probdety Ober al herder sheet, Dey, GOO.
[SI 0.0. rey, Carvey oP Pe سم لعج رفس بسا رد0 Spring bbe, 0
وزن دهي ويژگي 5
Spe," oad عم دا تسوا نع یاه( ی( بویت عیسو( ت۳۳ یله بل تسا 6۰ و
۵000 0۵۵06۸ وی 06 ,06 ای رس سا ما خی
| Vem Dk UY bh, CA. Xe, Omegrasin Chow Crate Drab م Dont
Camortnan” Oh om rate Orb Ornf mew, Deane, Oey Dyed OPAPP, COD.
[Bl ban, 027. een LW. Lew, OL, Pay, © Onaprrcare One on Perr Dehn Ochre Por Pee مه میسن ۵۵
ند مالس لسع مها Oecd Deterker (AIO), یر 2006۵0 006
Bl نس 1.0. Oye, (0 One ای و0 سامت هو تم hapa ‘erent ye, vk OW.
4 pp. 0109, C09.
عينا ملكي- يهينه سازي كشف اطلاعات از مستندات نيمه ساختياقت TT I AML
صفحه 53:
fl
ا As عقي" يارد لاح يون حبك الصوويه بويا سل LEE EEO Ya Ug SPER بودي تون مني
رمد اکن ge موز فرط دق tia espa
أ .يعاس يوه لداعت پل بان از يکي کار ین نم pA هرمز دنا دتم یکی 135
٩۵ pruned Lygerted Oceeprinan Orton Dot beh cl hereweendy Orne Oho نصا 0:۷ بت باق با نهآ
‘Abormar’OOrd DOO ‘heyaared Odorewe vu Ccewth wal Onebpwed ws bora Gere (OWGARDD), pp.
Oho, 6, CODD ,20-270
Gl ©. Oke, 0. Gory, ©. Dogys, ©, Crarceh, CherPans of UND Drovers by ikiee Tree Date مه
AODONDI, py. 670-099, 080, OOD
TBI. ony. Gham; B. Oks, “B rn of Opyromches “Layee Octeprintan” ened of “hark “الل
10, 6/۵ بو 0000۵ 6
[Bl ©. Onte, ©. Clye, “0 Grey ot Oiprowher & Orursretee Drove سا مایا مجع خسان 1115406-00,
برش هپس سوه ۵ dent Ort سل هه 00
|
ان 00۵0 یس ,0۵ اس مومس لت مسق
ع پم “Pernt ممعت مهن س0 لعن دس Por سعط للع مله" حبنت .© [Bl ©. Orde,
0
بايان نامه كارشناسي
طبقه بندي مستندات
احم ما من (DI. Sem, bis, “@ ReKBanonnto of Pet Ocrnprizatra Ortent,” GCod BOD ‘tersntead OrPerrane
1869 ,0005 ,طساب 3 Berean SABRE), gy: POPS, مهس انس مومت
نا ,0 ام سس پمهمسس0 060 "همست Gl ©. Gobwtad, “Dookie Leas bs Ohtani! eat
e008.
oS
مينا ملكي- يهينه سازي كشف اطلاعات از مستندات نيمه ساختيافته .0861 TT
(
صفحه 54:
fl @
Sale SD
1. M. Maleki, A. Abdollahzadeh, "A New Location-based Feature Weighting
Method for Categorization of Semi-structured Documents," accepted in the
31st Annual Conference of the German Classification Society on Data Analysis,
Machine Learning, and Applications (GFKL 2007), March 2007, Freiburg i.
Br., Germany.
2, M. Maleki, A. Abdollahzadeh, "TFCRF: A Novel Feature Weighting Method
Based on Class Information in Text Categorization (revised version),"
accepted in the 31st Annual Conference of the German Classification Society
on Data Analysis, Machine Learning, and Applications (GFKL 2007), March
2007, Freiburg i. Br., Germany.
3. M. Maleki, A, Abdollahzadeh, "TFCRF: A Novel Feature Weighting Method
Based on Class Information in Text Categorization,” accepted in the 19th
international conference on Computer, Information and Systems Science and
Engineering, (ICKM 2007), 29-31 January 2007, Bangkok, Thailand.
4 م. ملکي. | عبدالله زاده. "1۳018 روش جدید وزن دهي ويژگي مبتني بر اطلاعات کلاس در حوزة طبقه بندي
مستندات "» پذیرفته شده در دوازدهمین کنفیانس انجمن مهندسي کامپیوتر ایران 2007 05706
1-3 اسقند 1385 دانشکده برق و کمپیوتردانشگاه شهید بهشتي, تهران: یران
آزمایشگا سيستع هاي موشمند
مينا ملكي- يهيته سازي كشف اطلاعات از مستددات نيمه ساختيافته .0861 Oh
صفحه 55:
صفحه 56:
١ يكو
"برش وباس
تن
دانشکده مهندسي کامپيوتر
و فناوري اطالعات
دانشگاه صنعتي امير كبير
دفاعيه پايان نامه كارشناسي ارشد
بهينه سازي كشف اطالعات از مستندات نيمهساختيافته XML
Optimizing Information Discovery
from Semi-Structured XML Documents
دانشجو
مينا ملكي
استاد راهنما
دكتر احمد عبداللهزاده بارفروش
1بهمن 1385
عناوين اصلي
ضرورت انجام پژوهش
هدف پژوهش
طبقه بندي مستندات
روش هاي وزن دهي ويژگي
روش وزن دهي ويژگي پيشنهادي TFCRF
روش وزن دهي ويژگي پيشنهادي LBTF
سيستم طبقه بندي كننده مستندات نيمه ساختيافته XML
مشخصات بستر آزمايشگاهي پياده سازي شده
نتايج ارزيابيهاي انجام شده
نتيجه گيري ،دستاوردهاي پروژه ،پيشنهاد كارهاي آينده
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
3
ضرورت انجام پژوهش
مستندات وب
ساختيافته ؟
مستندات نيمه ساختيافته XML
بازيابي+جستجو +فهم و يادگيري +ارزيابي +استخراج اطالعات...+
كشف خودكار اطالعات ازمستندات نيمه ساختيافته XML
دانشهاي جديد ،الگوها،
کشف خودكار
ارتباطات در مجموعه وسيعي از مستندات
خالصه سازي
متن كاوي
طبقه بندي
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
خوشه بندي
...
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
4
هدف پژوهش
بهبود كارايي طبقه بندي كننده
بهبود كشف اطالعات از مستندات نيمه ساختيافته XML
سازماندهي مستندا@ت
تشخيص موضوع مستندات
بندي كننده جهت
راستايطبقIه
كارايIي
بهبود
راهكاري بIه
عاليق كاربر
مستندات در
منظوركردن
ساختيافته و پيدا
ارائIه جستجوي
شاخص بندي خودكار مستندات در سيستمهاي بازيابي اطالعات
ساختيافتهها XML
اطالعات از
كردنكشف
فرايند
نيمه مراتبي از پوشه
مستندات سلسله
الكترونيكي يا فايلها در
بالدرنگ نامه هاي
بهبودمرتب
تشخيص معناي کلمات مبهم
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
5
طبقه بندي مستندات
طبقهبندي مس@تندات = انتس@اب اس@ناد متن@ي بر اس@اس محتوي ب@ه ي@ك ي@ا چن@د طبقIه از
قبل تعيين شده
ماتريس
تصميم گيري
فازهاي طبقه بندي
}D {d1, d2,...,dn
}C {c1,c2,...,cm
1 d j ci
aij
0 d j ci
فاز آموزشيساخت مدل با استفاده از مستندات آموزشي
فار آزمايشي استفاده از مدل بر روي مستندات آزمايشي
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
6
مراحل طبقه بندي مستندات
پيش پردازش مستندات
شاخص بندي مستندات
تبديل مستندات به برداري از كلمات تشكيل دهنده
انتخاب ويژگي
كاهش ابعاد بردار كلمات
وزن دهي ويژگي
آستانه يابي تكرار مستندات ()DF
بهره اطالعاتي ()IG
روش هاي مبتني بر TF
قدرت ويژگي ()TS
روش 2
روش هاي مبتني بر IDF
تعيين ميزان اهميت و قدرت كلمات انتخاب شده در متمايز كردن هر مستند از ساير مستندات
طبقه بندي مستندات
اعم@ال الگوريتم طبقه بندي بر روي بردار
كلم@ات انتخاب و وزن دهي شده مستندات
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
طبقه بندي كننده هاي بيزين
نزديكترين Kهمسايه ()KNN
درخت هاي تصميم گيري
شبكه هاي عصبي
ماشين هاي بردارهاي پشتيبان ()SVM
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
7
راهكار بهبود كارايي طبقه بندي كننده
ارائه الگوريتم جديد
طبقه بندي كننده مستندات
بهبود عمليات پيش پردازش
1960
الگوهاي آماري رخداد كلمات
Luhn
1986
سيستم هاي خبره
Humphery
1988
درخت هاي تصميم گيري
Biebricherو ه@مكارا@ن
1992
روش KNN
Creecyو ه@مكارا@ن
1994
الگوريتم Rocchio
Hull
1994
طبقه بندي كننده بيزين
Lewisو ه@مكارا@ن
1996
روش رگرسيون LLSF
Yangو Chute
1996
شبكه هاي عصبي
Rumelhart
1998
SVM
Joachims
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
8
راه حل پيشنهادي
بهبود روش وزن دهي ويژگي براي باالبردن كارايي طبقه بندي كننده
مستندات نيمه ساختيافته XML
متن كاوي
استخراج اطالعات
پرسش و پاسخ
طبقه بندي مستندات
پيش پردازش
شاخص بندي
انتخاب ويژگي
خالصه سازي
خوشه بندي
الگوريتم
طبقه بندي
وIزن دهي ويژگي
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
9
روش هاي وزن دهي ويژگي
وزن دهي ويژگي
)di (w1i ,...,wki
di Dاگر
:kت@@عداد و@يژگ@يهايم@تمايز در ك@لم@جموعة D
:wikوز@ند@هيو@يژگ@ي tkدر م@ستند di
روش هاي متداول وزن دهي ويژگي
روشهاي مبتني بر TF
تابعي از توزيع ويژگي در هر يك از مستندات
روشهاي مبتني بر IDF
تابعي از توزيع ويژگي در مجموعه مستندات D
di D
روش هاي مبتني بر اطالعات طبقات
تابعي از توزيع ويژگي در طبقات
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
10
روش وزن دهي ويژگي مبتني بر TF
ايده :افزايش وزن دهي ويژگي با افزايش فركانس ويژگي در هر مستند.
توضيحات
رابطه
)tk’ di(#تعداد تكرار ويژگيtk
در مستند di
نام روش
of di
#(t , d ) tk vector
wki tf(tk, di ) k i
tk vector
of di
0
) tf (tk, di
k (tf(tk, di ))2
wki
TF
normTF
-
)) wki log(tf(tk , di
-
1
) 1 tf(tk , di
r=1
kت@@عداد و@يژگ@يهاي م@نحصر
pk D
ب@@ه ف@@رد) iدرtf (tk , d
م@جموعة
wki ITF(tk , di ) 1
wki Sparck
(tk , di ) tf (tk , di ) * k log pk
logTF
ITF
Sparck
D
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
11
روش هاي وزن دهي ويژگي مبتني بر IDF
ايده :كاهش وزن ويژگي با افزايش فركانس ويژگي در مجموعه مستندات .D
D
wki idf(tk , di ) log
) D(tk
IDF
) wki tfidf(tk , di ) tf(tk , di ) * idf(tk , di
TFIDF
) tfidf(tk , di
2
)) k (tfidf(tk , di
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
normTFIDF wki
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
12
روش وزن دهي ويژگي مبتني بر اطالعات طبقات
روش TFRF
سال 2005توسط آقاي Lan
D(tk , cj )
|rf (tk , cj ) log 2 |C
| D(tk , cm) |
m1,mj
) tf(tk, di ) * rf (tk,cd
i
k tf(tk,di ) 2 * (rf (tk,cdi ))2
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
wki TFRF(tk, di )
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
13
روش وزن دهي ويژگي پيشنهادي TFCRF
a
تعداد مستندات
متعاق به كالس c1
b
c
:aتعداد مستندات فاقد ويژگي xاز كالس c1
:bتعداد مستندات داراي ويژگي xاز كالس c1
تعداد مستندات
متعلق به كالس هاي غير c1
d
( )4
)(3
)(2
)(1
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
:cتعداد مستندات داراي ويژگي xاز كالس غير c1
:dتعداد مستندات فاقد ويژگي xاز كالس غير c1
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
14
روش وزن دهي ويژگي پيشنهادي
(TFCRFادامه)
روش هاي وزن دهي ويژگي مبتني بر IDF
a
تعداد مستندات
متعاق به كالس c1
b
c
تعداد مستندات
متعلق به كالس هاي
غير c1
d
((3 )4
)
(2
)
)(1
N
a b c d
idf(x) log
log
b c
b c
وزن xدر ( =)1وزن xدر ( = )2وزن xدر ( = )3وزن xدر ()4
روش TFRF
b
rf (x,c1) log 2
c
وزن xدر ( <)4وزن xدر ( < )3وزن xدر ( < )1وزن xدر ()2
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
15
روش وزن دهي ويژگي پيشنهادي
(TFCRFادامه)
a
تعداد مستندات
متعاق به كالس c1
b
c
تعداد مستندات
متعلق به كالس هاي غير c1
d
روش وزن دهي ويژگي TFRF
وزن ( xالف)= وزن ( xب) = وزن ( xج) = وزن ( xد)
روش وزن دهي ويژگي منطقي
وزن ( xالف) < وزن ( xب) < وزن ( xج) < وزن ( xد)
(الف)
)ب(
)ج(
)د(
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
16
)(ادامه
positiveRF
(tk,ci )
TFCRF روش وزن دهي ويژگي پيشنهادي
| D(tk,cj ) |
| D(cj ) |
|C|
| D(tk,cm) |
negativeRF
(tk,ci )
crfValue
(tk , ci )
positiveRF
(tk , cj)
negativeRF
(tk , cj )
m1,mj
|C|
| D(cm) |
m1,mj
wki TFCRF(tk , di )
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
17
log(tf(tk , di ) * crfValue
(tk , cdi ))
2
(tk , cdi )))
k (log(tf (tk , di ) * crfValue
XML بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته-مينا ملكي
روش وزن دهي ويژگي پيشنهادي LBTF
مثال :طبقه بندي مقاالت علمي برچسب گذاري شده XML
فركانس ويژگي xدر ”عنوان“ 1بار
2بار
”چكيده“
100بار
” متن“
روش وزن دهي ويژگي TF
=100+2+1=103وزن ويژگي x
روش وزن دهي ويژگي منطقي
وزن جزء متن*+100وزن جزء چكيده*+2وزن جزء عنوان* =1وزن ويژگي x
مساله :تعيين ميزان اهميت (وزن) اجزاء مستند نيمه ساختيافته
راه حل :1فرايند مكاشفه اي در تعيين ميزان اهميت هر جزء ( Giriسال )2004
راه حل :2طبقه بندي كننده متا ( Bratkoسال 2004و )2006
راه حل :3روش وزن دهي ويژگي LBTFپيشنهادي ( Malekiدر سال )2007
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
18
روش وزن دهي ويژگي پيشنهادي
( LBTFادامه)
ايده :وزن دهي ويژگي براساس اطالعات ساختاري مستندات نيمه ساختيافته XML
تكنيك :توجه به چگالي هر يك از اجزاء تشكيل دهنده مستند XML
مجموعه اجزاء موجود در مستندات XMLمجموعه D
E e1,...,ek
N
) lwf(ej ) 1/ #(tk , di ,ej
i1tkVocab
) wki LBTF(tk , di ) #(tk , di ,ej ) * lwf(ej
ej E
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
19
سيستم طبقه بندي كننده مستندات نيمه ساختيافته XML
واحد طIبقه بندي کننده
مستندات نيمه ساختيافته
طبقه بندي شده XML
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
واحد پيش پردازشگر
مستندات نيمه ساختيافته XML
مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
20
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
21
زيرسيستم پاالينده مستندات
وظيفه :دريافت و پااليش مجموعه مستندات XMLورودي جهت تعيين مجموعه D
ورودي :مستندات نيمه ساختيافته XML
خروجي :مستندات پااليش شده XMLبه عنوان مجموعه D
مولفه ها
حذف كننده برچسب هاي غير ضروري
بررسي كننده ساختار مستندات XML
انتخاب كننده مستندات XMLپااليش شده
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
حاوي اطالعات معنايي مهم نيستند.
در تعداد كمتري از مستندات مجموعه وجود دارند.
شناسايي و اصالح اجزاء غير خوش فرم
قابل تبديل به برچسب هاي ديگر هستند.
حذف اجزاء تهي
داراي بيشترين برچسب
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
22
زيرسيستم استخراج كننده ويژگي ها
وظيفه :پردازش مجموعه مستندات Dجهت استخراج ويژگي هاي مهم با حفظ
اطالعات ساختاري
ورودي :مجموعه مستندات D
خروجي :مجموعه مستندات Dشاخص بندي شده
مولفه ها
شاخص بندي مستندات و استخراج كلمات با حفظ اطالعات مكاني
تحليلگر لغوي ساختاري
حذف اعداد و عالئم نگارشي
سازنده پايگاه داده
پاالينده لغوي
يكسان سازي شكل حروف
حذف كلمات توقف ريشه يابي شده
ريشه يابي كلم@ات
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
23
زيرسيستم استخراج كننده ويژگي ها
(ادامه)
قالب مستندات شاخص بندي شده
اطالعات ويژگي
شناسه ويژگي
اطالعات
مستندات حاوي ويژگي
تعداد
تاكيد بر روي ويژگي
شناسه مستند
تعداد
تكرار ويژگي در مستند
اطالعات
برچسب هاي حاوي ويژگي
شناسه برچسب
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
تعداد
ظاهر شدن در جمله اول
تعداد
تكرار ويژگي در برچسب
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
24
زيرسيستم كاهنده ويژگي ها
وظيفه :كاهش ابعاد ويژگي هاي تشكيل دهنده مستندات و انتخاب بهترين آنها
ورودي :جداول پايگاه داده حاوي ويژگي هاي شاخص بندي شده ساختاري
خروجي :ليستي از ويژگي هاي انتخاب شده
مولفه ها
فيلتر كننده ويژگي ها
انتخاب كننده ويژگي
تعريف حد آستانه پائين و باال
حذف ويژگي هاي نادراشكال امالئي يا ذهن خالق نويسنده (!)
حذف ويژگي هاي وافر كلمه توقف حذف نشده
شناسايي و حذف ويژگي هاي داراي بار معنايي پائينتر از ساير
ويژگي ها
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
25
زيرسيستم وزن دهي ويژگي
وظيفه :تعيين ميزان اهميت هر يك از ويژگي هاي مستند در متمايز كردن آن
مستند از ساير مستندات
ورودي :برداري از ويژگIي هاي انتخاب شده بIه همراه اطالعات شاخIص بندي
مكاني آنها
خروجي :بردار ويژگي هاي وزن دهي شده
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
26
مشخصات بستر آزمايشگاهي پياده سازي شده
پياده سازي در چارچوب Net.به زبان برنامه نويسي #Cبا بيش از 6500خط كد
مستندات ورودي inex
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
27
مجموعه مستندات inex
شام@ل 12107مقال@ه علم@ي از 18مجل@ه انتشارات انجم@ن كامپيوت@ر IEEEاز سال
1995تا 2002به فرمت XML
تاريخچه
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
28
مجموعه مستندات inex
شام@ل 12107مقال@ه علم@ي از 18مجل@ه انتشارات انجم@ن كامپيوت@ر IEEEاز سال
1995تا 2002به فرمت XML
تاريخچه
برچسب هاي مستندات inex
برچسب هاي پايه
حفظ برچسب ابتدا/انتها و محتويات
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
29
مجموعه مستندات inex
شام@ل 12107مقال@ه علم@ي از 18مجل@ه انتشارات انجم@ن كامپيوت@ر IEEEاز سال
1995تا 2002به فرمت XML
تاريخچه
برچسب هاي مستندات inex
برچسب هاي پايه
برچسب هاي حذف شدني
حذف برچسب ابتدا/انتها و محتويات
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
30
مجموعه مستندات inex
شام@ل 12107مقال@ه علم@ي از 18مجل@ه انتشارات انجم@ن كامپيوت@ر IEEEاز سال
1995تا 2002به فرمت XML
تاريخچه :دانشگاه Duisburgآلمان
برچسب هاي مستندات inex
برچسب هاي پايه
برچسب هاي حذف شدني
برچسب هاي تبديل شدني
تبديل برچسب ابتدا /انتها مبدا به مقصد
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
31
مجموعه مستندات inex
شام@ل 12107مقال@ه علم@ي از 18مجل@ه انتشارات انجم@ن كامپيوت@ر IEEEاز سال
1995تا 2002به فرمت XML
تاريخچه
برچسب هاي مستندات inex
برچسب هاي پايه
برچسب هاي حذف شدني
برچسب هاي تبديل شدني
برچسب هاي ساختاري
حذف برچسب ابتدا /انتها
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
32
مجموعه مستندات inexmodified
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
33
مشخصات بستر آزمايشگاهي پياده سازي شده
پياده سازي در چارچوب Net.به زبان برنامه نويسي #Cبا بيش از 6500خط كد
مستندات ورودي inex
الگوريتم طبقه بندي كننده SVM
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
34
الگوريتم طبقه بندي كننده SVM
هدف:
پيدا کردن تمام صفحات 1, 2,...
در فضاي rبعدي که نمونههاي مثب@ت و
منفي را با بيشترين حاشيه از هم جدا كنند.
مزاياي :SVM
حاشيه كوچك
بهترين الگوريتم طبقه بندي مستندات
قابليت كار با تعداد ويژگي هاي زياد
عدم تاثير تعداد ويژگي بر كارايي الگوريتم
پايداري
پياده سازي توسط LIBSVM
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
حاشيه بزرگ
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
35
مشخصات بستر آزمايشگاهي پياده سازي شده
پياده سازي در چارچوب Net.به زبان برنامه نويسي #Cبا بيش از 6500خط كد
مستندات ورودي inex
الگوريتم طبقه بندي كننده SVM
روش انتخاب ويژگيآستانه يابي فركانس مستندات ()DF
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
36
انتخاب ويژگي DF
دليل انتخاب
سادگي
هزينه محاسباتي پائين
دقت و كارايي معادل بهترين روش هاي انتخاب ويژگي نظير IG
مناسب در حوزه طبقه بندي مستندات
ايده :ظاه@ر شدن ويژگ@ي در تعداد مس@تندات بيشت@ر باال بودن ارزش معناي@ي ويژگي
جهت تفكيك طبقات از يكديگر (بعد از حذف كلمات توقف)
راهكار :شمارش تعداد مستندات داراي ويژگي
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
37
مشخصات بستر آزمايشگاهي پياده سازي شده
پياده سازي در چارچوب Net.به زبان برنامه نويسي #Cحدود ....خط كد
مستندات ورودي inex
الگوريتم طبقه بندي كننده SVM
روش انتخاب ويژگي DF
روشهاي وزن ده@ي
LBTF
ويژگ@يمبتن@ي بر + TFمبتني برIDF + TFRF + TFCRF +
تقسيم بندي مستندات به نسبت 3/2آموزشي و 3/1آزمايشي
تعداد كلمات توقف بعد از تكميل 1392كلمه 1079كلمه توقف ريشه يابي شده
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
38
معيارهاي ارزيابي
Ac(cj )
Pr(c j )
Re(c j )
TP(cj ) TN(cj )
TP(c j ) FP(c j ) TN(cj ) FN(cj )
TP(c j )
TP(c j ) FP(c j )
TP(c j )
TP(c j ) FN(c j )
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
39
XML بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته-مينا ملكي
نتايج ارزيابيهاي انجام شده
تاثير فيلتر كردن ويژگي ها
حد آستانه پائين %10كل تعداد مستندات
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
40
نتايج ارزيابيهاي انجام شده
(ادامه)
ارزيابي روش وزن دهي ويژگي LBTF
180مستند ورودي
بدون فيلتر
ميانگين تعداد كلمات در هر برچسب و وزن برچسب
عنوان 5 :ويژگي وزن برچسب عنوان 2/0
نتيجه منطقي
چكيده 40 :ويژگي وزن برچسب چكيده 09/0
كلمات كليدي 11 :ويژگي وزن برچسب كلمات كليدي 025/0
متن 439 :ويژگي وزن برچسب متن 002/0
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
41
نتايج ارزيابيهاي انجام شده
(ادامه)
ارزيابي روش وزن دهي ويژگي LBTF
تعداد مستندات180 :
تعداد كل ويژگي ها10816:
بهترين مقدار Accuracy
TF: 46 در%صد
LBTF: 55 در%صد
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
42
نتايج ارزيابيهاي انجام شده
(ادامه)
ارزيابي روش وزن دهي ويژگي LBTF
LBTF
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
43
نتايج ارزيابيهاي انجام شده
(ادامه)
ارزيابي روش وزن دهي ويژگي LBTF
TF
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
44
نتايج ارزيابيهاي انجام شده
(ادامه)
ارزيابي روش وزن دهي ويژگيTFCRF
تعداد مستندات720 :
تعداد ويژگي26434:
:TF
73/0 به ازاي 8000ويژگي
: Sparck
767/0 به ازاي 2000ويژگي
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
45
نتايج ارزيابيهاي انجام شده
(ادامه)
ارزيابي روش وزن دهي ويژگيTFCRF
TFRF
883/0 به ازاي 2000ويژگي
TFCRF
0/ 933 به ازاي 4000ويژگي
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
46
نتايج ارزيابيهاي انجام شده
(ادامه)
تاثير تعداد مستندات بر روي روش TFCRF
TFCRF
TFRF
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
47
نتايج ارزيابيهاي انجام شده
(ادامه)
تاثير فيلتر كردن ويژگي ها بر روش TFCRF
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
48
نتيجه گيري
بهبود كاراي@@ي طبقهبندي كننده مس@@تندات نيم@@ه س@@اختيافته( XMLحدود 5ال@@ي 9
درصد) با بكارگيري روش وزن دهي ويژگي LBTF
افزاي@ش س@رعت طبقهبندي كننده مس@تندات نيم@ه س@اختيافته XMLدر رس@يدن به
بيشترين حد كارايي با بكارگيري روش وزن دهي ويژگي LBTF
بهبود كاراي@ي طبقهبندي كننده مس@تندات (حدود 5درص@د) ب@ا بكارگيري روش وزن
دهي ويژگي TFCRF
عدم وابس@ته بودن كاراي@ي روش طبقهبندي كننده مس@تندات مبتن@ي بر TFCRFب@ا
تغيير تعداد مستندات ورودي
افزاي@ش س@رعت محاس@باتي ب@ا كاه@ش تعداد ويژگ@ي ه@ا ( %83در 360مس@تند و %89
در 720مس@تند) كاه@ش ناچي@ز كاراي@ي طبقهبندي كننده مس@تندات مبتن@ي بر
( TFCRFحدود )004/0
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
49
دستاوردهاي پروژه
ارائه روش جديدي براي طبقهبندي مستندات نيمه ساختيافته XML
طراح@ي و پياده س@ازي چارچوبIي جهIت ارزيابIي اجزاء مختلIف سيستم طبقهبندي كننده
مستندات نيمه ساختيافته
طراح@ي و پياده سIازي يIك تحليلگIر لغوي سIاختاري براي شاخ@ص بندي كردن مستندات
نيمه ساختيافته با حفظ اطالعات ساختاري ويژگيهاي تشكيل دهنده آنها
ارائه روش جديدي براي وزن دهي برچسب ها و تعيين ميزان اهميت هر يك از اجزاء
ارائ@ه روش@ي جدي@د براي وزن دهIي ويژگيهاي مسIتندات نيمIه سIاختيافته براساس
موقعيت ويژگي ()LBTF
ارائه روش جديد براي وزن دهي ويژگي براساس اطالعات طبقات ()TFCRF
بكارگيري روش وزن دهي ويژگي Sparckدر حوزه طبقهبندي مستندات
ارائ@ه ليسIت كاملIي از كلمات توقIف +ايده جدي@د ب@ه منظور دس@تيابي ب@ه بهين@ه تري@ن ليست
كلمات توقف
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
50
پيشنهاد كارهاي آينده
بهبود نحوه وزن دهي اجزاء مستندات نيمه ساختيافته
تركيب روش هاي وزن دهي ويژگي
ارائه روش جديدي براي انتخاب ويژگي از مستندات نيمه ساختيافته
استفاده از WordNetبراي توليد برداري از ويژگيهاي مفهومي
برچسب گذاري مستندات فارسي
طبقهبندي مستندات فارسي
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
51
مراجع
كتاب
T. Mitchell, Machine Learning, McGraw Hill, New York, US, 1999.
R. Baeza, N. Ribeiro, Modern Information Retrieval, ACM press, New York, US, 1999.
J. Han, M. Kamber, Data Minig: Concepts and Techniques, Morgan Kaufman Publisher, 2001.
P. Baldi, P. Frasconi, P. Smyth, Modeling the Internet and the Web-Probabilistic Methods and Algorithms,chapter4, Wiley, 2003.
M. W. Berry, Survey of Text Mining, Clustering, Classification, and Retreival, Springer Publisher, 2004.
وزن دهي ويژگي
E. Leopold, J. Kindermann, “Text Categorization with Support Vector Machines. How to Represent Texts in Input Space?,” Journal
of Machine Learning, vol. 46, no. 1-3, pp. 423-444, 2002.
Z.H. Deng, S.W. Tang, D.Q. Yang, M.Z.h. Li-Yu Li, K.Q. Xie, “A Comparative Study on Feature Weight in Text
Categorization,” 6th Asia Pacific Web Conference, Hangzhou, China, April 14-17, 2004.
M. Lan, S.Y. Sung, H.B. Low, .C.L. Tan, “A Comparative Study on Term Weighting Schemes for Text Categorization,” IEEE
International Conference on Neural Networks (IJCNN05), pp. 546-551, 2005.
J. Zhang, T.N. Nguyen, “A New Term Significance Weighting Approach,” Journal of Intelligent Information System, vol. 24. no.
1, pp. 61-85, 2005.
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
52
XML بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته-مينا ملكي
مراجع
طبقه بندي مستندات نيمه ساختيافته
پايان نام@ه كارشناسي،"" رويکردي ن@و در کاوش شبک@ة گس@تردة جهان@ي ب@ا هدف س@اخت ي@ک دروازة وب براي دس@تيابي ب@ه مجموع@ة طبقهبندي شدهاي از اطالعات، ص@في خان@ي.ژ
.1384 ، دانشگاه صنعتي اميركبير، دانشكده مهندسي كامپيوتر و فناوري ارتباطات،ارشد
.1385 ، دانشگاه صنعتي اميركبير، دانشكده رياضي و علوم کامپيوتر،" پايان نامه كارشناسي ارشد، "ساخت پرتال با استفاده از تکنيکهاي وبکاوي، مرادي دولت آبادي.پ
.H.J. Oh, S.H. Myaeng, M.H. Lee, “A practical Hypertext Categorization Method Using Links and Incrementally Available Class
Information,”23rd ACM International Conference on Research and Development in Information Retrieval (SIGIR00), pp.
264-271, Athens, GR, 2000.
M. Diligenti, M. Gori, M. Maggini, F. Scarselli, “Classification of HTML Documents by Hidden Tree Markov Models,”
ICDAR01, pp. 849-853, USA, 2001.
Y. Yang, S. Slattery, R. Chani, “A Study of Approaches to Hypertext Categorization,” Journal of Intelligent Information Systems,
vol. 18, no. 2/3, pp. 219-241, 2002.
A. Bratko, B. Filipic, “A Study of Approaches to Semi-structured Document Classification,” Technical Report IJS-DP-9015,
Department of Intelligent Systems, Jozef Stefan Institute, November 2004.
L. Denoyer and P. Gallinari, “Baysian Network Model for Semi-Structured Document Classification,” Journal of Information
Processing and Management, vol. 40, no. 5, pp. 807-827, 2004.
A. Bratko, B. Filipic, “Exploiting Structural Information for Semi-structured Document Categorization,” Information Processing &
Management, vol. 42/3, pp. 679-694, Elsevier, 2006.
طبقه بندي مستندات
Y. Yang, X. Liu, “A Re-Examination of Text Categorization Methods,” 22nd ACM International Conference on Research and
Development in Information Retrieval(SIGIR-99), pp. 42–49, Berkeley, US, 1999.
F. Sebastiani, “Machine Learning in Automated Text Categorization,” ACM Computing Surveys, vol. 34, no. 1, pp. 1–47,
2002.
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
53
XML بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته-مينا ملكي
مقاالت مستخرج از پروژه
1.
M. Maleki, A. Abdollahzadeh, "A New Location-based Feature Weighting
Method for Categorization of Semi-structured Documents," accepted in the
31st Annual Conference of the German Classification Society on Data Analysis,
Machine Learning, and Applications (GFKL 2007), March 2007, Freiburg i.
Br., Germany.
2.
M. Maleki, A. Abdollahzadeh, "TFCRF: A Novel Feature Weighting Method
Based on Class Information in Text Categorization (revised version),"
accepted in the 31st Annual Conference of the German Classification Society
on Data Analysis, Machine Learning, and Applications (GFKL 2007), March
2007, Freiburg i. Br., Germany.
3.
M. Maleki, A. Abdollahzadeh, "TFCRF: A Novel Feature Weighting Method
Based on Class Information in Text Categorization," accepted in the 19th
international conference on Computer, Information and Systems Science and
Engineering, (ICKM 2007), 29-31 January 2007, Bangkok, Thailand.
روش جدي@د وزن ده@ي ويژگ@ي مبتن@ي بر اطالعات كالس در حوزة طبقه بندي:TFCRF” ، عبدالل@ه زاده. ا،يI ملك.م
،)CSICC 2007( ه شده در دوازدهمي@ن كنفر@ان@س انجم@ن مهندس@ي كامپيوت@ر ايرانI پذيرفت،“مس@تندات
. ايران، تهران، دانشکده برق و کامپيوتر دانشگاه شهيد بهشتي،1385 اسفند1-3
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
54
XML بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته-مينا ملكي
.4
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
55
مينا ملكي -بهينه سازي كشف اطالعات از مستندات نيمه ساختيافته XML
آزمايشگاه سيستم هاي هوشمند
http://ce.aut.ac.ir/ISLAB
56