Sunday, November 28, 2010

Сингулярное разложение SVD

Есть такая тема в линейной алгебре, которую почему-то упорно игнорируют в институтах. Называется она сингулярное разложение матрицы или, на английском, Singular Value Decomposition. По-сути, сингулярное разложение матрицы это способ разложить матрицу в серию последовательных приближений, тем самым раскрывая её внутреннюю структуру. Используется это во множестве областей таких как text mining, обработка сигналов, сжатие изображений и пр.
Что это такое, я расскажу на примере котировок на бирже. Допустим у нас есть набор котировок в конце дня для нескольких акций.

GAZP AVAZ SBER
2.11 170.16 102.35 35.36
3.11 170.19 103.3 35.65
8.11 174.2 103.95 36.27
9.11 176.1 103.59 37.4
10.11 174.47 100.44 36.9
11.11 172.6 98.4 35.19
12.11 171.88 97.94 33.6
13.11 171.69 97.8 32.95
15.11 171.79 99.2 32.96
16.11 169.57 95.26 29.81
17.11 168.81 97.2 35.8
18.11 170.7 99.66 33.8
19.11 172.2 98.7 33.5

Нас мало интересуют сами котировки, поэтому имеет смысл привести их к общему знаменателю. Будем рассматривать выручку от инвестиций в процентах, по формуле

Ri = 100% * (Vi – Vi-1)/Vi

Это не совсем корректно с финансовой точки зрения, но для наших целей сойдет:

GAZP AVAZ SBER
0.16 0.49 0.02
0.02 0.93 0.83
2.36 0.63 1.74
1.09 -0.35 3.12
-0.93 -3.04 -1.34
-1.07 -2.03 -4.64
-0.42 -0.47 -4.53
-0.11 -0.14 -1.92
0.06 1.43 0.01
-1.29 -3.97 -9.54
-0.45 2.04 20.1
1.12 2.53 -5.59
0.88 -0.96 -0.88


Так вот, математики утверждают, что любую матрицу можно разложить в произведение трех матриц:

A = U*W*VT               (1)

где U и V – ортогональные матрицы, а W – диагональная матрица. Причем, хитрые математики предпочитают когда все отсортировано, поэтому диагональные элементы матрицы W располагаются в порядке убывания. Это и есть сингулярное разложение или SVD. В нашем случае оно будет иметь вид:


0 -0.08 0.02
0.04 -0.12 0.12
0.08 -0.21 -0.71
0.12 0.05 -0.45
-0.07 0.48 -0.11
-0.2 0.26 0.12
-0.19 -0.01 0.13
-0.08 -0.02 0.04
0.01 -0.22 0.19
-0.41 0.45 -0.02
0.82 0.2 0.17
-0.21 -0.58 0.07
-0.04 0.06 -0.41
*
24.51 0 0
0 6.09 0
0 0 2.79

*
0.02 0.15 0.99
-0.4 -0.9 0.14
-0.92 0.4 -0.04

Диагональные элементы wk матрицы W называются сингулярными числами. Столбцы матрицы U называются левыми сингулярными векторами {uk}, и т.к. матрица ортогональна, то эти векторы формируют ортонормированный базис. Т.е. ui*uj = 1 только если i=j, во всех остальных случаях ui*uj = 0. Строки матрицы V называются правыми сингулярными векторами {vk} и формируют другой ортонормированный базис. Теперь мы можем переписать наше равенство (1) в виде:
Ar = Σk=1r(uk * wk * vkt)
Причем Ar гарантированно является наиболее точным приближением матрицы A среди всех матриц с рангом r.

Это очень важное свойство. Теперь, удаляя наименьшие (т.е. последние) сингулярные числа и проводя обратное преобразование, мы можем эффективно убирать шумы из наших данных. На этом построены, например, некоторые способы улучшения и сжатия изображений.

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

Перейдем теперь к более реалистичному примеру. Для него я взял дневные котировки 18 крупных российских компаний за последний год (AFLT, AVAZ, BEGY, GAZP, KMAZ, KRSG, LKOH, LSNG, MDMBP, MMBM, ROSB, ROSN, SBER, SIBN, SNGS, TATN, TRNFP, VTBR)
Аналогично примеру выше, применил операцию SVD для этих котировок и получил разложение A = U*W*VT. Получившиеся матрицы слишком большие чтобы приводить их в тексте, для желающих повторить эксперимент, данные можно взять тут.


Рассмотрим матрицу V, особый интерес в ней для нас представляют первые столбцы. Ведь помните, что в матрице W диагональные значения отсортированы и, стало быть, во всем этом произведении U*W*V Наибольшее значение имеют первые столбцы матрицы U и первые строки матрицы VT (т.е. столбцы матрицы V) Более того, строки матрицы V соответствуют отдельным компаниям (это простое следствие закона произведения матриц) Давайте возьмем первые три столбца полученной матрицы V и отметим соответствующие точки на графике:





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

Матрица U является более интересной с точки зрения временной характеристики. Она отражает то, как вели себя котировки той или иной компании в разное время. Сегодня я не буду углубляться в изучение этой матрицы.










P.S. для расчета сингулярного разложения я использовал Java библиотеку Jama - очень простая, надежная и удобная библиотека, единственный недостаток - не поддерживаются разреженные матрицы, что не значительно в нашей ситуации, но может быть очень важно если SVD используется для анализа текста (об этом я расскажу чуть позже). Кроме того, сингулярное разложение умеют выполнять многие математические пакеты, такие как Mathcad или Mathematica. О другом и, пожалуй, самом известном применении SVD латентно семантическом анализе я напишу в ближайших постах.

Friday, November 19, 2010

Twitter предсказывает котировки на рынке.

Интересная статья о том, как можно предсказать котировки на рынке используя Twitter. Авторы утверждают, что сумели достичь точности более чем 87%, что, очевидно должно сделать их баснословно богатыми. Загвоздка только в одном, если это действительно работает, то как только эта методика стала известно широкой публике, она будет включена во всевозможные инструменты для анализа рынка используемые крупными инвесторами. И это, в свою очередь, очень скоро приведет к снижению эффективности такого инструмента. Я бы на их месте держал такой инструмент в строжайшей тайне и делал бы на нем деньги.

Что же они сделали? Они брали сообщения пользователей в twitter группировали по дням и скармливали алгоритму под названием GPOMS, авторство которого приписывается Google, но сам Google почему-то не дает никакой информации по нему. В результате они получили шесть временных рядов настроений: спокойствие, тревога, уверенность, энергичность, доброта и счастье. Эти ряды они скоррелировали с индексом Dow Jones Industrial Average и выяснилось, что так называемое, «Спокойствие» с точностью 87.6% коррелирует с поведением индекса через 3 дня. Естественно, все предсказания работают только в случае отсутствия неожиданных новостей, когда поведение рынка не подвержено сильному влиянию происходящих или ожидаемых событий.

Что ж, не считая использования некого магического алгоритма GPOMS, в целом статья выглядит интересной и является достойным чтивом для всех кто интересуется data mining-ом. Хотя применение на российском рынке выглядит сомнительным, хотя бы потому, что в США на фондовом рынке играет огромное количество людей, в отличии от Роcсии, где это прерогатива небольшой интересующейся прослойки. А посему и настроение масс вряд ли будут существенно влиять на цены акций. Хотя, кто знает. Давайте писать наши собственные алгоритмы и… держать их в тайне.

Monday, November 15, 2010

Как извлечь полезный текст из HTML. Часть 2

В прошлой заметке я рассказал, как можно извлечь полезный текст из HTML страниц. Решение основывалось на том, что в тех участках HTML-страниц где содержится полезный текст, как правило, очень мало разметки. То есть, величина отношения количества текста к количеству разметки больше некоторого порогового значения. Для своего тестирования я использовал новостные ленты rbc.ru, rbcdaily.ru и свой блог algorithmist.ru.
Этот подход дал неплохие результаты, но к сожалению он дает очень большое количество ложных срабатываний, около 2% на указанных выше сайтах. Улучшить ситуацию нам помогут методы машинного обучения, а именно нейронные сети. Идея заключается в том, чтобы в момент проверки является ли та или иная строчка полезным текстом обратиться к предварительно натренированной нейронной сети и спросить у нее.
В качестве параметров для нейронной сети я выбрал следующие атрибуты:

  • плотность HTML разметки в данной строке
  • длина строки
  • плотность HTML разметки в предыдущей строке
  • длина предыдущей строки
  • плотность HTML разметки в следующей строке
  • длина следующей строки
  • номер строки в документе


Все длины строк предварительно нормированы относительно максимальной длины строки в документе. Номер строки в документе так же нормирован относительно общего количества строк. Таким образом все 7 параметров принимают значения от 0 до 1 включительно.
Для создания нейронной сети я воспользовался библиотечкой Encog
За основу была взята простейшая feed forward нейронная сеть и активирующая функция гиперболический тангенс:



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



Для тренировки нейронной сети было создано два набора данных. Один тренировочный, другой проверочный. Конечно, мне было слишком лениво создавать большое количество данных вручную, поэтому каждый набор состоял всего из 10 статей с разных сайтов.
В результате, получилась нейронная сеть с характеристиками: количество ложных срабатываний 0.4%, количество пропусков события 0%. Конечно, эти результаты сильно зависят от того, какие именно сайты скармливать нейронной сети. Она не 100% универсальная. Но на большинстве новостных лент и блогов ведет себя неплохо выдавая внятное содержимое практически для любой страницы.
Думаю, что если требуется получить максимально точный результат, то лучше тренировать отдельные нейронные сети на каждый веб сайт. На практике это гораздо проще чем писать специальный HTML парсер и поддерживать его при малейших изменениях сайта.
Как и в прошлый раз, кнопка для желающих протестировать:





Как извлечь полезный текст из HTML. Часть 1

Задача на первый взгляд может показаться тривиальной: извлечь полезный текст из HTML страниц с различных сайтов, например новости с новостных лент. На практике, однако, реализация подобной функциональности, как правило, оканчивается написанием кучи парсеров заточенных под конкретные сайты. Поддерживать такие парсеры – сущий кошмар, особенно если система должна работать в автономном режиме долгое время. Хотелось бы иметь универсальное решение. Сегодня я опишу один из возможных вариантов решения этой проблемы.

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

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

Для нашего примера я взял статью с rbcdaily.ru Можно было бы использовать версию для печати, но в целях чистоты эксперимента, остановимся на стандартной версии. Текст был разбит на строки и для каждой строки посчитано количество HTML-тегов разметки и количество прочего текста.

  
boolean isMarkup = false;
int markupCnt = 0;
for (int i = 0; i < sline.length(); i++) {
char ch = sline.charAt(i);
if (ch == '<') {
isMarkup = true;
}
if (isMarkup) {
markupCnt++;
}
if (ch == '>') {
isMarkup = false;
}
}

Красной линией на графике обозначается длина строки, синей линией количество не-HTML текста. В целях улучшения визуализации, показаны данные усредненные по 5 строк.



Не слишком понятная картина, правда? Некий пик между 89 и 100, а в остальном, много пиков и провалов. Беглый взгляд в HTML и становится понятно, что в нашем случае он очень сильно засорен JavaScipt-ом и HTML-комментариями. Для улучшения результатов, стоит их удалить. Это сделать достаточно просто, предварительно обработав HTML. После этого, результаты становятся более очевидными:



У нас четко нарисовался пик с основным текстом и куча мусора, который можно смело выбрасывать в корзину. Простейшим способам выбрать где здесь текст, а где мусор, это отобрать строки в которых величина отношения длины HTML разметки к длине строки меньше определенного порогового значения. В нашем случае я взял 0.3 и получил на удивление хорошие результаты



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

Протестировать результаты такого фильтра можно тут, введите адрес страницы которую бы вы хотели отфильтровать и нажмите старт.




Saturday, November 13, 2010

Об округлении, банкирах и математиках

Казалось бы, что может быть проще, округлить дробь до целого? И чего тут обсуждать, нас всех в школе учили это делать. Однако… берем Java:
        
System.out.println(Math.round(2.5));
System.out.println(Math.round(3.5));

Получаем
3
4
Всё правильно? Да, так нас учили в школе, меня по-крайней мере. Советский союз - колыбель инженеров, а это стандартное математическое округление.
Но, теперь возьмем C#
  
Console.WriteLine(Math.Round(2.5));
Console.WriteLine(Math.Round(3.5));

Получаем
2
4
Оп-п-паньки. Неожиданно, правда? Получается что в C# округление работает не так как в Java. Лезем в документацию и читаем:

"Поведение этого метода соответствует стандарту IEEE-754, раздел 4. Этот способ округления иногда называют округлением до ближайшего или банковским округлением. Минимизирует ошибки округления, происходящие от постоянного округления среднего значения в одном направлении."

И ведь действительно, есть такой стандарт и действительно так принято. США – колыбель банкиров. И говорят, их так учат округлять в школе.

Но вернемся к нашему программированию. Чтобы сделать всё еще более запутанным, попробуем вот такой Java код
  
System.out.println(new DecimalFormat("0").format(2.5));
System.out.println(new DecimalFormat("0").format(3.5));

В результате
2
4

Вот такая вот петрушка, а теперь представьте что есть приложение где серверная часть написана на Java а клиентская на .Net и какие прелестные и неуловимые баги это может породить. Или пусть даже всё написано на Java, но например значения в таблице мы форматируем с помощью DecimalFormat а «итого» считаем с помощью Math.round(). Счастливых вам ночей с дебаггером, дорогие программисты…

К счастью, в .Net метод Round перегружен Round(Decimal) / Round(Decimal, MidpointRounding) и при необходимости можно явно указать способ округления. Таким образом, привести C# к Java достаточно просто:
  
Console.WriteLine(Math.Round(2.5, MidpointRounding.AwayFromZero));
Console.WriteLine(Math.Round(3.5, MidpointRounding.AwayFromZero));

К сожалению, я не знаю простого способа привести Java к C#. Нужно либо использовать BigDecimal в конструктор которого передать MathContext с типом округления ROUND_HALF_EVEN либо писать собственный метод.

Friday, November 12, 2010

Динамическое программирование на Haskell. Часть 3

В продолжение моих предыдущих постов (1, 2) о замечательном языке программирования Haskell. Вот мы решили задачу, получили программу, которую можно запускать и увидеть результат. Но что же со временем выполнения? А как собственно измерить время выполнения программы или части программы в Haskell?
Эта задача оказывается сложнее чем в императивных языках. И причиной тому, склонностью Haskell к ленивым вычислениям. Haskell настолько ленив, что не будет вычислять ничего до тех пор пока в этом не возникнет реальной необходимости. С одной стороны это открывает перед нами такие возможности как бесконечные массивы и бесконечная рекурсия. А с другой стороны, это создает некоторые трудности для нас, привыкших к императивному мышлению.
Итак, поехали. Имеется программа:
import Array

change :: [Int] -> Int -> Int
change xs n = dp!n
where
dp = listArray (0,n) [ cell i | i<-[0..n]]
cell 0 = 0
cell i = succ$minl [dp!(i-x)| x<-xs, i>=x]

minl :: [Int] -> Int
minl [] =  0
minl xs =  minimum xs


В императивном языке, можно было бы просто написать:
timer :: Int -> IO()
timer n = do
t0 <- getCPUTime
let c = change [1,2,5,10,50] n –(1)
t1 <- getCPUTime
putStrLn $ show $ div (t1-t0) cpuTimePrecision
Но в нашем случае, это не работает. Результат будет все время 0, потому что Haskell заметит, что переменная c не нужна и, стало быть, вычислять её не стоит. Чтобы все-таки получить результат, необходимо модифицировать строчку помеченную (1), получим следующую программу:
timer :: Int -> IO()
timer n = do
t0 <- getCPUTime
return $! change [1,2,5,10,50] n  -- (1)
t1 <- getCPUTime
putStrLn $ show $ div (t1-t0) cpuTimePrecision
Результат работы этой программы: 1000000 : 255656 100000 : 4093 10000 : 187 1000 : 15 Как мы видим время выполнения далеко от полиномиального, как предполагается в динамическом программировании. И, к сожалению, большая часть этого времени тратится в сборщике мусора. В чем легко убедиться запустив программу с ключиком: +RTS –sstderr %GC time 97.8% Проблема в том, что наша программа выделяет слишком много слишком много массивов. К счастью, решение есть. Пусть и несколько более запутанное:
change :: [Int] -> Int -> Int
change xs n = cs!!n
where
cs = 0 : (map succ (foldl1 minimize (map (\x -> replicate (x-1) maxBound ++ cs) xs)))

minimize [] [] = []
minimize (x:xs) (y:ys) = (min x y) : minimize xs ys


Что здесь происходит? Мы создаем ленивый массив cs в котором храним все решения задачи для заданного набора монет. Как вычисляются значения в этом массиве? Для этого мы создаем по ленивому массиву для каждой монеты, очевидно что если величина монеты X то первые X-1 значение в этом массиве будут не определены. Ведь мы не можем разменять сумму монетой большего достоинства чем сама сумма. Чтобы не усложнять вычисления, вместо неопределенности мы вбиваем самое большое возможное значение maxBound. Оставшиеся значения в этом массиве заполняются результирующим массивом (вот она прелесть Хаскеля, массив заполняет сам себя!)
Дальнейшее просто, каждый элемент массива cs равен минимальному значению из всех соответствующих элементов частных массивов плюс единица.

Запускаем еще раз наш таймер и смотрим время выполнения:

1000000 : 8656
100000 : 718
10000 : 62
1000 : 0

Мы не только добились полиномиального времени выполнения, как обещает динамическое программирование, но и увеличили скорость работы алгоритма на порядок.

Thursday, November 11, 2010

Topcoder MM DigitsPattern

Подошел к концу очередной Topcoder MM, задачка DigitsPattern, что ж этот матч был пожалуй самым неоднозначным из всех что мне доводилось видеть. Здесь было всё, и бурный старт большого числа участников в начале и осознание того, что что-то не так в середине и озарение уже ближе к концу. Концовка же была самой знаменательной. Такого еще не бывало, аж 46 участников разделили между собой первое место.
Видя такое единодушие среди участников невольно задумываешься, а нет ли здесь случайно точного решения. Какого-нибудь динамического или жадного алгоритма. На поиски этого точного решения я и потратил чуть меньше недели. Скажу сразу, не нашел. Может быть оно и есть, вот только мое решение было далеко от идеального когда оно тоже поднялось на первое место. Что же это, слабость тестовых данных или сама задачка такова, что её способны решить столь большое число участников. Я надеюсь, что первое, но лучше подождем финальных результатов, они либо опровергнут либо подтвердят мою гипотезу.
Задачака звучала так (за полной формулировкой обращайтесь к исходникам): Вам требуется последовательно заполнить поле в клетку различными цифрами. Когда вы зполняете некоторую свободную клетку, она получает значение 1, все соседние с ней клетки получают +1 к своему значению, если они заполнены. В качестве входного параметра вам дается целевой шаблон и ваша цель заполнить как поле как можно ближе к этому шаблону. Близость к шаблону определяется как сумма абсолютной величины отклонения значения клетки в шаблоне от значения полученного в результате заполнения. Есть еще особые правила формирования шаблона, задаются размеры поля и способ кодирования ответа и входных параметров, все это интересующиеся могут почитать в исходном тексте.
Первая идея которая пришла мне в голову заключалась в том, чтобы нумеровать клетки в порядке обратном их величине в шаблоне. Это очевидное и безумно простое решение дало бы в итоге ~200-ое место. Любые попытки перебора, перестановок и прочих манипуляций с этим подходом едва ли вывели бы даже в первую сотню.
Озарением стало, что можно просто последовательно отбирать клетки с минимальным значением разности «максимально возможное значение клетки» - «требуемое значение клетки». Максимально возможное значение для данной клетки равно количеству не заполненных на данный момент времени соседей + 1. Очень простая формула и на уливление хороший результат. Это решение подняло меня в топ 100. Следом была простое и очевидное изменение: немного менять порядок выбираемых клеток, решение за решением, это дало мне 50-ое место.
Остаток времени я посвятил нежному и внимательному тюнингу решения: добавил кэш, чтобы отслеживать состояния в которых уже был. Добавил дополнительную сортировку для выбираемых клеток (теперь уже они выбирались не просто с минимальным значением разности но и с учетом соседних клеток). Эти манипуляции вывели меня на 1-ую строчку предварительного рейтинга.
Выход на первую строчку охладил интерес к дальнейшему решению, наверное зря. Ведь на собственной базе данных из 1000 тестов, увеличив время решения в 10 раз, я легко убедился, что мое решение не оптимально как минимум в 17 случаях. Но желания что-то подкручивать и искать дальнейшие оптимизации уже не было.

Интересные находки:
Класс java.util.BitSet, когда-то я о нем читал в книжках, но до сих пор на практике не приходилось использовать. В этой задачке он пригодился для кэширования. BitSet служил ключем для кэша. К сожалению, вскоре по результатам профайлинга мне пришлось сделать собственную реализацию FastBitSet потому что скорость работы стандартной была явно не удовлетворительной. Конечно это связанно с расширенным функционалом стандартной реализации и с ограниченными требованиями в моем случае.

Tuesday, November 9, 2010

Рисуем графы на Java

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

Graphviz



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


JGraph



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


Jung




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

Prefuse



Это гораздо больше чем библиотека для визуализации графов. К сожалению разработка проекта заброшена, последняя версия на сайте beta от 2007-го года доступна только в виде исходников. Впрочем, исходники собрались без проблем. А вот с документацией, увы, проблема, на сайте всё ограничивается оглавлением, большинство страниц содержат печальное «Coming soon...». Было бы здорово если бы кто-нибудь взялся и продолжил развитие этого продукта.

Итого, мой выбор остановился на Jung. Среди всех перечисленных вариантов это единственный удовлетворял основным критериям: бесплатный и на Java. Жаль, что выбор библиотек такого рода столь ограничен.