Метод оцінки подібності веб-сторінок
Наведено метод оцінювання Інтернет-сторінок та їх алгоритм очищення від інформаційного шуму; запропоновано алгоритм видалення веб-сторінок з даними, що дублюються....
Saved in:
| Published in: | Оптико-електронні інформаційно-енергетичні технології |
|---|---|
| Date: | 2008 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут фізики напівпровідників імені В.Є. Лашкарьова НАН України
2008
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/32180 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Метод оцінки подібності веб-сторінок / В.М. Дубовой, О.Ю. Краковецький, О.В. Глонь // Оптико-електронні інформаційно-енергетичні технології. — 2008. — № 2 (16). — С. 63-66. — Бібліогр.: 8 назв. — укp. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-32180 |
|---|---|
| record_format |
dspace |
| spelling |
Дубовой, В.М. Краковецький, О.Ю. Глонь, О.В. 2012-04-13T21:52:58Z 2012-04-13T21:52:58Z 2008 Метод оцінки подібності веб-сторінок / В.М. Дубовой, О.Ю. Краковецький, О.В. Глонь // Оптико-електронні інформаційно-енергетичні технології. — 2008. — № 2 (16). — С. 63-66. — Бібліогр.: 8 назв. — укp. 1681-7893 https://nasplib.isofts.kiev.ua/handle/123456789/32180 681.3.06 Наведено метод оцінювання Інтернет-сторінок та їх алгоритм очищення від інформаційного шуму; запропоновано алгоритм видалення веб-сторінок з даними, що дублюються. uk Інститут фізики напівпровідників імені В.Є. Лашкарьова НАН України Оптико-електронні інформаційно-енергетичні технології Методи та системи оптико-електронної і цифрової обробки зображень та сигналів Метод оцінки подібності веб-сторінок Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Метод оцінки подібності веб-сторінок |
| spellingShingle |
Метод оцінки подібності веб-сторінок Дубовой, В.М. Краковецький, О.Ю. Глонь, О.В. Методи та системи оптико-електронної і цифрової обробки зображень та сигналів |
| title_short |
Метод оцінки подібності веб-сторінок |
| title_full |
Метод оцінки подібності веб-сторінок |
| title_fullStr |
Метод оцінки подібності веб-сторінок |
| title_full_unstemmed |
Метод оцінки подібності веб-сторінок |
| title_sort |
метод оцінки подібності веб-сторінок |
| author |
Дубовой, В.М. Краковецький, О.Ю. Глонь, О.В. |
| author_facet |
Дубовой, В.М. Краковецький, О.Ю. Глонь, О.В. |
| topic |
Методи та системи оптико-електронної і цифрової обробки зображень та сигналів |
| topic_facet |
Методи та системи оптико-електронної і цифрової обробки зображень та сигналів |
| publishDate |
2008 |
| language |
Ukrainian |
| container_title |
Оптико-електронні інформаційно-енергетичні технології |
| publisher |
Інститут фізики напівпровідників імені В.Є. Лашкарьова НАН України |
| format |
Article |
| description |
Наведено метод оцінювання Інтернет-сторінок та їх алгоритм очищення від інформаційного шуму; запропоновано алгоритм видалення веб-сторінок з даними, що дублюються.
|
| issn |
1681-7893 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/32180 |
| citation_txt |
Метод оцінки подібності веб-сторінок / В.М. Дубовой, О.Ю. Краковецький, О.В. Глонь // Оптико-електронні інформаційно-енергетичні технології. — 2008. — № 2 (16). — С. 63-66. — Бібліогр.: 8 назв. — укp. |
| work_keys_str_mv |
AT dubovoivm metodocínkipodíbnostívebstorínok AT krakovecʹkiioû metodocínkipodíbnostívebstorínok AT glonʹov metodocínkipodíbnostívebstorínok |
| first_indexed |
2025-11-26T00:17:27Z |
| last_indexed |
2025-11-26T00:17:27Z |
| _version_ |
1850597075891257344 |
| fulltext |
5
УДК 681.3.06
В.М. ДУБОВОЙ, О.Ю. КРАКОВЕЦЬКИЙ, О.В. ГЛОНЬ
МЕТОД ОЦІНКИ ПОДІБНОСТІ ВЕБ-СТОРІНОК
Вінницький національний технічний університет,
вул. Хмельницьке шосе, 95, м Вінниця, Україна, 21021,
тел.: +380 (432) 43-78-96, E-mail: dub@faksu.vstu.vinnica.ua
Аннотація. Наведено метод оцінювання Інтернет-сторінок, та їх алгоритм очищення від інформаційного
шуму, а також запропоновано алгоритм видалення веб-сторінок з даними, що дублюються.
Аннотация. Приведен метод оценивания Интернет-страниц, и их алгоритм очищения от информационного
шума, а также предложен алгоритм удаления веб-страниц с данными, которые дублируются.
Ключові слова: подібність веб-сторінок, с-means, VIPS, критерій Пірсона
2χ , кластеризація веб-сторінок.
ВСТУП
Проблема вибору необхідного і, головне, корисного матеріалу в Інтернеті серед безлічі
документів є досить актуальною. Пошукові системи використовують різноманітні коефіцієнти (Google –
PageRank [1, 2], Яндекс – ТІЦ [2] тощо) для сортування результатів пошуку. Таким чином, «розкручені»
сайти будуть завжди знаходитися на вершині списку, хоча дуже часто частина цих сайтів містить
ідентичну інформацію, що призводить до втрачання часу користувачами на «візуальне» фільтрування
результатів пошуку. Наприклад для пошукового запиту «Иллюстрированный самоучитель по MathCAD
12» [3] з перших 10 ресурсів 5 мали ідентичну інформацію в тій чи іншій мірі. Таким чином, користувач
втрачає до 50% часу для перегляду даних ресурсів. Потрібно зазначити, що інформація на цих сайтів
дублюється не в повній мірі, а лише основна її частина (контент), все інше - дизайн, посилання, рекламні
блоки відрізняються. Таким чином актуальними задачами є визначення основного контенту сторінок та
оцінка їх подібності.
ОГЛЯД ЛІТЕРАТУРИ
Поняття подібності веб-сторінок в літературі безпосередньо не розглядається. Натомість існує
ряд робіт, присвячених задачам кластеризації текстової інформації [4-6], що оперують поняттям
«відстанні» між об’єктами, що по своїй суті схоже з поняттям подібності. Для обчислення відстані
використовують міри Ейлера, Меланхобіса, критерій Пірсона тощо. Наприклад, відстань можна
знаходити за допомогою критерію
2χ Пірсона
,
1
2
1 2
,2
1
,1
,2,1
21
2 ∑
=
−
+
=
k
i
ii
ii n
m
n
m
mm
nnχ (1)
де 1n - об’єм першого тексту, 2n - об’єм другого тексту, im ,1 - частота i -ї ознаку в першому
тексті, im ,2 - частота i -ї ознаки в другому тексті [7]. Значення jim , (матриця подібності) обчислюється
як кількість входжень i -ї ознаки в j -у документі: )( ,, jjiji pfcountm ∈= . Відповідно, коефіцієнт
подібності можна обчислювати як
2
, /1
2
χ=ppi
S .
Даний підхід має ряд недоліків: значення відстанні може відрізнятися для однакового степеня
дублювання даних за рахунок різної довжини текстів, значення відстанні достатньо великі навіть для
невеликих текстів, тобто необхідно вводити понижаючі коефіцієнти і, накінець, основний недолік в тому,
©
В.М. ДУБОВОЙ, О.Ю. КРАКОВЕЦЬКИЙ, О.В. ГЛОНЬ, 2008
ПРИНЦИПОВІ КОНЦЕПЦІЇ ТА СТРУКТУРУВАННЯ РІЗНИХ РІВНІВ ОСВІТИ З ОПТИКО-ЕЛЕКТРОННИХ ІНФОРМАЦІЙНО-
ЕНЕРГЕТИЧНИХ ТЕХНОЛОГІЙ
6
що отримане значення відстані (і відповідно й подібності) неможливо оцінити експертним шляхом, тобто
визначити чи отримана відстань є великою чи малою. Для оцінки експерним шляхом необхідно мати
повну матрицю відстаней.
АКТУАЛЬНІСТЬ ТА МЕТА РОБОТИ
Велика кількість даних та технологій «розкрутки» сайтів призводить до необхідності розробки
методів та алгоритмів фільтрації результатів пошуку з метою покращення ефективності пошуку в
Інтернеті.
Метою даної роботи є вирішення задачі очищення веб-сторінок від інформаційного шуму та
розробка методу оцінки подібності веб-сторінок.
ОЧИЩЕННЯ ВЕБ-СТОРІНОК ВІД ІНФОРМАЦІЙНОГО ШУМУ
Алгоритм виділення основного контенту зі сторінки полягає в наступному:
1. На вхід подається веб-сторінка, яка ділиться на окремі
інформаційні блоки.
2. На основі регресійної моделі оцінки важливості інформаційних
блоків сайтів.
F = 1.739 + 0.033·ImgsNum - 0.062·ImgsAsLinksNum + 0.087·ImgsAsLinksRatio + 0.002·LinksNum –
0.006·WordsAsLinksNum + 0.291·WordsAsLinksRatio + 0.012·SentNum + 1.523·SentAvgLengthRatio –
0.005·WordsInSentsNum + 1.75·WordsInSentsRatio – 0.164·StopWordsNum – 8.22· StopWordsRatio +
0.004·WordsNum – 0.003·ListItemsNum – 0.002·HeadersNum – 0.14·ControlsNum – 0.456·MediaObjectsNum
+ 3.712·ContentRatio + 0.849·WordsAsListsRatio + 0.105·FontSize + 0.002·FontWeight,
для кожного блоку розраховуються числові значення важливості.
3. За допомогою нечіткого методу кластеризації с-means [6] (на
основі числових значень оцінки важливості) блоки діляться на три
кластери (відповідно до трьохрівневої системи оцінки
важливості).
4. На виході отримуємо сторінку, до якої входять лише ті блоки, які
були ідентифіковані як важливі.
Розглянемо роботу алгоритму на реальному прикладі. В якості тестової сторінки було взято
статтю інформаційного агенства CNN [8]. Вона була розбита на інформаційні блоки, а кожен з блоків був
оцінений за допомогою регресійної моделі. В результаті отримано 7 блоків, які були кластеризовані за
допомогою нечіткого методу кластеризації с-means. Результати наведено в таблиці 1.
Таблиця 1.
Результати нечіткої кластеризації
№
блоку
№
класт.
4 5 7 1 3 2 6
I 0.0449 0.0133 0.0881 0.3291 0.9963 0.9844 0.0000
II 0.0059 0.0015 0.0056 0.0139 0.0005 0.0033 1.0000
III 0.9492 0.9852 0.9063 0.6569 0.0032 0.0122 0.0000
В таблиці 2 наведено порівняння кластеризованих результатів і результатів, отриманих за
допомогою експерта (1 – інформація неважлива, 2 – мало важлива, 3 – основний контент).
Таблиця 2.
Порівняння результатів оцінки важливості блоків
ПРИНЦИПОВІ КОНЦЕПЦІЇ ТА СТРУКТУРУВАННЯ РІЗНИХ РІВНІВ ОСВІТИ З ОПТИКО-ЕЛЕКТРОННИХ ІНФОРМАЦІЙНО-
ЕНЕРГЕТИЧНИХ ТЕХНОЛОГІЙ
7
№ Оцінка за регресійною моделю Експ. оцінка Кластер.
оцінка
1 7.88679307143625 1 1
2 13.5747065165397 2 2
3 38.154141209372 3 3
4 1.1426199376947 1 1
5 2.44260051472691 1 1
6 15.1783915874052 2 2
7 6.23407392941833 1 1
Таким чином, на основі результатів можна побачити, що запропонований алгоритм успішно
справляється з поставленою задачею.
МЕТОД ОЦІНКИ ПОДІБНОСТІ ВЕБ-СТОРІНОК
Під подібністю веб-сторінок будемо розуміти степінь дублювання даних, що вони містять
.),( 2121 datadatapagepageSimilarity ∪= (2)
Під коефіцієнтом подібності будемо розуміти числову характеристику подібності, причому
повному дублюванню даних буде відповідати значення 1, відповідно 0 – документам, що повністю
відрізняються.
Нехай 1p і 2p - дві веб-сторінки, для яких необхідно визначити їх подібність, 1f і 2f - набір
унікальних ознак відповідних веб-сторінок. Під унікальними ознаками матимемо на увазі набір ознак, що не
повторюються в межах однієї веб-сторінки. В якості таких ознак будемо використовувати елементи
інформаційного наповнення, а саме слова, речення, посилання та графічний контент (в принципі, використання
інших елементів також допустиме). Загальний набір ознак F (2) утворюється шляхом об’єднання набору ознак
веб-сторінок, що порівнюються. Ознаки, що повторюються, також видаляються з набору
)()()(, 2121 fcountfcountFcountffF +≤∪= (3)
Коефіцієнт дублювання даних i -ї веб-сторінки в j -й будемо обчислювати за допомогою
наступного виразу
)(
)()()(
)(
i
ji
pp
fcount
Fcountfcountfcount
ji
−+
=δ (4)
Загальний коефіцієнт даних, що дублюється в веб-сторінках 1p і 2p будемо
обчислювати за допомогою виразу
)()(
)()()(
,
ji
ji
pp
fcountfcount
Fcountfcountfcount
ji +
−+
=δ , (5)
а коефіцієнт подібності відповідно як
].1,0[,2 ,,, ∈= jipppp SS
jiji
δ (6)
Відповідно відстань між веб-сторінками може бути обчислена за допомогою виразу
ПРИНЦИПОВІ КОНЦЕПЦІЇ ТА СТРУКТУРУВАННЯ РІЗНИХ РІВНІВ ОСВІТИ З ОПТИКО-ЕЛЕКТРОННИХ ІНФОРМАЦІЙНО-
ЕНЕРГЕТИЧНИХ ТЕХНОЛОГІЙ
8
ji
ji
pp
pp
S
D
,
,
1
= (7)
Таким чином, коефіцієнт подібності враховує невідповідність розмірів веб-сторінок та їх
величини, а відстань між сторінками є певним чином обмеженою, так як коефіцієнт подібності може
змінюватися лише в діапазоні від 0 до 1. Таким чином вирішується проблема розмірності відстані і
подібності.
АЛГОРИТМ ВИДАЛЕННЯ ВЕБ-СТОРІНОК З ДАНИМИ, ЩО ДУБЛЮЮТЬСЯ
Даний алгоритм може використовуватися для фільтрування результатів веб-пошуку будь-якої
пошукової системи.
Параметри алгоритму:
- кількість сторінок результатів пошуку n , що необхідно
проаналізувати (зазвичай використовуються результати, що
знаходяться на перших двох сторінках результатів пошуку, тому
оптимальним є значення 15-20 ресурсів);
- максимальний допустимий коефіцієнт подібності maxS , при якому
сторінка вважаться такою, що дублюються і не включається в
рузультуючий набір;
- метод видалення сторінок: inline, коли сторінки можуть
видалятися при першому знайденому недопустимому дублюванні
чи postprocessed, коли спочатку аналізуються всі сторінки, і лише
потім приймаються рішення про видалення тієї чи іншої сторінки.
Принцип видалення веб-сторінки з результуючого набору:
>
.
,)()(
otherwisep
ifp
j
ppppi ijji
δδ
Покроковий опис алгоритму:
1. Користувач вводить пошуковий запит, пошукова система видає
результати – набір сторінок P .
2. Аналізуються перші n веб-сторінок: вони розбиваються на блоки,
оціюються за допомогою регресійної моделі, інформаційний шум
«відсікається». На виході отримуємо n веб-сторінок, які
складаються лише з основного контенту.
3. Обчислюються коефіцієнти подібності між сторінками. Всі
сторінки, що дублюються, видаляються з результуючого набору (в
залежності від методу видалення сторінок).
4. На виході отримуємо набір сторінок, інформація в яких не
дублюється.
ВИСНОВКИ
В даній роботі запропоновано алгоритм очищення веб-сторінок від інформаційного шуму,
запропоновано метод оцінки подібності веб-сторінок та алгоритм видалення веб-сторінок з даними, що
дублюються. Розроблені метод та алгоритми можуть бути реалізовані як надбудова до сучасних
рішень і ефективно використовуватися в пошукових системах.
Подальша робота над покращенням розроблених методів та алгоритмів буде проводитися в
ПРИНЦИПОВІ КОНЦЕПЦІЇ ТА СТРУКТУРУВАННЯ РІЗНИХ РІВНІВ ОСВІТИ З ОПТИКО-ЕЛЕКТРОННИХ ІНФОРМАЦІЙНО-
ЕНЕРГЕТИЧНИХ ТЕХНОЛОГІЙ
9
таких напрямках:
1. Аналіз додаткових ознак веб-сторінок для обчислення подібності
та відстані.
2. Реалізація багатопотокового аналізу для зменшення часу аналізу.
3. Розробка методу автоматичного визначення максимально
допустимого коефіцієнта подібності maxS для конкретного
пошукового запиту.
СПИСОК ЛІТЕРАТУРИ
Стаття в Вікіпедії про PageRank // Режим доступу: http://ru.wikipedia.org/wiki/PageRank.
1. Что такое тИЦ? Что такое PR? // Режим доступу: http://fogmaker.net/post_1192898532.html.
2. Результати пошуку «Иллюстрированный самоучитель по MathCAD 12» в Google // Режим
доступу:http://www.google.com.ua/search?hl=ru&q=Иллюстрированный+самоучитель+по+MathC
AD+12&btnG=Поиск&meta=.
3. Дюк В. А., Самойленко А. П. Data Mining: учебный курс. - СПб.: Питер, 2001. – 368 c.
4. Барсегян А. А. Методы и модели анализа данных: OLAP И Data Mining. - СПб.: BHV, 2004. – 336 с.
5. Чубукова И. А. Data Mining. БИНОМ. Лаборатория знаний, Интернет-университет
информационных технологий - ИНТУИТ.ру. – 2006. – Режим доступу:
http://www.intuit.ru/department/database/datamining/. – Заголовок з екрану.
6. Бормашов Дмитрий Александрович. Кластерный анализ текстов // Томск: Томск. гос. ун-т.
Факультет информатики, 2006.- 43 с.
7. Стаття інформаційного агенства CNN // Режим доступу:
http://edition.cnn.com/2008/WORLD/weather/09/06/hurricane.ike/index.html.
Надійшла до редакції 05.10.2008р.
ДУБОВОЙ ВОЛОДИМИР МИХАЙЛОВИЧ, д.т.н, професор – завідувач кафедри
комп’ютерних систем управління Вінницького національного технічного університету.
КРАКОВЕЦЬКИЙ ОЛЕКСАНДР ЮРІЙОВИЧ – аспірант кафедри комп’ютерних систем
управління Вінницького національного технічного університету.
ГЛОНЬ ОЛЬГА ВІТАЛІЇВНА – к.т.н., доцент кафедри комп’ютерних систем управління
Вінницького національного технічного університету.
|