Headroom.js — библиотека, реализующая паттерн Quick Return для экономии вертикального пространства экрана

Одна из типичных проблем, возникающих перед разработчиком интерфейса для устройств с альбомной ориентацией экрана (особенно если у них маленькая диагональ) — недостаток вертикального пространства. Довольно популярный элемент — горизонтальная панель с кнопками или меню, зафиксированная над основным контентом, даёт быстрый доступ к нужным функциям, но занимает дефицитное место. Если не фиксировать её, а позволить прокручивать вместе со страницей, то при необходимости воспользоваться одной из кнопок, пользователю придётся возвращаться на самый верх. Один из шаблонов дизайна интерфейсов для решения этой проблемы получил название Quick Return (быстрый возврат) — при начале прокрутки вниз панель уходит за пределы экрана, но выдвигается вновь, как только начинается прокрутка вверх, независимо от того, в какой части страницы находится пользователь.

Принцип работы библиотеки Headroom.js, реализующей этот шаблон, очень прост — в ответ на начало скроллинга меняются CSS-классы панели, делая её видимой или невидимой. У библиотеки есть API как для чистого JavaScript, так и для jQuery/Zepto и AngularJS.

Использование

Чистый JS:

// находим элемент var myElement = document.querySelector("header"); // создаём экземпляр Headroom, передавая в конструктор найденный элемент var headroom  = new Headroom(myElement); // инициализируем экземпляр headroom.init(); 

jQuery/Zepto:

// Проще некуда! // init() вызывается неявно $("header").headroom(); 

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

<!-- выбирается элемент $("[data-headroom]") --> <header data-headroom> 

AngularJS:

<header headroom></header> <!-- или --> <headroom></headroom> <!-- или с опциями --> <headroom tolerance='0' offset='0' classes="{pinned:'headroom--pinned',unpinned:'headroom--unpinned',initial:'headroom'}"></headroom> 

Опции

Для управления поведением Headroom.js предусмотрены опции. Их немного, а структура объекта опций выглядит так:

{     // вертикальное смещение в пикселях, при котором панель "отцепляется"     offset : 0,     // допуск в пикселях, в пределах которого состояние не меняется     tolerance : 0,     // допуск также можно задать отдельно для прокрутки вверх или вниз     tolerance : {         down : 0,         up : 0     },     // Применяемые классы CSS     classes : {         // при инициализации элемента         initial : "headroom",         // при прокрутке вверх         pinned : "headroom--pinned",         // при прокрутке вниз         unpinned : "headroom--unpinned",         // выше вертикального смещения         top : "headroom--top",         // ниже вертикального смещения         notTop : "headroom--not-top"     },     // callback при фиксации элемента, здесь и далее this указывает на элемент     onPin : function() {},     // callback при отцеплении     onUnpin : function() {},     // callback при попадании выше вертикального смещения     onTop : function() {},     // callback при попадании ниже вертикального смещения     onNotTop : function() {} } 

Пример использования стилей

.headroom {     transition: transform 200ms linear; } .headroom--pinned {     transform: translateY(0%); }  .headroom--unpinned {     transform: translateY(-100%); } 

Вот и всё. Поиграть с параметрами и стилями можно на демонстрационной странице. Библиотека распространяется под лицензией MIT. Автор Headroom.js — веб -разработчик Ник Вильямс, ему также принадлежит ещё один весьма популярный проект — библиотека enquire.js для работы с media queries.

ссылка на оригинал статьи http://habrahabr.ru/post/224787/

Эффект последней строки

Copy-Paste
Я изучил множество ошибок, возникающих в результате копирования кода. И утверждаю, что чаще всего ошибки допускают в позднем фрагменте однотипного кода. Ранее я не встречал в книгах описания этого феномена, поэтому и решил о нём написать. Я назвал его «эффектом последней строки».

Введение

Меня зовут Андрей Карпов. Я занимаюсь необычным занятием. Я исследую программный код приложений с помощью статических анализаторов и описываю найденные ошибки и недочёты. Занимаюсь я этим из-за прагматичных и корыстных побуждений. Так наша компания рекламирует инструменты PVS-Studio и CppCat. Нашли ошибки. Описали в статье. Привлекли внимание. Profit. Но сегодня статья не про анализаторы.

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

База уникальна! Сейчас она содержит около 1500 фрагментов кода с ошибками. Она ждёт людей, которые смогут выявить в этих ошибках закономерности. Это может послужить основой многих исследований и материалов для книг и статей.

Специально я не делал никаких исследований накопленного материала. Тем не менее одна закономерность так явно проявляет себя, что я решил изучить её подробнее. В статьях мне часто приходится писать «обратите внимание на последнюю строку». Я решил, что это не спроста.

Эффект последней строки

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

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

Простой короткий пример:

inline Vector3int32& operator+=(const Vector3int32& other) {   x += other.x;   y += other.y;   z += other.y;   return *this; }

Обратите внимание на строчку «z += other.y;». В ней забыли поменять ‘y’ на ‘z’.

Пример кажется искусственным. Но этот код взят из реального приложения. Далее я убедительно покажу, что это очень частая и распространенная ситуация. Именно так и выглядит «эффект последней строки». Человек чаще всего допускает ошибку в самом конце внесения однотипных исправлений.

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

Теперь немного цифр.

Изучив базу ошибок, я выявил 84 фрагмента кода, которые, как мне кажется, были написаны с использованием Copy-Paste. Из них 41 фрагмент содержит ошибку где-то в середине скопированных блоков. Вот пример:

strncmp(argv[argidx], "CAT=", 4) && strncmp(argv[argidx], "DECOY=", 6) && strncmp(argv[argidx], "THREADS=", 6) && strncmp(argv[argidx], "MINPROB=", 8)) {

Длина строки «THREADS=» не 6, а 8 символов.

В остальных 43 случаях ошибка была найдена в самом последнем скопированном блоке.

На первый взгляд, число 43 совсем немного больше 41. Но учтите, что однотипных блоков бывает достаточно много. И ошибка может быть в первом, втором, пятом или даже в десятом блоке. Получаем относительно ровное распределение ошибок в блоках и резкий скачок в конце.

В среднем я взял, что количество однотипных блоков равно 5.

Получается, что на первые 4 блока приходится 41 ошибка. Или около 10 ошибок на один блок.

На последний пятый блок приходится 43 ошибки!

Для наглядности можно построить вот такой приблизительный график:

Рисунок 1. Приблизительный график количества ошибок в пяти блоках похожего кода.

Рисунок 1. Приблизительный график количества ошибок в пяти блоках похожего кода.

Получается:

Вероятность допустить ошибку в последнем скопированном блоке в 4 раза больше, чем в любом другом.

Каких-то грандиозных выводов я из этого не делаю. Просто интересное наблюдение. С практической точки зрения полезно знать о нём. Тогда можно заставить себя не расслабляться в самом конце.

Примеры

Осталось убедить читателей, что это не мои фантазии, а реалии жизни. Для этого я продемонстрирую примеры, которые подтвердят мои слова.

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

Source Engine SDK

inline void Init( float ix=0, float iy=0,                   float iz=0, float iw = 0 )  {   SetX( ix );   SetY( iy );   SetZ( iz );   SetZ( iw ); }

В конце нужно было вызвать функцию SetW().

Chromium

if (access & FILE_WRITE_ATTRIBUTES)   output.append(ASCIIToUTF16("\tFILE_WRITE_ATTRIBUTES\n")); if (access & FILE_WRITE_DATA)   output.append(ASCIIToUTF16("\tFILE_WRITE_DATA\n")); if (access & FILE_WRITE_EA)   output.append(ASCIIToUTF16("\tFILE_WRITE_EA\n")); if (access & FILE_WRITE_EA)   output.append(ASCIIToUTF16("\tFILE_WRITE_EA\n")); break;

Совпадает последний и предпоследний блок.

ReactOS

if (*ScanString == L'\"' ||     *ScanString == L'^' ||     *ScanString == L'\"')

Multi Theft Auto

class CWaterPolySAInterface { public:     WORD m_wVertexIDs[3]; }; CWaterPoly* CWaterManagerSA::CreateQuad (....) {   ....   pInterface->m_wVertexIDs [ 0 ] = pV1->GetID ();   pInterface->m_wVertexIDs [ 1 ] = pV2->GetID ();   pInterface->m_wVertexIDs [ 2 ] = pV3->GetID ();   pInterface->m_wVertexIDs [ 3 ] = pV4->GetID ();   .... }

Последняя строчка написана по инерции и является лишней. В массиве всего 3 элемента.

Source Engine SDK

intens.x=OrSIMD(AndSIMD(BackgroundColor.x,no_hit_mask),                 AndNotSIMD(no_hit_mask,intens.x)); intens.y=OrSIMD(AndSIMD(BackgroundColor.y,no_hit_mask),                 AndNotSIMD(no_hit_mask,intens.y)); intens.z=OrSIMD(AndSIMD(BackgroundColor.y,no_hit_mask),                 AndNotSIMD(no_hit_mask,intens.z));

В последней строке забыли заменить «BackgroundColor.y» на «BackgroundColor.z».

Trans-Proteomic Pipeline

void setPepMaxProb(....) {     ....   double max4 = 0.0;   double max5 = 0.0;   double max6 = 0.0;   double max7 = 0.0;   ....   if ( pep3 ) { ... if ( use_joint_probs && prob > max3 ) ... }   ....   if ( pep4 ) { ... if ( use_joint_probs && prob > max4 ) ... }   ....   if ( pep5 ) { ... if ( use_joint_probs && prob > max5 ) ... }   ....   if ( pep6 ) { ... if ( use_joint_probs && prob > max6 ) ... }   ....   if ( pep7 ) { ... if ( use_joint_probs && prob > max6 ) ... }   .... }

В последнем условии забыли заменить «prob > max6» на «prob > max7».

SeqAn

inline typename Value<Pipe>::Type const & operator*() {   tmp.i1 = *in.in1;   tmp.i2 = *in.in2;   tmp.i3 = *in.in2;   return tmp; }

SlimDX

for( int i = 0; i < 2; i++ ) {   sliders[i] = joystate.rglSlider[i];   asliders[i] = joystate.rglASlider[i];   vsliders[i] = joystate.rglVSlider[i];   fsliders[i] = joystate.rglVSlider[i]; }

В последней строке надо было использовать массив rglFSlider.

Qt

if (repetition == QStringLiteral("repeat") ||     repetition.isEmpty()) {   pattern->patternRepeatX = true;   pattern->patternRepeatY = true; } else if (repetition == QStringLiteral("repeat-x")) {   pattern->patternRepeatX = true; } else if (repetition == QStringLiteral("repeat-y")) {   pattern->patternRepeatY = true; } else if (repetition == QStringLiteral("no-repeat")) {   pattern->patternRepeatY = false;   pattern->patternRepeatY = false; } else {   //TODO: exception: SYNTAX_ERR }

В самом последнем блоке забыли про ‘patternRepeatX’. Должно быть:

pattern->patternRepeatX = false; pattern->patternRepeatY = false;

ReactOS

const int istride = sizeof(tmp[0]) / sizeof(tmp[0][0][0]); const int jstride = sizeof(tmp[0][0]) / sizeof(tmp[0][0][0]); const int mistride = sizeof(mag[0]) / sizeof(mag[0][0]); const int mjstride = sizeof(mag[0][0]) / sizeof(mag[0][0]);

Переменная ‘mjstride’ будет всегда равна единицы. Последняя строчка должна быть такой:

const int mjstride = sizeof(mag[0][0]) / sizeof(mag[0][0][0]);

Mozilla Firefox

if (protocol.EqualsIgnoreCase("http") ||     protocol.EqualsIgnoreCase("https") ||     protocol.EqualsIgnoreCase("news") ||     protocol.EqualsIgnoreCase("ftp") ||          <<<---     protocol.EqualsIgnoreCase("file") ||     protocol.EqualsIgnoreCase("javascript") ||     protocol.EqualsIgnoreCase("ftp")) {          <<<---

Подозрительная строка «ftp» в конце. С этой строкой уже сравнивали.

Quake-III-Arena

if (fabs(dir[0]) > test->radius ||     fabs(dir[1]) > test->radius ||     fabs(dir[1]) > test->radius)

Не проверили значение из ячейки dir[2].

Clang

return (ContainerBegLine <= ContaineeBegLine &&         ContainerEndLine >= ContaineeEndLine &&         (ContainerBegLine != ContaineeBegLine ||          SM.getExpansionColumnNumber(ContainerRBeg) <=          SM.getExpansionColumnNumber(ContaineeRBeg)) &&         (ContainerEndLine != ContaineeEndLine ||          SM.getExpansionColumnNumber(ContainerREnd) >=          SM.getExpansionColumnNumber(ContainerREnd)));

В самом конце выражение «SM.getExpansionColumnNumber(ContainerREnd)» сравнивается само с собой.

MongoDB

bool operator==(const MemberCfg& r) const {   ....   return _id==r._id && votes == r.votes &&          h == r.h && priority == r.priority &&          arbiterOnly == r.arbiterOnly &&          slaveDelay == r.slaveDelay &&          hidden == r.hidden &&          buildIndexes == buildIndexes; }

Забыли в самом конце про «r.».

Unreal Engine 4

static bool PositionIsInside(....) {   return     Position.X >= Control.Center.X - BoxSize.X * 0.5f &&     Position.X <= Control.Center.X + BoxSize.X * 0.5f &&     Position.Y >= Control.Center.Y - BoxSize.Y * 0.5f &&     Position.Y >= Control.Center.Y - BoxSize.Y * 0.5f; }

В последней строке забыли сделать 2 правки. Во-первых, надо заменить ">=" на "<=. Во-вторых, заменить минус на плюс.

Qt

qreal x = ctx->callData->args[0].toNumber(); qreal y = ctx->callData->args[1].toNumber(); qreal w = ctx->callData->args[2].toNumber(); qreal h = ctx->callData->args[3].toNumber(); if (!qIsFinite(x) || !qIsFinite(y) ||     !qIsFinite(w) || !qIsFinite(w))

В самом последнем вызове функции qIsFinite, нужно использовать в качестве аргумента переменную ‘h’.

OpenSSL

if (!strncmp(vstart, "ASCII", 5))   arg->format = ASN1_GEN_FORMAT_ASCII; else if (!strncmp(vstart, "UTF8", 4))   arg->format = ASN1_GEN_FORMAT_UTF8; else if (!strncmp(vstart, "HEX", 3))   arg->format = ASN1_GEN_FORMAT_HEX; else if (!strncmp(vstart, "BITLIST", 3))   arg->format = ASN1_GEN_FORMAT_BITLIST;

Длина строки «BITLIST» не 3, а 7 символов.

На этом остановимся. Думаю, приведённых примеров более чем достаточно.

Заключение

В этой статье вы узнали, что при использовании Copy-Paste вероятность допустить ошибку в последнем скопированном блоке в 4 раза выше, чем в любом другом.

Эта особенность психологии человека, а не его профессиональных навыков. В статье мы увидели, что к тяге к ошибкам в конце склонны даже высококвалифицированные разработчики таких проектов, как Clang или Qt.

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

Эта статья на английском

Если хотите поделиться этой статьей с англоязычной аудиторией, то прошу использовать ссылку на перевод: Andrey Karpov. The Last Line Effect.

Прочитали статью и есть вопрос?

Часто к нашим статьям задают одни и те же вопросы. Ответы на них мы собрали здесь: Ответы на вопросы читателей статей про PVS-Studio и CppCat, версия 2014. Пожалуйста, ознакомьтесь со списком.

ссылка на оригинал статьи http://habrahabr.ru/company/pvs-studio/blog/224783/

Gitchain: смесь Гитхаба с Биткоином

Канадский программист Юрий Рашковский решил объединить две популярные технологии — систему контроля версий Git и распределённую БД Биткоин. Его проект Gitchain, который недавно успешно собрал на Кикстартере запланированные 10 000 долларов, по задумке автора позволит сделать систему контроля версий Git по-настоящему распределённой. С ростом популярности крупных публичных репозиториев, таких как Гитхаб, система Git, которая изначально задумывалась как распределённая, фактически используется централизованно и полностью зависит от сторонних серверов.

В Gitchain цепочка блоков, построенная по образу и подобию Биткоина, хранит метаданные репозиториев. Это напоминает устройство сети Namecoin, где имена доменов и данные их владельцев общедоступны и защищены от подделок точно так же, как защищены транзакции сети Биткоин. Сам код и данные репозиториев хранятся отдельно, в сети DHT, так как их объём может быть слишком большим и быстро раздует цепочку блоков до неприемлемого размера. Вот небольшой скринкаст, который демонстрирует сеанс работы с Gitchain:

Юрий Рашковский пишет, что собранных денег хватит на то, чтобы завершить разработку базовой версии Gitchain до конца лета. Если удастся собрать 15 000 долларов, будут добавлены некоторые продвинутые функции — возможность создавать приватные зашифрованные репозитории, а также система вознаграждений участников сети, причём не только за майнинг блоков (proof of work), но и за хранение и передачу данных (proof of storage, proof of bandwidth). Это позволит перевести сеть из разряда хобби-проекта для энтузиастов в нечто более срьёзное и масштабируемое.

Весь код Gitchain открыт и доступен на Гитхабе под лицензией Apache 2.0

ссылка на оригинал статьи http://habrahabr.ru/post/224779/

Как улучшить сегментацию пользовательской активности. Семинар в Яндексе

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

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

Пользователь взаимодействует с поисковиком и браузером непрерывно:

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

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

В связи с изучением пользовательских сессий возникает несколько задач:

  1. определение границ логических сессий;
  2. предсказание следующего действия в сессии;
  3. извлечение сессионной информации для помощи в совершении следующего действия;
  4. моделирование действий пользователя в рамках одной сессии;
  5. Оценка скрытых данных в течение сессии – информационная потребность, удовлетворенность сессией, усталость.

Далее нам потребуется сформулировать несколько определений и ввести несколько обозначений. Главный герой моего рассказа – браузерная сессия – это последовательность страниц, посещенных пользователем в течение дня: Du – (d1…….dn). Второстепенный объект – запросная сессия – последовательность запросов заданных пользователем в течение одного дня: Qu – (q1…….qn). Vs также хотим выделить логическую браузерную сессию (и логическую запросную сессию) – часть браузерной сессии, состоящую из логически связанных страниц, посещенных с одной и той же информационной потребностью g:

Рассмотрим пример того, какой может быть пользовательская сессия:

Пользователь заходит на страницу поисковика, начинает искать информацию про научные семинары, перешел на страницу со списком всех семинаров Яндекса и узнал, что 28 марта будет интересный ему доклад и прочитал его анонс. Вдруг он заметил в анонсе какое-то неизвестное ему понятие и захотел посмотреть, что это такое. Он переходит по ссылке на сайт ecir2013.org. В этот момент у него поменялась информационная потребность: в начале он хотел посмотреть информацию про семинары, теперь он заинтересовался конференцией. Посмотрев на главную страницу конференции, он находит еще одно неизвестное понятие – информационный поиск. Он снова идет в поисковик и вводит там запрос [информационный поиск]. В поиске он находит станицу в Википедии, читает про нее, решает, что ему эта тема интересна, и возвращается на портал Яндекса, чтобы посмотреть, где же будет проходить семинар, т.е. возвращается к исходной логической сессии.

Конечно, это искусственный пример, но на нем можно проследить некоторые важные особенности логических сессий:

  1. Как правило, логические сессии перемежаются.
  2. Некоторые страницы участвуют в нескольких логических сессиях.
  3. Пользовательская потребность изменяется до задания запроса.

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

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

Как правило Du сегментируется на основе периода неактивности τ (здесь τ(d) – момент открытия d). di и di+1 принадлежат одной сессии, соответственно, τ(di+1) — τ(di) < τ. Это самый популярный и распространенный подход. Но очевидно, что он не работает, когда сессии перемежаются друг с другом. Если пользователь вернется к какой-то теме, с точки зрения этого подхода, это уже будет новая логическая сессия.

Задача логического разбиения запросных сессий уже решалась в двух работах:

  • P. Boldi et al. The Query-flow Graph: Model and Applications.
  • R. Jones et al. Beyond the Session Timeout: Automatic Hierarchical Segmentation of Search Topics in Query Logs.

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

В своем исследовании я решил поднять несколько вопросов:

  • Возможно ли уточнить логическое разбиение запросных сессий до уровня браузерный сессий?
  • Насколько качественное разбиение дает подход, основанный на периоде неактивности?
  • Как разные алгоритмы кластеризации влияют на качество сегментации?
  • Какие источники факторов важны для логической сегментации?

Метод

В качестве исходных данных применялись сырые браузерные сессии – последовательности страниц, посещенных пользователем. Сама же сегментация строится в два шага:

  1. Попарная классификация. Предсказываем, с одной ли целью пользователь посетил пару страниц (di,dj): учим функцию p(di,dj)∈[0;1], оценивающую вероятность принадлежности di,dj одной логической сессии.
  2. Кластеризация. Для разных оценок p(di,dj) кластеризовать полный граф на N вершинах di с весами ребер p(di,dj) в сильно связные компоненты

В результате у нас получается сегментация:

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

После этого учим классификатор p(di,dj).

В качестве модели для классификатора мы используем дерево решений с логистической функцией потерь. Она максимизирует вероятность корректной классификации всех пар:

Для каждой пары (d, d’) мы извлекаем четыре типа факторов (всего около 29 штук):

  1. Факторы на основе URL.
  2. Текстовые факторы.
  3. Сессионные факторы. Время между посещениями d, d’, количество документов между ними, был ли переход по ссылкам.
  4. Контекстные обобщения. Те же, что и в предыдущих трех пунктах, только вычисление для документа d", предшествующего d’.

Будем считать, что классификация произведена, и теперь наша цель – кластеризовать полный граф, найти разбиение, максимизирующее вероятность (значения ρ фиксированы, разбиение изменяется):

Π’ – произведение по всем парам (d, d’) из одного кластера;
Σ – сумма по всем парам (d, d’) из разных кластеров;
Π" – произведение по всем парам (d, d’) из всех кластеров.

Постановка задачи выглядит неплохо, однако в таком виде она оказывается NP-полной. Т.е. при большом размере сессий кластеризация будет очень затратна вычислительно. Поэтому приходится применять различные жадные алгоритмы. При работе с жадными алгоритмами подобного типа всегда возникает баланс между скоростью, качеством и областью применимости, который нужно подбирать непосредственно под конкретную задачу. Я разбил все жадные алгоритмы на две области применимости. Первая – это кластеризация в реальном времени: каждый новый документ dnew добавляется к текущему кластеру (g1, g2) или образует новый (gnew).

Я использовал три жадных алгоритма:

  1. Максимальное правдоподобие последней страницы. dg – последняя страница сегмента g. Все p(dg,dnew) < 1/2, следовательно, начинаем новую сессию. Иначе добавляем dnew к сессии с максимальной вероятностью.
  2. Максимальное правдоподобие всех страниц. Все p(d,dnew) < 1/2, следовательно начинаем новую сессию. Иначе добавляем dnew к сессии, содержащей документ с максимальной вероятностью.
  3. Жадное добавление. Добавление dnew чтобы максимизировать рост Φ. Если Φ всегда уменьшается для всех g, начинаем новый сегмент.

Второй тип алгоритмов работает со всей дневной активностью пользователя сразу, т.е. проводит пост-кластеризацию. К этому типу относится жадное слияние. Мы создаем N – |Du| кластеров. Жадным образом сливаем существующие кластеры, пока можно увеличить Φ.

Сложность первого алгоритма O(G × N), где G – количество сегментов. У всех остальных алгоритмов сложность O(N2).

Эксперименты

В качестве сырых данных были использованы анонимизированные браузерные логи, собранные с помощью тулбара. Они содержали адреса публичных страниц, для каждой из которых извлекалось время посещения, источник посещения (если был переход по ссылке), текст документа и ссылки, по которым пользователь с них уходил (если это происходило). Для обучающей выборки каждая браузерная сессия была вручную поделена асессорами на логические сессии. Всего у нас было 220 браузерных логических сессий и 151 тысяча пар для обучения классификатора: 78 тысяч из одной сессии и 73 тысячи из разных. Средняя длина логической сессии составляла 12 страниц, а среднее число логических сессий у пользователя в день – 4,4.

В таблице ниже представлено качество временного разбиения и классификаторов, обученных на разных наборах факторов:

Набор факторов Временное разбиение Все Без контекста Без текста
F-мера 80% 83% 83% 82%
Точность 72% 82% 81% 81%

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

Rk Фактор Очки
1 время между d1 и d1 1
2 LCS 0.58
3 LCS/length(url1) 0.40
4 LCS/length(url2) 0.40
5 # страниц между d1 b d1 0.33
6 триграммное совпадение URL 0.32
7 контекстный LCS/length(url1) 0.32
8 один хост 0.22
9 LCS/length(url2) 0.20
10 контекстный LCS 0.20

Как мы и ожидали, самый важный фактор – время между посещением документов. Также довольно естественно, что важную роль играет URL и LCS (длина общей подстроки URL). Какую-то роль играют контекстные факторы. При этом здесь нет ни одного текстового фактора.

Теперь перейдем к экспериментам в кластеризации. Мера качества алгоритмов основана на Rand Index. Для двух сегментаций S1, S2 множества Du он равен доле одинаково соответственных пар документов:

Здесь n1 – # пар из одного сегмента S1, S2, n2 – # пар из разных сегментов S1, S2, N – # элементов в Du. Далее S1 – идеальная сегментация, а S2 – оцениваемая. R(S1, S2) представляет собой точность соответствующего классификатора. На графике ниже представлен Rand Index для периода активности в τ:

Теперь посмотрим, как работают описанные нами выше алгоритмы:

Метод Rand Index Сложность
Временной 0.72
Макс. правдоподобие посл. страниц 0.75 O(N × G)
Макс. правдоподобие всех страниц 0.79 O(N2)
Жадное добавление 0.82 O(N2)
Жадное слияние 0.86 O(N2)

Качество классификатора соответствующего жадному слиянию (0.86) даже выше, чем у исходного классификатора (0.82).

Выводы

  1. Предложен метод автоматической обработки браузерных логов, уточняющий разбиение запросных логов.
  2. Мы свели задачу сегментации к хорошо изученным задачам классификации и кластеризации.
  3. Хотя временной подход довольно неплох, более сложные алгоритмы кластеризации ощутимо его превосходят.
  4. Контекстные и текстовые факторы оказываются гораздо менее важными для определения логических связей между страницами в пределах одной сессии, чем факторы основанные на сессионных данных и совпадении URL.

Ближайший научно-технический семинар в Яндексе состоится 10 июня. Он будет посвящен теме рекомендательных систем и распределенных алгоритмов.

ссылка на оригинал статьи http://habrahabr.ru/company/yandex/blog/224719/