Питання з інформатики

1. Поняття інформаційної технології.

ІТ - кошти, методи та системи збору, передачі, обробки та представлення інформації користувачеві.

Існують 4 етапи еволюції:

Поява мовлення;

Поява писемності;

Поява коштів Вт (Сучасні і тд .).

У сучасному ІТ виділяють 3 складові:

Апаратне забезпечення (кошти Вт та оргтехніки - hardware);

Програмне забезпечення (прикладне та системне ПЗ, методичне та інформаційне забезпечення - software);

Організаційне забезпечення (включаючи людину в системи ІТ, взаємодія людини з цими системами, системне використання технічних і програмних засобів - orgware)

ІТ = нові ІТ = сучасні ІТ.

Нові ІТ -- сучасна ІТ технологія, що використовує розвинений (інтелектуальний) інтерфейс з кінцевим користувачем.

ІТ як прикладна наука, що вивчає фундаментальні співвідношення у великих інформаційних системах.

ІТ як практика - Інтелектуальна діяльність з проектування і створення конкретних технологій обробки даних.

В ІТ виділяють 3 складові:

Базові ІТ. Забезпечують рішення окремих компонентів у тієї чи іншої задачі, служать для створення прикладних ІТ. Наприклад: технології програмування, СУБД, системи розпізнавання зображення і тд.

Прикладні ІТ. Формуються на основі базових інформаційних технологій, які призначені для повної інформатизації об'єкта. Наприклад: САПР, АСУП, геоінформаційні системи.

що забезпечують ІТ. Забезпечують реалізацію базових і прикладних ІТ. На ринку представлені їх окремі частини. Наприклад: сучасна мікроелектронна база коштів Вт, перспективні системи та комплекси (оптичні й еволюційний, трансп'ютерів).

3.Основні методи організації текстових файлів.

Цепочечние файли.

До самої БД додається довідник, який має наступну структуру:

Ключ - значуще слово, що характеризує той чи інший документ. Поруч пишеться адресна посилання на той текстовий файл, який має даний ключ як значимий терміну. І до цієї підрядку додаються власне текстові файли.

Цепочечная модель: скільки індексних термінів у тексті виділено стільки і має бути посилань.

Переваги:

Максимальна довжина пошуку визначається найдовшою ланцюжком;

Нові записи (тексти) можна ставити в початок ланцюга, що спрощує її коригування.

Недоліки:

Ланцюги можуть бути довгими, якщо деякі терміни використовуються досить часто;

Необхідність виділення пам'яті для зберігання адресних посилань у самих текстах;

Якщо довідник дуже великий, він значно ускладнює роботу з текстами і вимагає організації додаткового доступу до себе самого.

Питання 5 (закінчення).

терміну k. Якщо Sk зменшується, то k або взагалі не розглядається як можливий індекс, або йому присвоюється негативний вагу.

1.Параметри, засновані на динамічній ефективності. Всім термінів спочатку присвоюються однакову вагу, потім користувач формує запит, і видаються документи і користувач визначає релевантність, система сама зменшує або збільшує вагу документа, відповідно до потреб користувача, тобто передбачається певна програма навчання системи.

Ми розглянули статистичні підходи (СП). Крім СП використовуються такі підходи, які передбачають місце розташування терміну в тексті.

Підходи:

1. У індексаціонние терміни включаються ті, які зустрічаються в назвах документів, назвах розділів, розділів і т.д.

2. Складаються списки значущих для деякої предметної області слів. Тобто складається глосарій за деякою предметної області.

Методи збільшення повноти. Часто буває необхідно видати найбільше число релевантних документів з масиву. У цьому випадку необхідно до використовуваних індексаціонним термінів додати додаткові, щоб розширити область пошуку.

1-й підхід до вирішення цього завдання: використання термінів заступників зі словника синонімів, який називають тезаріусом, в якому терміни згруповані в класи.

2) Метод асоціативного індексування. Заснований на використанні матриці асоційованого термінів, яка задає для кожної пари термінів показник асоційованими. Абсолютна запис цього ПА між термінами j і k:

f (j; k) = сум (i = 1 - n) fij * fjk - частота спільного використання f (j; k) = сум (i = 1 - n) fij * fjk/(сум (i = 1 - n) fij ^ 2 + сум (i = 1 - n) fjk ^ 2 - сум (i = 1 - n) fij * fjk -- для розрахунку відносного значення цього показника. fij, k - частота появи терміну j або k в i - м документі. 0 <= f (j; k) <= 1. Якщо f (j; k) = 0, то терміни зовсім не асоціюються, якщо f (j; k) = 1, то повністю асоційованими.

6. Використання частотних заходів у індексуванні.

Частотний метод - По кожному терміну, що входить до документа підраховується частота входження термінів у документ fik, i - номер документа, k - термін. Ця частота абсолютна. Потім документи упорядковуються відповідно до зростання або зменшення частоти.

Якщо термін має більшу частоту, то це, швидше за все загальновживаний термін, не розкриває конкретну предметну область (буде багато документів).

Якщо термін має малу частоту, то він суттєво відображає зміст, навіть якщо його включити до дескриптори (ключові слова), то він, швидше за все буде використовуватися в холосту. Тому ці 2 найпростіших документа виключають з списку.

терміна з більшою частотою присвоюють меншу вагу, з меншою частотою - більшу вагу.

Інвертований файли.

Виходять з цепочечних файлів, коли в довідник включаються адресні посилання на всі тексти, які мають відповідний ключ як індексаціонного терміну.

Недолік: змінне число адрес в довіднику.

Гідність: швидкий пошук релевантних документів, так як їх адреси знаходяться відразу в довіднику, обробку якого можна організувати в оперативній пам'яті.

розосереджені файли.

Весь масив документів розбивається на групи файлів, ключові терміни яких пов'язані деяким математичним співвідношенням. Тоді пошук в довіднику замінюється обчислювальної процедури, яка називається хешування, рандомізації або перемішуванням. Тут немає довідника, а існує обчислювальна процедура, тобто блок, названий блоком рандомізації, який по ключу (пошуковому терміну) на підставі обчислювальної процедури визначає адресу, за якою знаходиться текст.

Ключ адреса цю ділянку

(ключ) пам'яті

називається

Бакет

У цій області пам'яті знаходиться кілька текстів, кожен з яких характеризується по своєму у векторі документів. Тобто адреса виходить з обчислювальної процедурою.

Переваги:

Швидкий обчислюваний доступ;

Через відсутності довідника економиться пам'ять.

Недоліки:

Складність при виборі методу хешування;

Застосовується для коротких векторів запитів, коли в пошуку бере участь трохи слів;

Зміни векторів документів породжує складність у веденні файлів.

Кластерні файли.

Документи розбиваються на родинні групи, які називають кластерами або класами. Кожен клас описується Центроїд (профілем) і вектор запиту перш за все порівнюється з Центроїд класу.

Переваги:

Можливий швидкий пошук, тому що число класів, як правило, невелика;

Можливо інтерактивне звуження (розширення) пошуку за рахунок виключення або додавання додаткових кластерів.

Недоліки:

Необхідність формувати кластери;

Необхідність введення файлу Центроїд;

Додатковий витрата пам'яті для файлу Центроїд або профілів.

4. Поняття Центроїд кластеру.

Безліч термінів складових векторів кластеру називаються Центроїд або репрезентативним кластерним профілем. Т.ч. кожен кластер характеризується центроідним вектором, який являє собою безліч пар: ((tik , Wik)), де tik - безліч термінів що описують i-й кластер, wik - Безліч ваг.

Вага - число, що визначає значимість даного терміну для розкриття змісту документа.

7. Розрахунок співвідношення "сигнал-шум" при індексуванні.

Використання співвідношення "сигнал - шум". Тут виключається ще одна частота: сумарна або загальна частота появи терміну k в наборі з n документів і розраховується:

Fk = сума (i = 1 - n) fik

Шум k-го символу розраховується:

Nk = сума (i = 1 - n) fik/Fk * log (Fk/fik)

Сигнал k - го символу:

Sk = log Fk - Nk

Шум є максимальним, якщо термін має рівномірний розподіл у n документах. Шум є мінімальним і рівномірним, коли термін має нерівномірний розподіл, наприклад, коли він зустрічається тільки в одному документі, з частотою Fk, тоді:

Nk = сума (i = 1 - n) fik/Fk * log Fk/fik = 0, в цьому випадку сигнал має максимальне значення:

Sk = log Fk - Nk = log Fk

З урахуванням цих параметрів, для визначення ваги використовується відношення сигналу до шуму k-го терміну: Sk/Nk. Чим більше це відношення, тим більший вага призначається. Будується однозначна таблиця.

8.Іспользованіе розподілу частоти терміна при індексуванні.

Використання розподілу частоти терміну (ухилення).

Ухилення розраховується:

U = (сум (fik - fk))/(n-1)

fk - середня частота терміна k в наборі з n документів.

fk = Fk/n

Для оцінки ваги терміна використовується не ухиляння, а формула Fk * U/fk

Чим більше це відношення, тим більшої ваги призначається терміну.

9.Іспользованіе при індексуванні параметрів, заснованих на здатності терміна розрізняти документи набору.

Вихідні дані - Набір з n документів і безліч S коефіцієнтів подібності всіх пар документів з безлічі n: (S (Di, Dj)). Ці коефіцієнти подібності розраховуються на підставі векторів документів. Спосіб розрахунку різний, а принцип: S (Di, Dj) = 1, якщо вектора ідентичні.

S (Di, Dj) = 0, якщо в векторах немає жодного загального документа.

За S розраховують середній коефіцієнт подоби: S = C * сум (i = 1 - n) S (Di, Dj), С - коефіцієнт усереднення, може бути будь-яким, зокрема C = 1/n.

Далі з векторів документів видаляють деякий k - й термін і розраховують середній коефіцієнт по парного подібності, але з віддаленою k-му терміном: Sk (тобто в векторах документа не беруть участь ваги k-го терміну). Якщо Sk зростає щодо S, то терміну k присвоюється позитивний вагу. Чим більше ця різниця, тим більшу вагу присвоюється терміну k. Якщо Sk зменшується, то k або взагалі не розглядається як можливий індекс, або йому присвоюється негативний вагу.

10.Дінаміческая інформативність як метод індексування.

Всім термінів спочатку присвоюються однакову вагу, потім користувач формує запит, і видаються документи і користувач визначає релевантність, система сама зменшує або збільшує вагу документа, відповідно до потреб користувача, тобто передбачається певна програма навчання системи.

5 Призначення та основні методи індексації.

Завдання створення вектора документа називається індексуванням.

Методи автоматичного індексування. Завдання цих методів - побудувати вектори документів ((tik, wik)). Вихідні дані - масив документів. Потрібно виділити ті терміни, які розкривають текст документа tik і привласнити вага wik.

Методи:

1. Частотний метод - по кожному терміну, що входить в документ підраховується частота входження термінів у документ fik, i - номер документа, k - термін. Ця частота абсолютна. Потім документи упорядковуються відповідно до зростання або зменшення частоти.

Якщо термін має більшу частоту, то це, швидше за все загальновживаний термін, не розкриває конкретну предметну область (буде багато документів).

Якщо термін має малу частоту, то він суттєво відображає зміст, навіть якщо його включити до дескриптори (ключові слова), то він, швидше за все буде використовуватися в холосту. Тому ці 2 найпростіших документа виключають з списку.

терміна з більшою частотою присвоюють меншу вагу, з меншою частотою - більшу вагу.

2. Використання співвідношення "сигнал - шум". Тут виключається ще одна частота: сумарна або загальна частота появи терміна k в наборі з n документів і розраховується:

Fk = сума (i = 1 - n) fik

Шум k-го символу розраховується:

Nk = сума (i = 1 - n) fik/Fk * log (Fk/fik)

Сигнал k - го символу:

Sk = log Fk - Nk

Шум є максимальним, якщо термін має рівномірний розподіл у n документах. Шум є мінімальним і рівномірним, коли термін має нерівномірний розподіл, наприклад, коли він зустрічається тільки в одному документі, з частотою Fk, тоді:

Nk = сума (i = 1 - n) fik/Fk * log Fk/fik = 0, в цьому випадку сигнал має максимальне значення:

Sk = log Fk - Nk = log Fk

З урахуванням цих параметрів, для визначення ваги використовується відношення сигналу до шуму k-го терміну:

Sk/Nk. Чим більше це відношення, тим більшу вагу

Призначається. Будується однозначна таблиця.

1.Використання розподілу частоти терміну (ухилення).

Ухилення розраховується:

U = (сум (fik - fk))/(n-1)

Fk - середня частота терміна k в наборі з n документів.

Fk = Fk/n

Для оцінки ваги терміна використовується не ухиляння, а формула Fk * U/fk

Чим більше це відношення, тим більшої ваги призначається терміну.

2.Параметри, засновані на здатності терміна розрізняти документи набору. Вихідні дані -- набір з n документів і безліч S коефіцієнтів подібності всіх пар документів з безлічі n: (S (Di, Dj)). Ці коефіцієнти подібності розраховуються на підставі векторів документів. Спосіб розрахунку різний, а принцип: S (Di, Dj) = 1, якщо вектора ідентичні.

S (Di, Dj) = 0, якщо в векторах немає жодного загального документа.

За S розраховують середній коефіцієнт подібності: S = C * сум (i = 1 - n) S (Di, Dj), С - коефіцієнт усереднення, може бути будь-яким, зокрема C = 1/n.

Далі з векторів документів видаляють деякий k - й термін і розраховують середній коефіцієнт по парного подібності, але з віддаленою k-му терміном: Sk (тобто в векторах документа не беруть участь ваги k-го терміну). Якщо Sk зростає щодо S, то терміну k присвоюється позитивний вагу. Чим більше ця різниця, тим більшу вагу присвоюється

11.Методи індексування, засновані на становищі терміну в тексті.

Підходи:

1.В індексаціонние терміни включаються ті, які зустрічаються в назвах документів, назвах розділів, розділів і т.д.

2.Составляются списки значущих для деякої предметної області слів. Тобто складається глосарій за деякою предметної області.

3.Методи збільшення повноти. Часто буває необхідно видати найбільше число релевантних документів з масиву. У цьому випадку необхідно до використовуваних індексаціонним термінів додати додаткові, щоб розширити область пошуку.

1) 1-й підхід до вирішення цього завдання: використання термінів заступників зі словника синонімів, який називають тезаріусом, в якому терміни згруповані в класи.

2) Метод асоціативного індексування. Заснований на використанні матриці асоційованого термінів, яка задає для кожної пари термінів показник асоційованими. Абсолютна запис цього ПА між термінами j і k:

f (j; k) = Сум (i = 1 - N) fij * fjk - частота спільного використання f (j; k) = сум (i = 1 - n) fij * fjk/(сум (i = 1 - n) fij ^ 2 + сум (i = 1 - n) fjk ^ 2 - сум (i = 1 - n) fij * fjk -- для розрахунку відносного значення цього показника. fij, k - частота появи терміну j або k в i - м документі. 0 <= f (j; k) <= 1. Якщо f (j; k) = 0, то терміни зовсім не асоціюються, якщо f (j; k) = 1, то повністю асоційованими.

12.Постановка завдання збільшення повноти при пошуку в текстовій базі даних і основні методи її вирішення.

Методи збільшення повноти. Часто буває необхідно видати найбільше число релевантних документів з масиву. У цьому випадку необхідно до використовуваних Индексаціонним термінів додати додаткові, щоб розширити область пошуку.

1) 1-й підхід до вирішення цього завдання: використання термінів заступників зі словника синонімів, який називають тезаріусом, в якому терміни згруповані в класи.

2) Метод асоціативного індексування. Заснований на використанні матриці асоційованого термінів, яка задає для кожної пари термінів показник асоційованими. Абсолютна запис цього ПА між термінами j і k:

f (j; k) = сум (i = 1 - n) fij * fjk - частота спільного використання f (j; k) = сум (i = 1 - n) fij * fjk/(сум (i = 1 - n) fij ^ 2 + сум (i = 1 - n) fjk ^ 2 - сум (i = 1 - n) fij * fjk -- для розрахунку відносного значення цього показника. fij, k - частота появи терміну j або k в i - м документі. 0 <= f (j; k) <= 1.

Якщо f (j; k) = 0, то терміни зовсім не асоціюються, якщо f (j; k) = 1, то повністю асоційованими.

Другий спосіб: використовуються матриці для розширення пошуку: вводиться деяке граничне значення коефіцієнта асоційованого (СКА), вище якого коефіцієнти прирівнюються до одиниці, а нижче до 0.

13.Метод асоціативного індексування в задачі збільшення повноти пошуку.

Заснований на використанні матриці асоційованого термінів, яка задає для кожної пари термінів показник асоційованими. Абсолютна запис цього ПА між термінами j і k:

f (j; k) = сум (i = 1 - n) fij * fjk - частота спільного використання f (j; k) = сум (i = 1 - n) fij * fjk/(сум (i = 1 - n) fij ^ 2 + сум (i = 1 - n) fjk ^ 2 - сум (i = 1 - n) fij * fjk -- для розрахунку відносного значення цього показника. fij, k - частота появи терміну j або k в i - м документі. 0 <= f (j; k) <= 1.

Якщо f (j; k) = 0, то терміни зовсім не асоціюються, якщо f (j; k) = 1, то повністю асоційованими.

Другий спосіб: використовуються матриці для розширення пошуку: вводиться деяке граничне значення коефіцієнта асоційованого (СКА), вище якого коефіцієнти прирівнюються до одиниці, а нижче до 0.

14.Метод імовірнісного індексування в задачі збільшення повноти пошуку.

Суть: наявність у документі деяких термінів Т1, Т2, ..., Тi дозволяє з певною вірогідністю Р віднести ці документи до класу документів Ск і привласнити вектору документів ідентифікатор цього класу, тобто додатковий термін. Причому зазначена ймовірність Р для цього "приписування" повинна бути більше деякого порогового значення.

Імовірність Р записується: Р (Т1, Т2, ..., Тi, Ск) - імовірність того, що за наявності термінів Тi, документ буде належати класу Ск. Р (Т1, Т2, Тi, Ск) = а * р (Ск) * р (Т1, Ск) * (Т2, Ск) * ... * (Тi, Ск)

Коефіцієнт а підбирається таким чином, щоб виконувалася умова: сума (к = 1, m) Р (Т1, Т2, ..., Тi, Ск) = 1 - тобто щоб виконувалася повна група подій. Документ, який містить термін Т1, Т2, ..., Тi обов'язково повинен належати одному з класів Ск.

m -- число видів документів нашого масиву.

Р (Ск) - Імовірність класу Ск. Ця ймовірність розраховується як частота, в чисельнику - число документів, що знаходяться в класі Ск, в знаменнику - загальна кількість документів у всіх m класах.

Р (Тj, Ск) - дріб, у чисельнику -- загальне число появи терміну Тj в документах класу Ск, в знаменнику - загальне число появи всіх термінів у документах класу Ск.

15.Постановка завдання підвищення точності пошуку в текстовій базі даних і основні методи її рішення.

Задача - як можна точніше отримувати потрібні документи.

2 способи:

а). Використання найбільш вузьких термінів.

б). Використання словосполучень для індексування документів. Для визначення словосполучень використовуються статистичний і лінгвістичний підходи.

Статистичний підхід (СП):

Відповідно з СП словосполучення - така комбінація термінів, частота появи спільного яких в масивах документів велика щодо частот появи окремих термінів цього словосполучення. Зв'язність термінів визначається коефіцієнтом зв'язності:

Сik = Fkj/(Fk * Fj) * N - це зв'язність 2-х термінів, хоча може бути і більше (до 4-х).

Fk, Fj - приватні частоти термінів k і j. Питання 15 (закінчення).

Fkj - частота появи спільного термінів.

N -- кількість слів у масиві.

Після розрахунку цих значень і коефіцієнта зв'язності (КС) у словосполученні відбирають такі терміни, для яких Сjк і Fkj більше порогового значення, яке встановлюється емпірично. Граничні значення: Сjк > = 20 та Fkj> = 3.

Якщо ці характеристики для термів, включених до словосполучення підтримуються, то виходять гарні вибірки.

Недолік:

не враховується порядок слів у словосполученнях;

метод дозволяє вважати ідентичними навіть словосполучення з однаковим порядком проходження терміна.

Лінгвістичні методи - використовують спрощені синтаксичні розбори пропозицій, причому, як правило, пропозицій з заголовків текстів.

Алгоритм аналізу спрощених фраз:

Утворюються предводітельние словосполучення шляхом проставлення дужок перед приводами, числівниками, невизначеними займенниками і т.д.

Встановлюються зв'язку праворуч та/або ліворуч від слів, виділених у першому пункті між різними структурами.

Зі структури виключаються кількісні числівники, допоміжні дієслова, займенники і т.д. Залишаються лише індексаціонние словосполучення. У результаті повинні залишитися зв'язку або комбінації види: сущ. - Ім. (прил. - прил .).

Приклад: (Some investigations) (in computer science) (which can lead) (to the creation) (of artificial intelligence). У результаті маємо:

Computer science -> investigations -> artificial intelligence -> creation.

16.Статістіческій метод освіти словосполучень в задачі підвищення точності пошуку в текстовій базі даних.

Відповідно з СП словосполучення - така комбінація термінів, частота появи спільного яких в масивах документів велика щодо частот появи окремих термінів цього словосполучення. Зв'язність термінів визначається коефіцієнтом зв'язності:

Сik = Fkj/(Fk * Fj) * N - це зв'язність 2-х термінів, хоча може бути і більше (до 4-х).

Fk, Fj - приватні частоти термінів k і j.

Fkj - частота появи спільного термінів.

N -- кількість слів у масиві.

Після розрахунку цих значень і коефіцієнта зв'язності (КС) у словосполученні відбирають такі терміни, для яких Сjк і Fkj більше порогового значення, яке встановлюється емпірично. Граничні значення: Сjк > = 20 та Fkj> = 3.

Якщо ці характеристики для термів, включених до словосполучення підтримуються, то виходять гарні вибірки.

Недолік:

не враховується порядок слів у словосполученнях;

метод дозволяє вважати ідентичними навіть словосполучення з однаковим порядком проходження терміна.

17.Лінгвістіческій метод освіти словосполучень в задачі підвищення точності пошуку в текстовій базі даних.

Лінгвістичні методи - використовують спрощені синтаксичні розбори пропозицій, причому, як правило, пропозицій з заголовків текстів.

Алгоритм аналізу спрощених фраз:

Утворюються попередні словосполучення шляхом проставлення дужок перед приводами, числівниками, невизначеними займенниками і т.д.

Встановлюються зв'язку праворуч та/або ліворуч від слів, виділених у першому пункті між різними структурами.

Зі структури виключаються кількісні числівники, допоміжні дієслова, займенники і т.д. Залишаються лише індексаціонние словосполучення. У результаті повинні залишитися зв'язку або комбінації види: сущ. - Ім. (прил. - прил .).

Приклад: (Some investigations) (in computer science) (which can lead) (to the creation) (of artificial intelligence). У результаті маємо:

Computer science -> investigations -> artificial intelligence -> creation.

18.Задача автоматичного реферування текстів і методи її вирішення.

Завдання створення рефератов - завдання виявлення списку документів та короткий його подання.

Вихідні дані:

масив вихідних даних;

готові вектора документів (тобто вже повинна бути вирішена задача створення векторів (tik, wik }).

Методи для автореферірованія:

Розрахунковий -- визначаються ваги словосполучень, що містять 2 значущих терміну з вектора документа.

w = 1/2t * wi1 * wi2 - вага словосполучення з 2-х термінів.

wi1 і w i2 - ваги 1-го і 2-го терміну з вектора.

t -- кількість слів у тексті між термінами ti1 і t i2, які не є значимими.

Далі по тексту визначається значуще пропозицію. Це така пропозиція, яка містить велике число значущих груп. Після розрахунку значущості пропозицій, вони упорядковуються і для реферування вибираються найбільш значущі. Далі найбільш значущі пропозиції упорядковуються так, як вони йшли в тексті, щоб не втратити логіку.

Позиційний метод. Включає в себе наступні НЕ альтернативні кроки:

Найбільш значущі пропозиції, які або починають, або закінчують абзац або розділ.

Виключаються питальні речення, незважаючи на їхнє положення в абзаці.

До значущим відносяться пропозиції, що містять слова - підказки. Наприклад: "дана (слово-підказка) робота виконана по такому - то плану і т.д. "

З значущих виключаються ті пропозиції, в яких є посилання на малюнки, таблиці, цитати і т.д.

19.Цепочечние текстові файли.

До самої БД додається довідник, який має наступну структуру:

Ключ - значуще слово, що характеризує той чи інший документ. Поруч пишеться адресна посилання на той текстовий файл, який має даний ключ як значимий терміну. І до цієї підрядку додаються власне текстові файли.

Цепочечная модель: скільки індексних термінів у тексті виділено стільки і має бути посилань.

Переваги:

Максимальна довжина пошуку визначається найдовшою ланцюжком;

Нові записи (тексти) можна ставити в початок ланцюга, що спрощує її коригування.

Недоліки:

Ланцюги можуть бути довгими, якщо деякі терміни використовуються досить часто;

Необхідність виділення пам'яті для зберігання адресних посилань у самих текстах;

Якщо довідник дуже великий, він значно ускладнює роботу з текстами і вимагає організації додаткового доступу до себе самого.

20.Інвертірованние текстові файли.

Виходять з цепочечних файлів, коли в довідник включаються адресні посилання на всі тексти, які мають відповідний ключ як індексаціонного терміну.

Недолік: змінне число адрес в довіднику.

Гідність: швидкий пошук релевантних документів, так як їх адреси знаходяться відразу в довіднику, обробку якого можна організувати в оперативній пам'яті.

21.Рассредоточенние текстові файли.

Весь масив документів розбивається на групи файлів, ключові терміни яких пов'язані деяким математичним співвідношенням. Тоді пошук в довіднику замінюється обчислювальної процедури, яка називається хешування, рандомізації або перемішуванням.

Тут немає довідника, а існує обчислювальна процедура, тобто блок, названий блоком рандомізації, який по ключу (пошуковий термін) на підставі обчислювальної процедури визначає адресу, за якою знаходиться текст.

Ключ адреса цю ділянку

(ключ) пам'яті

називається

Бакет

У цій області пам'яті знаходиться кілька текстів, кожен з яких характеризується по своєму у векторі документів. Тобто адреса виходить з обчислювальної процедурою.

Переваги:

Швидкий обчислюваний доступ;

Через відсутності довідника економиться пам'ять.

Недоліки:

Складність при виборі методу хешування;

Застосовується для коротких векторів запитів, коли в пошуку бере участь трохи слів;

Зміни векторів документів породжує складність у веденні файлів.

Питання 27 (закінчення).

4. Корекція кластерів зверху вниз.

На початку будуються один або кілька дуже великих кластерів, які потім розбиваються на більш дрібні.

Способи вибору початкових класів:

Як центрів класів використовуються випадкові документи;

Класом з ім'ям i можна вважати безліч документів, у векторах яких знаходиться термін i;

Як початкових класів приймаються всі документи, визнані доречними деякого запиту за результатами попередніх пошукових операцій.

Процес корекції кластерів:

Обчислюється КП між кожним документом і кожним Центроїд кластеру;

Кластери перевизначаються шляхом віднесення документів до тих з них, по відношенню до яким, вони мають найбільшу подібність;

Формуються Центроїд нових кластерів.

Ці 3 кроки виконуються до тих пір, поки:

Буде необхідність у змінах;

Щоб процес не був нескінченним, він виконується в задане число ітерацій.

5.Однократная кластеризація.

Документи розглядаються в довільному порядку і кожен документ або відноситься до існуючого класу, якщо КП достатній, або утворює новий кластер.

"+": кожен документ обробляється тільки 1 раз, => потребує мало часу.

"-": склад і структура класів суттєво залежить від порядку розгляду документів.

28. Знаходження КЛИК.

Кліка - такий вид кластеру, в якому кожен документ подібний до будь-якого іншого документу. Кліка формується тоді, коли виникає повний граф, тобто повне співвідношення подібності між всіма елементами.

А В

З Д

Вихідними даними для методу є матриця подібності документа масиву, яка заповнюється коефіцієнтами подібності всіх пар документів.

Матриця: S (Di, Dj) - діагональна квадратна і симетрична.

i = 1, N; j = 1, N.

Нехай задано безліч пар:

VDi = ((ti, wi))

VDj = ((tj, wj))

Коефіцієнт подібності документів визначається:

S (Di, Dj) = сум (k = 1, N) rk/N

r -- ставлення; N -- потужність безлічі документів.

0, wi = 0 або wj = 0

rk = wi/wj інакше

Щоб завдання вирішувалася адекватно, вектора (*) повинні бути впорядковані за термінами, тобто одні і ті ж терміни повинні бути записані в одних і тих самих позиціях цих векторів. Вихідна матриця, яка отримана в результаті розрахунків, перетвориться в бінарну наступним чином: вводиться деяке граничне значення T коефіцієнта подібності, і ті коефіцієнти, які менше його замінюються на 0, в іншому випадку на 1:

S (Di, Dj) 0

S (Di, Dj)> T, => 1

Алгоритм:

1.В клас чи кластер включаються підгрупи порядку 2, тобто ті елементи, які стосовно подібності встановлені на парі.

2.Із підгрупи порядку 2 отримують підгрупу порядку 3 за таким правилом: якщо є підгрупи (Di, Dj), (Di, Dp), (Dj, Dp), то отримуємо: (Di, Dj, Dp) і підгрупи з початкового списку виключаються.

3.Із підгрупи порядку p формують підгрупу порядку (p +1), тобто (Di, Dj, ..., Dp) => (Di, Dj, ...,

Питання 33 (продовження).

Послідовність.

Ця властивість гарантує, що користувач, що освоїв роботу в однієї частини системи не заплутається, працюючи в іншій її частині.

виражено у 3-х явища:

Послідовність в побудові фраз. Тобто вводяться коди або команди в системі завжди трактуються однаково;

Послідовність у використанні форматів даних - аналогічні поля завжди представляються в одному форматі (суперечить вимозі гнучкості);

Послідовність у розміщенні даних на екрані.

Рекомендується наступний шаблон для оформлення екрану:

Праворуч в 2-х, 3-х рядках міститься заголовок і дані про стан системи;

Далі, під заголовком розміщується область для виведення довідкових повідомлень;

Основна область - для малювання або для введення даних;

Нижче - область для виведення повідомлень про помилки;

Опис функціональних клавіш.

Стислість.

Вимагає від користувача введення мінімуму інформації. Це, з одного боку, прискорює роботу системи, а, з іншого, призводить до появи помилок.

Рекомендації:

Не слід запитувати інформацію, яку слід сформувати автоматично;

Інформація не повинна ви?? одітся одразу ж, тільки тому, що вона стала доступна системі. Вона повинна виводиться тільки в тому обсязі, який потрібно користувачеві і в потрібному для нього форматі.

Підтримка користувача - міра допомоги, яку система надає користувачеві при роботі з ній.

Ця підтримка виражається в 3-х видах:

Інструкції користувача. Виводяться у вигляді підказок або довідкової інформації. При цьому довідкова інформація повинна бути контекстної, своєчасною та доступною в будь-якій точці діалогу. Крім внутрішньосистемної існує зовнішня довідкова інформація, яка супроводжує текст у вигляді паперового носія. Там вказується 5 моментів:

Загальний огляд, у якому описується призначення системи, основні поняття предметної області, необхідні для оцінки системи, пов'язані з цими поняттями принципи роботи системи;

Як розпочати роботу з системою;

Відомості про поведінці користувача при виході системи або окремих частин з ладу;

Приклад роботи з системою;

Обмеження на систему.

Повідомлення про помилках. Гарне повідомлення про помилку повинно відповідати наступним вимогам:

Мабуть викладено в термінах, зрозумілих користувачеві;

Потрібно точно визначити причину помилки;

Повинно пояснювати, як виправити помилку;

Мабуть своєчасним, поки не виконані речі, які незворотні.

Підтвердження будь-яких дій системи.

Гнучкість - міра того, наскільки добре діалог відповідає різним рівням підготовки і продуктивності праці користувача. Гнучкість називають властивістю адаптивності системи.

Існує 3 системи, які характеризують її гнучкість:

37.Тіпи діалогів.

4 типу діалогу:

питання - відповідь;

меню;

командний мова;

екранні форми.

Запитання - відповідь. Сама стара форма ведення діалогу. Використовується в експертних системах, в інформаційно - пошукових системах до фактографічних або документальним баз даних.

3 види діалогу в режимі "запитання - відповідь":

Діалог з обмеженнями на предметну область. Форма запиту - довільна (обмежень немає), а лексика запиту будується на базі 2-х словників. 1-й містить функціональні слова, які або означають характер завдання, яке потрібно вирішити, або носять допоміжний характер, тобто ті запити з якими користувач звертається до БД. Ці функціональні слова є ключовими, сенс їх жорстко регламентований.

2-й словник містить специфічні терміни, які характеризують дану предметну область і, як правило, є іменами полів із записами бази даних. 1-е обмеження: якщо існують надійні закінчення, то кожне слово із запиту потрібно спроектувати на слова зі словника (де максимальне перехід, то і брати). 2-е обмеження в рамках діалогу -- обмеження на мову.

Вимоги:

Запит або завдання формується за допомогою фраз природної мови, кожна з яких описує елемент, операцію, яку треба виконати.

Кожне пропозиція повинна починатися з функціонального слова, що визначає потрібне дію.

При формулюванні умов пошуку кожне значення стать