< Попер   ЗМІСТ

Фактор Фано

Для изучения поведения процессов принято использовать еще один показатель - индекс разброса дисперсии (IDC), так называемый фактор Фано. Эта величина определяется как отношение дисперсии количества событий о2 (k) на заданном окне наблюдений k к соответствующему математическому

ожиданию m (k):

Для самоподобных процессов выполняется соотношение:

где C и H - константы.

Уго Фано (1912-2001)

Fano U. Ionization field of radiations. II. The fluctuations of the number of ions. Phys. Rev., 1947. -№ 72.

R/S-анализ. Показатель Херста

Показатель Херста (H.E. Hurst) - H связан с коэффициентом нормированного размаха R/ S, где R -вычисляемый определенным образом "размах" соответствующего временного ряда, а S - стандартное отклонение. Херст экспериментально обнаружил, что для многих временных рядов справедливо:

Доказано, что показатель Херста связан с традиционной "клеточной" фрактальной размерностью П простым соотношением:

Условие, при котором показатель Херста связан с фрактальной "клеточной" размерностью в соответствии с приведенной формулой, определено Е. Федером следующим образом: "... рассматривают клетки, размеры которых малы по сравнению как с длительностью процесса, так и с диапазоном изменения функции; поэтому соотношение справедливо, когда структура кривой, описывающая фрактальную функцию, исследуется с высоким разрешением, т.е. в локальном пределе". Еще одним важным условием является самоаффинность функции.

Гарольд Эдвин Херст (1880-1978)

Hurst H. Long Term Storage Capacity of Reservoirs. Transactions of the American Society of Civil Engineers, 1951. - № 116.

Показатель Херста характеризует персистентность -склонность процесса к трендам (в отличие от обычного броуновского движения). Значение означает, что направленная в определенную сторону динамика процесса в прошлом, вероятнее всего, повлечет продолжение движения в том же направлении.

Если то прогнозируется, что процесс изменит направленность. Н = % означает неопределенность -броуновское движение.

В частности, для изучения фрактальных характеристик

тематических информационных потоков для временных рядов

составленных из количества сообщений, опубликованных за промежуток времени от п — 1 до п, изучалось значение показателя Херста, определяемое из соотношения:

Здесь 5 - стандартное отклонение:

а Я - так называемый размах:

где

Исследования фрактальных свойств рядов измерений, получаемых в результате мониторинга тематических информационных массивов из Интернет, свидетельствуют о том, что показатель Н принимает значения в диапазоне 0.65 0.75, т.е. намного превышает Уэ. Поэтому можно утверждать, в этом случае обнаруживается персистентность (существование долговременных корреляций, которые могут быть связаны с проявлением детерминированного хаоса). Оказывается, что ряд Е(п) имеет фрактальную размерность D,равную

Исследования тематических информационных потоков подтверждают предположение о самоподобии и итеративности процессов в веб-пространстве. Републикации, цитирование, прямые ссылки и т. п. порождают самоподобие, проявляющееся в устойчивых статистических распределениях и известных эмпирических законах.

Вильфредо Парето (1848 - 1923)

Анализируя общественные процессы, В. Парето рассмотрел социальную среду как пирамиду, на вершине которой находятся некоторые люди, представляющие элиту. В результате исследований он

математически сформулировал зависимость между величиной дохода и количеством лиц, которые его получают. Парето в 1906 году установил, что около 80 % земли в Италии принадлежит лишь 20 % ее жителей. Он пришел к заключению, что параметры полученного им распределения приблизительно одинаковы и не различаются принципиально в разных странах и в разное время. Точно такая же закономерность по Парето наблюдается и в распределении доходов между людьми.

Распределение доходов по Парето описывается уравнением , где X - величина дохода, N -количество людей с доходом, равным или превышающим X, А и р - параметры распределения. В математической статистике это распределение получило имя Парето, при этом предполагаются естественные ограничения на параметры:

Распределению Парето присуще свойство устойчивости, т.е. сумма двух случайных переменных, которые имеют распределение Парето, также будет соответствовать этому распределению. Замеченное правило, называемое "законом Парето" или "принципом 80/20", применимо в очень многих областях. Например, при информационном поиске достаточно определить 20% важнейших ключевых слов, чтобы найти 80% необходимых документов, а затем расширить поиск или воспользоваться опцией "найти похожие" для полного решения задачи. Еще один пример: 80% посещений веб-сайта приходится лишь на 20% его вебстраниц.

При построении систем массового обслуживания, в том числе и информационно-поисковых систем, необходимо учитывать тот факт, что наиболее сложным функциональным возможностям системы, на реализацию которых уходит 80 и больше процентов трудозатрат, будут пользоваться не более чем 20 процентов пользователей данной системы.

В строгой формулировке этот эффект носит название принципа Парето. Предположим, что последовательность

соответствует размерам доходов отдельных людей. После ранжирования этой последовательности по убыванию получается новая последовательность

(элементы расположены в порядке убывания).

Предположим, что N - общее число людей, у которых

Тогда правило Парето можно переписать в таком виде:

Откуда:

Рассматривается сумма первых значений величины Х(г), т.е. общая величина дохода наиболее

богатых людей -

где

Переходя от дискретных величин к непрерывным (предполагая, что п >> 1), имеем:

В безразмерных переменных

- и

последнее равенство имеет вид (см. рис. 23):

Распределение Парето для различных значений параметров: зависимость
 для трех случаев:

Рис. 3.13.1 - Распределение Парето для различных значений параметров: зависимость

для трех случаев:

Величина / - в нашем примере - относительное количество дохода, получаемого первыми по рангу п людьми, доля которых (относительно всех людей) равна V .

Дж. Ципф изучил использование статистических свойств языка в текстовых документах и выявил несколько эмпирических законов, которые представил как эмпирическое доказательство своего "принципа наименьшего количества усилий". Он экспериментально показал, что распределение слов естественного языка подчиняется закону, который часто цитируется как первый закон Ципфа, относящийся к распределению частоты слова в тексте. Этот закон можно сформулировать таким образом. Если для какого-нибудь довольно большого текста составить список всех слов, которые встретились в нем, а потом ранжировать эти слова в порядке убывания частоты их появления в тексте, то для любого слова произведение его ранга и частоты появления будет величиной постоянной:

f X r = c, где f частота встречаемости слова в тексте; г - ранг слова в списке; с - эмпирическая постоянная величина (коэффициент Ципфа). Для славянских языков, в частности, коэффициент Ципфа составляет приблизительно 0,06-0,07.

Джордж Ципф (1902 - 1950)

Manning C.D., Schütze H. Foundations of Statistical Natural Language Processing - Cambridge, Massachusetts: The MIT Press, 1999.

Приведенная зависимость отражает тот факт, что существует небольшой словарь, который составляет большую часть лексем текста. Это главным образом служебные слова. Например, приведенный в монографии К.Д. Маннинга и Г. Шютце анализ романа "Том Сойер", позволил выделить 11.000 английских слов. При этом было обнаружено двенадцать слов (the, and, и др.), каждое из которых охватывает более 1 % лексем в романе.

Ципф объяснял гиперболическое распределение "принципом наименьшего количества усилий" предполагая что при создании текста меньше усилий уходит на повторение некоторых слов, чем на использование новых, т.е. на обращение к "оперативной памяти, а не к долгов ременной".

Ципф сформулировал еще одну закономерность, которая состоит в том, что частота и количество слов, которые входят в текст с данной частотой, также связанны подобным соотношением, а именно:

(3.13.6)

где N( /) - количество различных слов, каждое из которых используется в тексте / раз, В - некоторая константа нормирования.

Существует простая количественная модель определения зависимости частоты от ранга. Предположим, что генерируется случайный текст обезьяной на пишущей машинке. С вероятностью р генерируется пробел, а с вероятностью - другие символы, каждый из которых имеет равную вероятность. Показано, что полученный таким образом текст будет давать результаты, близкие по форме распределению Ципфа.

Лексема - слово как абстрактная единица морфологического анализа. В одну лексему объединяются различные словоформы одного слова. Например, словарь, словарем, словарю - это формы одной и той же лексемы, по соглашению пишущейся как словарь.

Более сложную модель генерации случайного текста, удовлетворяющего второму закону Ципфа, предложил Г.А. Саймон в 1955 г. В соответствии с этой моделью, если текст достиг размера в п слов, тогда то, каким будет (п +1) -е слово текста определяется двумя допущениями:

  • 1. Пусть N( Г, п) - количество разных слов, каждое из которых использовалось Г раз среди первых п слов текста. Тогда вероятность того, что (п + 1) -ым окажется слово, которое до того использовалось Г раз пропорционально Г Щ Г, п) - общему количеству появления всех слов, каждое из которых до этого использовалось / раз.
  • 2. С вероятностью

словом будет новое слово.

Из допущения 1 следует:

где К(п) - коэффициент пропорциональности.

Аналогично допущение 2 приводит к уравнению:

Из условия того, что вероятность генерации слова равна 1, имеем:

Учитывая то, что

имеем:

Кроме того, вводится еще одно допущение, состоящее в том, что для всех / выполняется:

Из последнего допущения следует, что

При этом

не зависит от я и, с учетом предыдущих уравнений:

Переходя к функции

для

имеем:

Использовав последнее уравнение Г 1 раз получаем:

Введя обозначение р = 1/ (1 — 6) последнее уравнение можно переписать:

Учитывая то, что

при Г —> те и обозначив в = 1 + р , имеем окончательно:

Распределение Ципфа часто искажается на практике ввиду недостаточных объемов текстовых корпусов, что приводит к проблеме оценки параметров статистических моделей. С другой стороны, соотношение между рангом и частотой была взята Солтоном в 1975 г. [116] как отправная точка для выбора терминов для индексирования.

Далее им рассматривалась идея сортировки слов в соответствии с их частотой в корпусе. Как второй шаг высокочастотные слова могут быть устранены, потому что они не являются хорошими различительными признаками для документов коллекции. На третьем шаге термы с низкой частотой, определяемой некоторым порогом (например слова, которые встречаются только единожды или дважды) удаляются, потому что они встречаются так нечасто, что редко используются в запросах пользователей. Используя этот подход, можно значительно уменьшить размер индекса поисковой системы. Более принципиальный подход к подбору индексных термов - учет их весовых значений. В весовых моделях среднечастотные термы оказываются самыми весомыми, так как они являются наиболее существенными при отборе того или иного документа (наиболее частотные слова встречаются одновременно в большом количестве документов, а низкочастотные могут не входить в документы, интересующие пользователя).

Еще один эмпирический закон, сформулированный Ципфом состоит в том, что количество значений слова коррелирует с квадратным корнем его частоты. Подразумевалось, что нечасто используемые слова менее неоднозначны, а это подтверждает то, что высокочастотные слова не подходят для внесения в индексы информационно-поисковых систем.

Ципф также определил, что длина слова обратно пропорциональна его частоте, что может быть легко проверено путем простого анализа списка служебных слов. Последний закон действительно служит примером принципа экономии усилий: более короткие слова требуют меньше усилий при воспроизведении, и таким образом, используются более часто. Этот "закон" можно подтвердить, рассматривая приведенную выше модель генерации слов обезьяной. Легко видеть, что вероятность генерации слова уменьшается с длиной, вероятность слова из п непробельных символов равна:

где р - вероятность генерации пробела.

Хотя закон Ципфа дает интересные общие характеристики слов в корпусах, в общем случае замечены некоторые ограничения его применимости при получении статистических характеристик коллекций документов, состоящих из множества независимых документов разных авторов. Законам Ципфа удовлетворяют не только слова из одного текста, но многие объекты современного информационного пространства.

 
< Попер   ЗМІСТ