Текстовый анализатор: распознавание авторства (окончание)

Эта статья об алгоритме распознавания авторства, реализованном в проекте «Текстовый анализатор». В окончании статьи мы рассмотрим, как собираются частотные характеристики, и в общих чертах познакомимся с нейросистемой Хэмминга. (Начало и продолжение).

Структура статьи:

1. Анализ авторства
2. Знакомство с кодом
3. Внутренности TAuthoringAnalyser и хранение текстов
4. Разбиение на уровни конечным автоматом на стратегиях
5. Сбор частотных характеристик
6. Нейросеть Хэмминга и анализ авторства

Дополнительные материалы:

• Исходники проекта «Текстовый анализатор» (Borland C++ Builder 6.0)
• Тестирование нейросистемы Хэмминга в Excel'е ([xls])
• Таблица переходов для КА, разбивающего текст на уровни ([xls])
• Расчет благозвучия отдельных букв ([xls])
• Презентация дипломного проекта «Текстовый анализатор» ([ppt])
• Презентация проекта «Карта благозвучия» ([ppt])
• Все эти материалы в сжатом виде ([zip], [7z], [rar])

5. Сбор частотных характеристик

Наиболее полезны для распознавания авторства частотные характеристики отдельных символов, двух-, трёхбуквенных сочетаний, частотные таблицы слов и т.д. В этой программе реализовано только самое простое: подсчет частот символов. Конечно, для комплексного анализа этого недостаточно. Сейчас точность распознавания, надо признать, не очень высокая. Насколько помню, в тестах вероятность правильного ответа достигала 60-70 процентов, и то — в идеальных условиях. Разрабатывая программу, я надеялся когда-нибудь её переписать, добавив комплексный анализ авторства на основе многих методов. Кто знает, может, ещё и возьмусь…

Итак, сбор частотных характеристик символов. Класс TCharFrequencyCalculator ([h]) составляет частотную таблицу, выполняя один проход по тексту. Шаблонный класс TFrequencyTable ([h]) может хранить частотную таблицу для объектов любого типа.

Copy Source | Copy HTML

1. class TCharFrequencyCalculator
2. {
3. private:
4.  
5.     TFrequencyTable<TChar> _FTable;
6.  
7. public:
8.  
9.     TFrequencyTable<TChar> & operator ()(TTextStringWrapper & tWrapper)
10.     {
11.         _FTable << ftm_Clear;
12.  
13.     TUInt i;
14.         TTextStringWrapper d; // Эта переменная, видимо, просто мусор в коде...
15.         for (i=tWrapper.Begin(); i<=tWrapper.End(); i++)
16.             _FTable << (tWrapper[i]);
17.     return _FTable;
18.     };
19.  
20.     TFrequencyTable<TChar> & operator ()(const TTextString & tTextString)
21.     {
22.         _FTable << ftm_Clear;
23.  
24.         for (TSInt i=1; i<=tTextString.Length(); i++)
25.             _FTable << tTextString[i];
26.     return _FTable;
27.     };
28.  
29.     TCharFrequencyCalculator(){};
30. };

// Использование:
TCharFrequencyCalculator calculator;
TFrequencyTable charFrequencyTable = calculator(text);


Стоит обратить внимание на то, что функций, подсчитывающих частоты, аж две. Первая принимает TTextStringWrapper ([cpp], [h]) — класс-обёртку над текстовой строкой. «Обёртка» ещё известна как паттерн Адаптер (Adapter, Wrapper, [1], [2], [3]). Он преобразует интерфейс одного класса в интерфейс другого. Можно было сделать по-настоящему универсальный калькулятор, но пришлось бы абстрагироваться от объектов, частоты которых мы подсчитываем. Калькулятора вообще не должно волновать, в каких списках, таблицах или массивах там хранятся данные, откуда берутся, сколько элементов, и в каком они порядке. Адаптированные под нужный калькулятору интерфейс, списки объектов обрабатывались бы единообразно… У вас не возникло ощущения дежа-вю? Правильно, мы это уже обсуждали, когда рассматривали менеджер конечного автомата. Там мы абстрагировались от списков событий с помощью паттерна «Итератор», а здесь — от списков элементов с помощью «Адаптер». Это его нетипичное применение, оно хуже, чем итераторы: нам бы пришлось наплодить иерархии адаптеров и частотных таблиц, чтобы их можно было оперативно заменять. В конце концов, адаптер перестал бы быть собой, а превратился в некий абстрактный контейнер. Примерно так бы это выглядело:

Copy Source | Copy HTML

1. class TFrequencyCalculator
2. {
3.     TFrequencyTable * operator ()(TWrapper * tWrapper, TFrequencyTable *table)
4.     {
5.         table << ftm_Clear;
6.  
7.         for (int i=tWrapper->Begin(); i<=tWrapper->End(); ++i)
8.             table << (tWrapper->at(i));
9.     return table;
10.     };
11. }
12.  
13. class TWordWrapper : public TWrapper
14. {
15. // ......
16.     virtual int Begin() const;
17.     virtual int End() const;
18.     virtual Word at(const int &index) const;
19. // ......
20. };
21.  
22. class TSentenceWrapper : public TWrapper {/*......*/};
23. class TWordsFrequencyTable : public TFrequencyTable {/*......*/};
24. class TSentenceFrequencyTable : public TFrequencyTable {/*......*/};
25.  
26. // Использование:
27. TWordWrapper wordWrapper = TWordWrapper(wordsList)
28. TFrequencyCalculator wordCalc;
29. TWordsFrequencyTable wordFrequencyTable = wordCalc(&wordWrapper, &wordFrequencyTable);
30.  
31. TSentenceWrapper sentenceWrapper = TSentenceWrapper(sentencesMap)
32. TFrequencyCalculator sentenceCalc;
33. TSentenceFrequencyTable sentenceFrequencyTable = sentenceCalc(&sentenceWrapper, &sentenceFrequencyTable);
34.  

6. Нейросеть Хэмминга и анализ авторства

Наконец, мы с вами, уставшие и побитые, добрались до самого последнего шага. Нейросеть Хэмминга ([1], [2]) берёт за основу набор бинарных векторов одинаковой длины. Они называются образцами и хранятся в матрице образцов. На вход нейросети подаётся тестируемый вектор той же длины. Количество входов равно размеру вектора; для данных большого объёма входов может быть очень много. Одно из преимуществ ИНС Хэмминга (перед ИНС Хопфилда) в том, что какой бы ни была размерность входного вектора, структура нейросети не поменяется. Слоёв — два, причём первый фиктивный; выходов и нейронов в каждом слое ровно столько, сколько образцов в матрице. Нейросеть работает быстро. Её задача — найти в матрице образцов вектор, который больше всего «похож» на входной. Похожесть определяется так называемым расстоянием Хэмминга. Чем меньше это расстояние, тем более «похожи» два вектора. Условно говоря, расстояние Хэмминга показывает, сколько битов в этих векторах не совпадает. Посчитать расстояние Хэмминга несложно, да и вся нейросеть — это лишь удобное представление нескольких простых формул. Вычислив какие-то значения, нейросеть сходится к результату: на выходах будет получен вектор со всеми нуликами, — исключая какой-нибудь один выход, где появится единица. Индекс этого выхода указывает на искомый образец в матрице образцов.

Чтобы загрузить в нейросеть (класс THamNeuroSystem: [cpp], [h]) образцы текстов, их нужно преобразовать к бинарному виду. Это делает шаблонный класс-коннектор (THamNSConnector: [h]). Забавно видеть код нейросети и коннектора: я понимаю, что это можно сделать гораздо, гораздо проще.

Copy Source | Copy HTML

1. template <class T> void THamNSConnector<T>::ByteToBinaryVector(T DataItem, TSInt SizeOfData, TSampleVector *DestinationVector)
2. {
3. vector <bool> BoolBits;
4. T NewDataItem = DataItem;
5.  
6.     for (TSInt i=1; i<SizeOfData; i++)
7.     {
8.         BoolBits.clear();
9.  
10.         BoolBits.push_back( NewDataItem & bitOne );
11.         BoolBits.push_back( NewDataItem & bitTwo );
12.         BoolBits.push_back( NewDataItem & bitThree );
13.         BoolBits.push_back( NewDataItem & bitFour );
14.         BoolBits.push_back( NewDataItem & bitFive );
15.         BoolBits.push_back( NewDataItem & bitSix );
16.         BoolBits.push_back( NewDataItem & bitSeven );
17.         BoolBits.push_back( NewDataItem & bitEight );
18.  
19.         for (TUInt j= 0; j<BoolBits.size(); j++)
20.                 {
21.             if (BoolBits[j]) DestinationVector->push_back(1);
22.             else DestinationVector->push_back( 0);
23.                 }
24.  
25.     NewDataItem = NewDataItem >> 8;
26.     };
27. };
28.  
29. template <class T> TSampleVector THamNSConnector<T>::VectorToBinaryVector(TVector SourceVector)
30. {
31.     TSInt SizeOfData;
32.     T DataItem;
33.     TUInt i;
34.     TSampleVector ResVector;
35.  
36.     SizeOfData = sizeof(T);
37.  
38.     for (i= 0; i<SourceVector.size(); i++)
39.     {
40.         DataItem = SourceVector[i];
41.         ByteToBinaryVector(DataItem, SizeOfData, &ResVector);
42.     };
43.  
44.     return ResVector;
45. };
46.  

На этом всё. Если не считать моих попыток улучшить нейросеть, больше рассказывать не о чем. Нейросеть возвращает индекс образца того текста, характеристики которого она считает более сходными с характеристиками текста неизвестного автора. Насколько правдив ответ, вы можете выяснить сами, скомпилировав программу. Меня на обширные тесты не хватило ни тогда, при написании диплома, ни сейчас. Надеюсь, статья была полезна.

С уважением.