Фракталы и кластеры в информационном пространстве

Дмитрий ЛАНДЭ,
к.т.н., заместитель директора

Информационного центра "ЭЛВИСТИ"

Немного истории

Термин фрактал (от латинского слова fractus - дробный), был предложен Б. Мандельбротом в 1975 году для обозначения нерегулярных самоподобных математических структур. Популярная сегодня фрактальная геометрия получила свое название лишь в 1977 году благодаря его книге "The Fractal Geometry of Nature". В работах ученого использованы научные результаты многих ученых, работавших в этой же области (прежде всего, Пуанкаре, Кантора, Хаусдорфа). Основное определение фрактала, данное Мандельбротом, звучало так: "Фракталом называется структура, состоящая из частей, которые в каком-то смысле подобны целому".

В самом простом случае небольшая часть фрактала содержит информацию о всем фрактале. Строгое определение самоподобных множеств было дано Дж. Хатчинсоном в 1981 году. Он назвал множество самоподобным, если оно состоит из нескольких компонент, подобных всему этому множеству, т.е. компонент получаемых афинными преобразованиями - поворотом, сжатием и отражением исходного множества.

Однако самоподобие - это хотя и необходимое, но далеко не достаточное свойство фракталов. Ведь нельзя же, в самом деле, считать фракталом точку, или плоскость, расчерченную клетками. Главная особенность фракталов заключается в том, что их размерность не укладывается в привычные геометрические представления. Фракталам характерна геометрическая "изрезанность". Поэтому используется специальное понятие фрактальной размерности, введенное Ф. Хаусдорфом и А. Безиковичем. Эта размерность не соответствует привычным для нас длине, площади или объему (размерности 1, 2 или 3, соответственно). Размерность фракталов - не является целым числом, характерным для привычных геометрических объектов. Вместе с тем, в большинстве случаев фракталы напоминают объекты, плотно занимающие реальное пространство, но не использующее его полностью.

Примеры абстрактных фракталов

Мандельброт предложил не только определение фракталов, но также и алгоритм построения одного из них, получившего название в честь ученого. Алгоритм построения множества Мандельброта основан на итеративном вычислении по формуле:

Z[i+1] = Z[i] * Z[i] + C,

где Z и C - комплексные переменные. Итерации выполняются для каждой стартовой точки

C прямоугольной или квадратной области - подмножестве комплексной плоскости.

Итерационный процесс продолжается до тех пор, пока Z[i] не выйдет за пределы окружности заданного радиуса, центр которой лежит в точке (0,0), или после достаточно большого числа итераций. В зависимости от количества итераций, в течение которых Z[i] остается внутри окружности, устанавливается цвет точки C. Если Z[i] остается внутри окружности в течение достаточно большого количества итераций, то эта точка растра окрашивается в черный цвет. Множеству Мандельброта принадлежат именно те точки, которые в течение бесконечного числа итераций не уходят в бесконечность.

Множество Мандельброта

Так как количество итераций соответствует номеру цвета, то точки, находящиеся ближе к множеству Мандельброта, имеют более яркий цвет.

Множество Мандельброта

Построение другого фрактального множества, снежинки Коха, начинается с правильного треугольника, длина стороны которого равна 1. Сторона треугольника считается базовым звеном для исходного положения. Далее, на любом шаге итерации каждое звено заменяется на образующий элемент - ломанную, состоящую по краям из отрезков длиной 1/3 от длины звена, между которыми размещаются две стороны правильного треугольника со стороной в 1/3 длины звена. Все отрезки - стороны полученной кривой считаются базовыми звеньями для следующей итерации. Кривая, получаемая в результате n-й итерации при любом конечном n, называется предфракталом, и лишь при n, стремящемся к бесконечности, кривая Коха становится фракталом. Получаемое в результате итерационного процесса фрактальное множество представляет собой линию бесконечной длины, ограничивающую конечную площадь. Действительно, при каждом шаге число сторон результирующего многоугольника увеличивается в 4 раза, а длина каждой стороны уменьшается только в 3 раза, т.е. длина многоугольника на n-й итерации равна 3*(4/3)n и стремится к бесконечности с ростом n.

Первые 5 поколений снежинки Коха

Площадь под кривой, если принять площадь образующего треугольника за 1, равна:

S = 1 +1/3 Сумма k=0 до бесконечности (4/9) в степени k = 1.6

В 80-х годах ХХ века как простое средство получения фрактальных структур появился метод "Систем Итерируемых Функций" (Iterated Functions System - IFS). IFS представляет собой систему функций, отображающих одно многомерное множество на другое. Наиболее простая реализация IFS представляет собой аффинные преобразования плоскости:

X' = A*X + B*Y + C

Y' = D*X + E*Y + F

В 80-х годах американские ученые М. Барнсли и А. Слоан предложили идею сжатия и хранения графической информации, основанную на соображениях теории фракталов и динамических систем. На основании этой идеи был создан алгоритм фрактального сжатия информации, позволяющий сжимать некоторые образцы графической информации в 500- 1000 раз. При этом каждое изображение кодируется несколькими простыми аффинными преобразованиями. Закодировав какое-то изображение двумя аффинными преобразованиями, оно однозначно определяется с помощью 12-ти коэффициентов. Если определить начальную точку итерационного процесса (например, X=0 Y=0) и запустить этот процесс, то через несколько итераций совокупность полученных точек будет описывать закодированное изображение.

В качестве примера использования IFS для построения фрактальных структур, можно привести кривую "дракона" Хартера-Хейтуэя.

"Дракон" Хартера-Хейтуэя

Использование IFS для сжатия обычных изображений, например, фотографий основано на выявлении локального самоподобия (в отличие от фракталов, где наблюдается глобальное самоподобие). По алгоритму Барнсли происходит выделение в изображении пар областей, меньшая из которых подобна большей, и сохранение нескольких коэффициентов, кодирующих преобразование, переводящее большую область в меньшую. Требуется, чтобы множество таких областей покрывало все изображение. Восстанавливающий алгоритм должен применять каждое преобразование к некоторому подмножеству, принадлежащему области, соответствующей применяемому преобразованию. Фракталы с большой точностью описывают многие физические явления и природные образования: облака, турбулентные течения, ветви деревьев, кровеносные сосуды. Мандельброт в свое время заметил: "Почему геометрию часто называют холодной и сухой? Одна из причин заключается в ее неспособности описать форму облака, горы, дерева или берега моря. Облака - это не сферы, горы - не конусы, линии берега - это не окружности, и кора не является гладкой, и молния не распространяется по прямой. Природа демонстрирует нам не просто более высокую степень, а совсем другой уровень сложности."

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

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

Один из лучших примеров проявления фракталов в природе -структура береговых линий. Действительно, на километровом отрезке побережье выглядит столь же изрезанным, как и на стокилометровом. Опыт показывает, что длина береговой линии L зависит от масштаба l, которым проводятся измерения, и увеличивается с уменьшением последнего по степенному закону L = Л l ^ 1-альфа, Л = const . Так, например, для побережья Великобритании альфа приблизительно равна 1.24, т.е., так называемая, фрактальная размерность береговой линии Великобритании равна 1.24.

Бреговая линия побережья Великобритании

Недавно Б. Саповаль из Политехнической школы в Палезо (Франция) и его коллеги создали компьютерную модель эрозии побережья. В модели вещество разрушалось либо под прямым воздействием волн, либо медленным "выветриванием", когда минералы растворялись в воде. Побережье было разделено на равные участки, причем в модели типы камней на этих участках выбирались случайным образом. Эрозионная сила моря зависит от того, насколько сильно глушатся волны. В узком заливе или бухте вода всегда спокойнее. Саповаль предположил, что глушение волн усиливается по мере того, как берег становится более изрезанным. Модель показала, что изначально гладкая береговая линия стремительно приобретает неровный профиль с выступами и множеством отделенных от берега островов. В результате она приобретает привычный профиль с фракталами. При моделировании береговых линий использовались двумерные стохастические фракталы, которые получаются в том случае, если в итерационном процессе случайным образом варьировать некоторые его параметры. Образовавшийся при моделировании берег очень напоминал Восточное побережье США. Поэтому ученые полагают, что им удалось обнаружить основное воздействие - изменение эрозионной силы самим побережьем.

В 2004 году в Ньюфаундленде биологом Ги Нарбонна из университета Кингстона (Канада) была открыта редкая ископаемая природная структура фрактального типа. Были найдены следы организмов, живших на Земле около 575 миллионов лет назад, и не относившихся ни к растениям, ни к животным, и называются рангеоморфами. Они были неспособны двигаться и не имели репродуктивных органов, а размножались, создавая новые ответвления. Организмы собирались во фрактальные структуры из разветвляющихся частей. Как выяснилось, каждый ветвящийся элемент фрактальных структур состоял их множества трубок, удерживаемых вместе полужестким органическим скелетом организмов. Нарбонн обнаружил рангеоморфы, собранные в несколько разных форм. Фрактальный рисунок представляется достаточно сложным, но, по словам исследователя, сходство организмов друг с другом делало достаточным простой геном для создания новых свободно плавающих ответвлений и для соединения ответвлений в более сложные структуры.

Уже около полувека в биологии известен закон, который утверждает, что многие свойства организмов, от продолжительности жизни и количества детенышей до скорости обмена веществ, пропорциональны массе тела в степени n/4, где n - целое. При этом сама природа закона более полувека оставалась загадкой. На первый взгляд, вместо четверки должна быть тройка, поскольку масса пропорциональна кубу размера тела.

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

И наконец, вся Вселенная, в соответствии с гипотезой российского физика С. Хайтуна, является фракталом, причем единственным известным в природе, полностью удовлетворяющим классическому определению. В физике известен факт, что плотность космических объектов стремительно падает с их размерами. Еще в 50-х годах советские физики-теоретики пришли к выводу, что "бесконечная" плотность Вселенной равна нулю. Эта идея и новейшие представления о фрактальности Вселенной подтверждают друг друга. Дело в том, что плотность всякого фрактала, расположенного в трехмерном пространстве, тождественно равна нулю. Классические фракталы обладают "всюду пустой" структурой, которая при проникновении в нее "расступается" до бесконечности. Вместе с тем, реальные системы бесконечного углубления в свою структуру не позволяют; на каком-то конечном шаге структура, будь то, скажем, снежинка или кровеносная система человека, теряет свой "фрактальный" вид - реальные структуры лишь "фракталоподобны". В соответствии с гипотезой Хайтуна, позволяя - из-за своей бесконечности - бесконечное проникновение в свою структуру, Вселенная, по мнению многих исследователей, является единственным "настоящим" фракталом, имея нулевую бесконечную плотность.

Информационное пространство и фракталы

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

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

В информационном пространстве возникают, формируются, растут и размножаются кластеры - группы взаимосвязанных документов. Системы, основанные на кластерном анализе, самостоятельно выявляют новые признаки объектов и распределяют объекты по новым группам.

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

Фрактальные свойства характерны для кластеров информационных Web-сайтов, на которых публикуются документы, соответствующие определенным тематикам. Эти кластеры, как наборы тематических документов, представляют собой фрактальные структуры, обладающие рядом уникальных свойств. Например, российскими исследователями (С. Иванов и др.), определена фрактальная размерность подобных информационных массивов, изменяющаяся в пределах от 1.05 до 1.50, что свидетельствует о небольшой плотности заполнения кластеров документами по одной теме.

Как один из основных законов отражающих самоподобие информационного пространства можно назвать закон Зипфа. В 1949 году профессор филологии из Гарварда Дж. Зипф собрал достаточный статистический материал, и экспериментально показал, что распределение слов естественного языка подчиняется закону: "Если к какому-либо достаточно большому тексту составить список всех встретившихся в нем слов, а затем ранжировать эти слова, т.е. расположить их в порядке убывания частоты встречаемости в данном тексте и пронумеровать в возрастающем порядке, то для любого слова произведение его порядкового номера (ранга) этом списке и частоты его встречаемости в тексте будет величиной постоянной." Ученый описал обнаруженную им закономерность распределения слов в текстах на английском языке:
- небольшое количество слов, таких как "the", "and" в английском языке, которые имеют очень высокий ранг;
- среднее количество слов имеет средний ранг;
- большое количество слов имеет очень низкий ранг.

Таким образом: f * r = c, где f - частота встречаемости слова в тексте; r - ранг (порядковый номер) слова в списке; с - эмпирическая постоянная величина. Эту закономерность зависимости частоты от ранга называют первым законом Зипфа. Т.е. зависимость количества слов с данной частотой от частоты - гипербола с постоянными параметрами для всех текстов в пределах одного языка. Значение константы в разных языках различно, но внутри одной языковой группы остается неизменным. Так, например, для английских текстов константа Зипфа равна приблизительно 0,1. Для русского и украинского языков коэффициенты Зипфа составляю приблизительно 0,06-0,07.

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

Основатель теории фракталов Б. Мандлеброт предложил теоретическое обоснование закона Зипфа, полагая, что можно сравнивать язык текста с кодированием. Исходя из требований минимальной стоимости сообщений, Мандельброт математическим путем пришел к аналогичной первому закону Зипфа зависимости f*r^e = c , где e - близкая к единице переменная величина, которая может изменяться в зависимости от свойств текста и языка. Постоянство коэффициента е сохраняется только в центральной зоне диаграммы распределения. По относительной величине той или иной зоны на графике можно судить о характеристиках рассматриваемой в тексте области знаний. Существуют также закономерности, открытые другими ученными (прежде всего, Брэдфордом - для периодических изданий и Лотки - для распределения авторов), являющиеся уточняющими следствиями закономерностей Зипфа, и также свидетельствующими о самоподобии информационного пространства.

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

В качестве примера применения кластерного анализа к информационному пространству приведем задачу выявления цепочек наиболее важных сюжетов в информационном потоке новостной информации из Интернет. Алгоритм выявления основных сюжетных цепочек, используемый, например, в системе InfoStream заключается в следующем. Последний поступивший на вход системы документ (документ с номером 1 при обратной нумерации) порождает первый кластер и сравнивается со всеми предыдущими в соответствии с некоторой метрикой ?, задающей тематическую близость документов. Если эта мера близости для какого-нибудь документа оказывается выше некоторой пороговой, то текущий документ приписывается первому кластеру. Сравнение продолжается, пока не исчерпывается список актуальных документов потока. После такой обработки, происходит обработка следующего документа, не вошедшего в первый кластер, с которым последовательно сравниваются все актуальные документы потока и т.д. В результате формируется некоторое неизвестное заранее количество кластеров, которые ранжируются по своим весам, задаваемым такими критериями, как время порождения информации, авторитет источников, пользовательские предпочтения и т.д.

В окончательное рассмотрение принимается лишь определенное количество кластеров с наибольшими весами, т.е. группы наиболее актуальных сообщений. Для выбранных кластеров заново пересчитываются центроиды - документы наиболее отражающие тематику кластера. Таким образом формируются сюжетные цепочки, реализующие запросы типа "о чем больше всего пишут по заданной тематике наиболее авторитетные изданий в последнее время?".

Пример формирования сюжетных цепочек

Фрактальный принцип самоподобия предполагает бесконечное дробление набора объектов с сохранением их свойств. В данном случае можно наблюдать подобие сюжетных цепочек, получаемых при уточнении запроса (конечно в определенных рамках). Вместе с тем, сегодня многими исследователями рассматривается не дробление, а естественный рост размеров информационного пространства.

Свойства самоподобия фрагментов информационного пространства наглядно демонстрирует новый интерфейс представленный на веб-сайте службы News Is Free (http://newsisfree.com). На этом сайте отображается состояние информационного пространства в виде ссылок на источники и отдельные сообщения. При этом учитывается два основных параметра отображения - ранг популярности и "свежесть" информации. В рамках этой модели можно наблюдать "дробление" групп источников при увеличении ранга популярности и "свежести" изданий. Когда этот ранг становится достаточно высоким, дробление не позволяет без особых усилий читать названия источников и идентифицировать отдельные документы.

Кластеры публикаций службы News Is Free

Web-пространство, являясь, пожалуй, самой динамичной частью информационного пространства, характеризуется большом количестве скрытых в нем неявных экспертных оценок, реализованных в виде гиперссылок. В ноябре 1999 года один из руководителей института поиска и анализа текстов, входящего в исследовательское подразделение IBM, Андрей Бр╦дер (Andrei Broder) и его соавторы из компаний AltaVista, IBM и Compaq математически описали "карту" ресурсов и гиперсвязей. Исследования опровергли расхожее мнение, будто Internet - это единое густое пространство. Проследив с помощью поискового механизма AltaVista свыше 200 млн. Web-страниц и несколько миллиардов ссылок, размещенных на этих страницах, ученые пришли к выводу о структуре Web- пространства как ориентированного графа, в котором вершины соответствуют Web- страницам, а ребра - соединяющим эти страницы гиперссылкам. В рамках этой модели задача анализа структуры связей между отдельными Web-страницами было обнаружено:

- центральное ядро (28% Web-страниц) - компоненты сильной связности (SCC) или узел галстука, составляют Web-страницы, взаимосвязанные так тесно, что, следуя гиперссылкам, из любой из них в конечном счете можно попасть на любую другую.

- 22% Web-страниц - это "отправные Web-страницы" (IN). Они содержат гиперссылки, которые в конечном счете ведут к ядру, но из ядра к ним попасть нельзя.

- столько же - 22% - "оконечных Web-страниц" (OUT), к которым можно прийти по ссылкам из ядра, но нельзя вернуться назад.

- 22% Web-страниц - отростки - полностью изолированы от центрального ядра: это либо "мысы", связанные гиперссылками со страницами любой другой категории, либо "перешейки", соединяющие две Web-страницы, не входящие в ядро.

Четыре основных множества - более 90% Web-страниц, топологически относящихся к одной компоненте связности и обусловили название модели - Bow Tie ("галстук- бабочка"). В модели учтены и "острова", которые вообще не пересекаются с остальными ресурсами Internet. Единственный способ обнаружить ресурсы этой группы - знать адрес.

Модель Bow Tie

Топология и характеристики модели оказались примерно одинаковыми для различных подмножеств Web-пространства, подтверждая тем самым наблюдение о том, что "Web - это фрактал", т.е. свойства структуры всего Web-пространства Bow Tie также верны и его отдельных подмножеств.

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

© Д. Ландэ, Корпоративные системы 6'2005