Карта книг Amazon.com

25 марта 2011 г.

Недавно я прочитал страничку Криса Харрисона (Chris Harrison) про карту книг, которые возможно купить на Amazon. Под картой здесь понимается изображение на котором каждая отдельная точка соответствует какой-либо конкретной книге. Соседние точки — это те книги, которые пользователи покупают вместе с данной.

Для построения карты, Крис взял данные о книгах у Аарона Швартца (Aaron Swartz), который написал кроулер на Python. Этот датасет содержал информацию о 730 000 книг и их связности в терминах рекомендаций Amazon. Как только у вас есть Amazon Web Services Developer ID, вы можете использовать API для доступа к базе данных Amazon. Тем не менее, есть пара ограничений: первое, возможно получить не более 10 книг похожих на данную, и второе, нельзя делать запросы чаще чем раз в секунду.

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

Код краулера, процесс построения картинки и результат под катом.

Построение датасета

Вот моя реализация на Perl. Две переменные необходимы для удачного старта — Amazon Developer ID и ASIN — уникальный номер товара на Amazon, в данном случае книги, с которой начнется процесс сбора данных.

#!/usr/bin/perl

use Encode;
require LWP::UserAgent;
use Thread::Queue;
use DBI;

# setup
my $aws_id = '...';
my $asin_start = '0201514591';
# ARM
#

# request template
sub make_similarity_request
{
return 'http://ecs.amazonaws.com/onca/xml?Service=AWSECommerceService&AWSAccessKeyId=' . $aws_id . '&Operation=SimilarityLookup&ResponseGroup=BrowseNodes&ItemId=' . $_[0];
}

# create useragent and request queue
my $ua = LWP::UserAgent->new;
$ua->timeout(10);
$ua->agent('amazon-crawl/0.1');
$ua->env_proxy;

my $queue = new Thread::Queue;
# Try to restore queue from file
my $opened = 1;
open FILE, "<queue.txt" or ($opened = 0);
if($opened == 1) {
print «Found 'queue.txt', restoring queue.\n»;
while() { $queue->enqueue($_); }} else { $queue->enqueue($asin_start); # add starting ASIN
}
# read categories names to search for
open FILE, "<categories.txt" or die $!;
my @categories = ;
foreach (@categories) { $_ =~ s/^\s+|\s+$//g; }
my @in_categories;
foreach (@categories) { $in_categories{$_} = 1; }
close FILE;
# check if we have certain ASIN in the base ot queue
sub not_in_base{ my $asin = $_[0];
my $dbh = $_[1];
my $all = $dbh->selectall_arrayref(«SELECT id FROM books WHERE asin='$asin'»);
if(@$all > 0) { return 0; } return 1;} sub not_in_queue{ return 1;}
# sqlite connection
my $dbh = DBI->connect(«dbi:SQLite:dbname=amazon.db», "", "", {AutoCommit => 1, PrintError => 1});
if($dbh) { print 'sqlite3 -> connected' . "\n";
}else {
print 'sqlite3 -> connection failed' . "\n";
exit;}
# get count of books in the base
my $bib = $dbh->selectall_arrayref(«SELECT * FROM books»);
my $books_in_base = @$bib;
print «Base contains ». $books_in_base . " books.\n";
# Deal Ctrl-C correctly
$SIG{INT} = \&endtsk;
sub endtsk { $SIG{INT} = \&endtsk;
# See ``Writing A Signal Handler''
print "\nCtrl-C caught, disconnecting from base, saving queue.\n";
$dbh->disconnect();
open FILE, "> queue.txt" or die $!;
while($queue->pending) { print FILE $queue->dequeue . "\n"; } close FILE;
exit;}
# perform requests
print 'Crawling begins...' . "\n";while($queue->pending) {
# get xml with similarity info
my $current_asin = $queue->dequeue;
my $response = $ua->get(make_similarity_request($current_asin));
if($response->code == 503) { print «Going to fast, pausing.\n»;
$queue->enqueue($current_asin); sleep 2; next;
} elsif($response->code != 200) { next; }
my $answer = encode('utf8', $response->decoded_content);
my @item;
if(@item = ($answer =~ /(.*?)<\/Item>/gsci)) { for $it (@item) { my @nodes;
my @asins;
# similar item asin & category
my $asin = '';
my $category = '';
if(@asins = ($it =~ /(.*?)<\/ASIN>/gsci)) { $asin = $asins[0];
if(@nodes = ($it =~ /\<Name\>(.*?)\<\/Name\>/gsci)) {  for(my $i = 0; $i < @nodes; $i++)
{
#   print «Items: $nodes[$i],$nodes[$i + 1],$nodes[$i + 2]\n»; # Ensure that this category is under Books->Subject->
if(($nodes[$i + 1] eq «Subjects») && ($nodes[$i + 2] eq «Books»)) {   my $node = $nodes[$i];
$node =~ s/&/&/gsci;
# correct '&'
$node =~ s/^\s+|\s+$//g;
# trim
$node =~ s/\'//gi;
if($in_categories{$node} == 1) {
# found some node, that we know, so break
$category = $node;
last;
}
} else {
next;
}  } } else {
print «Not found.\n»;} }
if(($asin ne '') && ($category ne '')) { if((not_in_queue($asin)) && (not_in_base($asin, $dbh))) { print «QUEUED: $asin - $category\n»; $queue->enqueue($asin); $books_in_base++; $dbh->do(«insert into books (id, asin, category) values (NULL,'$asin','$category')»); $dbh->do(«insert into books_relations (id, asin_from, asin_to) values (NULL,'$current_asin','$asin')»); } else { print «Analyzed this item!\n»; } }
# we have «similar» ASIN, add it to queue, if we haven't it in the base or queue already } }
# insert into 'books' table asin and it's category
# damn «one request per second» rule
my @pend = $queue->pending;
print "@pend items pending, $books_in_base in base.\n";
#select(undef, undef, undef, 0.25);}
# sqlite disconnection
$dbh->disconnect();
print «crawled.\n»;

API Amazon отвечает на запрос при помощи XML. Запрос «SimilarityLookup» возвращает XML с ASINами книг и их категориями (т.е. тематика, в случае книг). Для обработки ответа я использовал регулярные выражения, так как этой быстрее чем полный разбор XML и этого было достаточно. Вся необходимая информация для построения карты сохраняется в базу данных — sqlite3. Она содержит две таблицы — первая хранит информацию о книгах — ASIN, категория и название книги, вторая — хранит связи между книгами, описанными в первой таблице. Таблицы описаны так:

CREATE TABLE books (
id INTEGER PRIMARY KEY,
asin TEXT,
category TEXT,
name TEXT);
CREATE TABLE books_relations (
id INTEGER PRIMARY KEY,
asin_from TEXT,
asin_to TEXT);

Также скрипт сохраняет ASINы книг по которым необходимо послать запрос, в файл, для сохранения своего прогресса — в случае если он будет завершен, например по Ctrl-C.

Я запускал этот скрипт в течение нескольких ночей и собрал свой датасет о 145 000 книг.

Расстановка книг

Для построения карты был применен следующий принцип:

Берем стартовую книгу. В данном случае С++ ARM, B. Stroupstrup. Это текущая книга.
Поместим цветную точку с координатами (0,0) на изображение. Цвет соответствует тематике.
Взять похожие книги из базы данных. Поместить цветные точки, соответствующие этим книгам вокруг текущей. Опять же, их цвета соответствуют тематике этих книг.
Каждая из выбранных книг выбирается «текущей» и процесс начинается с начала.

Основная проблема здесь заключается в том, что у каждой точки не более 8 соседей, хотя необходимо разместить до 10. На самом деле каждая текущая точка в среднем будет иметь менее 8 вакантных мест, т.к. часть из них уже занята за счет предыдущих итераций. Поэтому, в любом случае будет некоторое нежелательное смещение, картинка не будет соответствовать реальности на 100%.

Для удобства в процессе сбора данных, тематикам были присвоены номера. Была написана еще одна программа (уже на С++) которая берет файл базы данных, описанной выше, а на выход выдает множество кортежей, каждый из которых состоит из координат и номера тематики:

0, 0, 9
1, 0, 9
0, 1, 9
-1, 0, 9
.. .

В данном примере, в точке (0, 0) есть книга с тематикой номер 9. Вокруг нее располагаются соседи из той же тематики.

Моя реализация на С++ при помощи библиотеки SOCI (для работы с sqlite3 бэкэндом) располагает точки со средним смещением (2, 2), что значит что в среднем соседняя книга располагается не далее чем на ~3 пикселя дальше от той книги, соседом которой она должна была быть, если бы были вакантные места.

Построение изображения карты

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

Ожидаемые вещи

«Computers & Internet», «Bussiness & Investitions», «Nonfiction» и «History» — это широко распространённые жанры. Они тесно связаны между собой, а также практически со всеми другими категориями.
Тематики «Computers & Internet» и «Religion & Spirituality» не связаны, за исключением косвенной связности через жанры «Health, Mind & Body» (G8) или «Entertainment». Ричард Столлман мог бы это исправить.
Тематика «Literature & Fiction» (D7, E7) связана с большим количество других категорий, но при этом достаточно локализована

Интересные особенности

H8, I8 — тематика «Comics & Graphics Novels» тесно связана с тематикой «Religion & Spirituality»
G8, H8, I8 – тематика «Religion & Spirituality» очень популярна (и занимает большую площать), но вполне самодостаточна, т.е. люди редко интересуются чем-то И религией.
C2 — Есть некоторое количество книг на границе между тематикой «Gays & Lesbians» и «Computer & Internet». Не могу представить о чем эти книги, но в базе данных все еще хранятся ASINы книг и возможно восстановить какая книга где расположилась.
E9 – тематика «Sport» по большей части связана с «Bussiness & Investiotions».

Теги: рубрика Программирование