Спосіб та система перетворення векторних даних

Реферат: Спосіб та система перетворення вхідного вектора даних належать до галузі представлення об'єкта, в елементах вихідного вектора даних. Кількаразове виконання способу або спрацьовування системи дозволяє отримати вихідний вектор даних, відповідний вхідному вектору даних. Результат перетворення еквівалентний виконанню перетворення вхідного вектора даних за допомогою проекційної матриці з елементами, які приймають значення 0 або 1, і наступної порогової трансформації. Перетворення здійснюється ефективно за рахунок використання особливостей застосованого типу проекції. Таким же перетворенням кожного вхідного вектора даних з масиву вхідних векторів даних отримують відповідний масив вихідних векторів даних, який може далі використовуватися системами та/або способами замість вхідного масиву. Цей вихідний масив може займати менше комп'ютерної пам'яті, ніж вхідний, та/або може бути представлений у форматі бінарних векторів даних з регульованою часткою одиничних елементів, що дозволяє обробляти вихідний масив більш ефективно, ніж вхідний, та/або застосовувати для обробки системи та/або способи, які ефективно оперують даними в такому форматі, або призначені для роботи з таким форматом даних. По вихідних векторах даних можна оцінити міри схожості та відмінності відповідних вхідних векторів даних. UA 102980 C2 (12) UA 102980 C2 UA 102980 C2 5 10 15 20 25 30 35 40 45 50 55 60 Винахід належить до області цифрової обробки даних, зокрема, до способів перетворення цифрових даних у вигляді числових векторів і може бути використаний для ефективного перетворення вхідних векторних даних у формат, який спрощує оцінювання мір їхньої схожості та відмінності. Більша частина електронних цифрових даних, які відповідають деяким об'єктам, може бути представлена як матриці або таблиці. Наприклад, масиви текстів при виконанні пошуку або класифікації можна розглядати як матриці слова-тексти, де в стовпцях - тексти, а в рядках слова. Покупки покупців можуть бути представлені матрицею, де в стовпцях - індивідуальні покупці, а в рядках - характеристики покупки, наприклад, місця покупок. Покупки покупців також можуть бути представлені матрицею, де в стовпцях - індивідуальні покупці, а в рядках - характеристики покупки, наприклад, куплені товари. Демографічна інформація про людей може бути представлена матрицею, де в стовпцях індивідуальні люди, а в рядках - їх характеристики, наприклад, вік, зріст, вага, та ін. Результати мас-спектрометричного аналізу білків пацієнтів можуть бути представлені матрицею, де в стовпцях - індивідуальні пацієнти, а в рядках - білки з різною масою. Ці лише приклади, далеко не вичерпні різноманітність даних, які відповідають деяким об'єктам та можуть бути представлені як матриці або таблиці. Також, слід розуміти, що об'єкти можуть бути представлені не в стовпцях, а в рядках матриці, і тоді характеристики об'єктів будуть представлені не в рядках, а в стовпцях матриці. Кожен рядок або стовпець матриці є вектором. Цю ж інформацію можна представити як набір векторів або точок в багатовимірному (евклідовому) просторі. Розмірність простору - це число координат (для матриці слова-тексти - це число слів), а кожна точка відповідає об'єкту (тексту). Координатами простору є елементи вектора. Розмірність простору може бути велика і складати, наприклад, сотні тисяч (за кількістю слів у мові), а число точок - мільйони й мільярди (по числу текстів - наприклад, число веб-сторінок Інтернет). У таких ситуаціях бажано перетворити масив даних таким чином, щоб число об'єктів, що представлені точками (векторами), збереглося, але підвищилась ефективність зберігання й обробки за рахунок зменшення витрат пам'яті, підвищення швидкості обробки, застосування спеціалізованих способів зберігання й обробки. Цих переваг можна досягти шляхом переходу в простір із відповідними властивостями: меншої розмірності, ніж вхідне; з більш простими операціями для обробки; або у простір, для якого існують ефективні способі обробки. Багато способів та систем оперують з мірами відмінності та схожості векторів у вхідному просторі, такими як відстань, скалярний добуток, кут та/або відношення відстаней і кутів та ін. Ці міри відмінності та схожості векторів взаємопов'язані. Наприклад, для двох векторів х1 і х2 їх скалярний добуток (х1, х2)=||х1|| ||х2|| cos(x1, x2); евклідова відстань ||х1-х2||=sqrt(||x1|| ||x1|| + ||х2|| ||х2|| - 2 ||х1|| ||х2|| cos(x1, х2)); де ||x1||, ||х2|| - евклідові норми векторів х1 і х2; cos(x1, x2) косинус кута між ними; sqrt - функція квадратного кореня. Мірами відмінності та схожості векторів оперують багато способів та систем інформаційного пошуку, класифікації, кластеризації, апроксимації, навчання і міркувань на основі прикладів, асоціативної пам'яті, і багато інших. В цих способах та системах широко використовувані лінійні моделі, що засновані на скалярному добутку; спосіб найближчого сусіда використовує міри відмінності та схожості, і т.д. Розглянемо приклад. Нехай заданий масив текстів, в якому треба знаходити тексти, близькі до запиту. Для цього, тексти та запити представляють як вектори. Розмірність вектора - число слів у словнику. Елементи вектора - слова словника. Значення елементів вектора - кількість разів уживання слова в тексті або запити. Знаходять схожість бінарних векторів запитів з бінарними векторами текстів бази за мірами схожості. Упорядковують тексти за величиною схожості та видають користувачеві найбільш подібні. Розглянемо інший приклад. Тексти новин треба відносить до ряду рубрик, щоб можна було читати новини з певної тематики. Тексти наявної бази текстів та нові тексти, що підлягають класифікації, представляють як вектори. Розмірність вектора - число слів у словнику. Елементи вектора - слова словника. Значення елементів вектора - кількість разів уживання слова в тексті. Для кожного тексту наявної бази текстів відомі рубрики, до яких вони належать. Знаходять схожість вектора вхідного тексту з векторами текстів бази за мірами схожості бінарних векторів. Надають вхідному тексту мітку класу (рубрику), що відповідає тексту бази з найбільш схожим вектором. Для таких і багатьох інших застосувань було б корисно оперувати з перетвореними векторними даними, які дають результати, що узгоджуються з результатами у вхідному багатовимірному векторному просторі, але при цьому більш ефективні - з точки зору економії 1 UA 102980 C2 5 10 15 20 25 30 35 40 45 50 55 60 пам'яті, швидкості обробки, можливості застосування для обробки даних інших класів систем, пристроїв та способів. Один з підходів до перетворення, яке дозволяє відновити відстані та кути між вхідними векторами по результуючим, полягає в застосуванні спеціально сконструйованої випадкової проекційної матриці R розмірністю NxA [W.B. Johnson & J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space // Contemporary Mathematics, 26:189-206, 1984; C.H. Papadimitriou, P. Raghavan, H. Tamaki, & S. Vempala. Latent semantic indexing: A probabilistic analysis, J. Comput. System Sci., 61:217-235, 2000; D.Achlioptas. System and method adapted to facilitate dimensional transform. U.S.Pat. 7318078; M.S. Charikar. Methods and apparatus for estimating similarity. U.S.Pat. 7158961; Мисуно И.С., Рачковский Д.А., Слипченко С.В. Векторные и распределенные представления, отражающие меру семантической связи слов // Математические машины и системы - 2005 - № 3 - С. 50-66], де А - число елементів вектора у вхідному просторі, N - число елементів вектора в результуючому просторі. Вхідний масив даних представлений вхідною матрицею X розмірністю AxL, L - число векторів. Проміжний результат перетворення - матриця Y - має розмірність NxL і отримується множенням Y=RX. Вихідна матриця Z(NxL), яка використовується для роботи подальшими способами обробки масиву даних, є результатом трансформації Y: Z=f(Y) і має розмірність NxL, як і Y. При певному виборі проекційної матриці R та трансформації f по векторам матриці Z можна оцінювати міри схожості відповідних векторів матриці X, які представляють деякі об'єкти (наприклад, тексти) - тобто, оцінювати схожість цих об'єктів. Так, в роботі [W.B. Johnson & J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space // Contemporary Mathematics, 26:189-206, 1984] за проекційну матрицю R було запропоновано використовувати випадкову ґаусову матрицю і використовувати в якості вихідної матриці Z безпосередньо матрицю Y=RX (що може розглядатися як тотожна трансформація, яка реалізується шляхом привласнення або переписування в елементи матриці Z значень елементів матриці Y): Z=Y. Показано, що за отриманими N-мірними векторами-стовпцями Z можна з високою точністю оцінити відстані між вхідними A-мірними векторами в X навіть при N