Develoloping User Interface Adaptive Methods for USSD Services

Tregubov Artem Sergeevich Master degree student of the Faculty of Information Technologies, Department of General Computer Studies at Novosibirsk State University 630090, Russia, Novosibirskaya oblast', g. Novosibirsk, ul. Pirogova, 2 artem.tregubov@mail.ru Other publications by this author

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

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

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

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

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

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

В данной статье предлагается использовать информацию о контексте (или окружении) пользователя. Основной идеей является то, что один и тот же пользователь, находясь в разных контекстах, может воспринимать информацию по-разному и иметь разные нужды ^[1].

Дизайн пользовательского интерфейса влияет на количество усилий, прилагаемых пользователем для достижения своих целей, а также на скорость освоения программной системы. Многие современные системы позволяют самостоятельно настраивать пользовательский интерфейс. Безусловно, это гораздо дешевле для производителей ПО, но пользователи, не являющиеся продвинутыми, могут не разобраться с возможностями ручной доработки интерфейса ^[2]. Кроме того, использование данного подхода не представляется возможным в рамках протокола USSD.

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

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

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

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

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

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

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

Поскольку данная работа посвящена разработке метода автоматической адаптации USSD-меню, стоит немного рассказать о данной технологии.

USSD (Unstructured Supplementary Service Data) – сессионно ориентированный протокол передачи неструктурированных данных, реализованный для сетей стандарта GSM. Эта технология позволяет осуществить высокоскоростное взаимодействие с пользователем в условиях отсутствия интернета ^[2].

Для открытия сессии пользователь набирает команду на телефоне вида *...#. Такой формат позволяет телефону понять, что нужно произвести не звонок, а USSD запрос. Запросы могут быть как единичными (например, запрос баланса), так и интерактивными. Если ответ пользователя не был получен сервером в течении 60-ти секунд, то сессия обрывается. Максимальная длина контента может составлять 182 символа.

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

При выборе алгоритма адаптации USSD-меню важно учитывать привычки пользователей. Резкое изменение меню усилит недовольство абонентов и усложнит процесс обучения.

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

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

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

В предыдущих работах ^[2-3] кластеризация производилась по вектору интересов. И это давало хорошие результаты.

В процессе изучения литературы посвященной вопросу создания адаптивных интерфейсов, бала изучена статья ^[1], в которой предлагалось разделить модель пользователя на 3 части: информация о пользовательском опыте, информация об устройстве, информация о контексте. Поскольку информацию об устройстве нельзя получить в рамках протокола USSD, было решено использовать информацию о пользовательском опыте и контексте.

На этапе анализа были сформированы следующие ограничения для предлагаемого алгоритма:

1. Максимальное количество символов на одной USSD странице не может превышать размер одного сообщения.
2. Максимальное количество пунктов меню на странице не должно превышать 5-6.
3. Не должна нарушаться тематическая структура иерархического графа меню.

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

Искусственные нейронные сети призваны решать множество различных задач. К задачам, решаемым при помощи данной технологии можно отнести: распознавание образов, аппроксимацию, оптимизацию ^[4].

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

Рис. 1, Иллюстрация работы нейронной сети

После кластеризации пользователей по интересам, необходимо перейти ко второму этапу.

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

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

Для каждой группы происходит выборка всех сессий, которые были открыты пользователями данного кластера. Затем полученные сессии кластеризуются на 7-9 групп. Этого должно хватить, поскольку пользователи открывшие данные контексты имеют схожие группы интересов, следовательно, имеют схожие контексты выполнения. Этот процесс выполняется для каждого кластера полученного на первом этапе (см. рис. 2).

Рис. 2, Иллюстрация второго этапа кластеризации

Опишем задачу оптимизации.

Пусть N – количество услуг, K–количество пользователей, `n_(ij)` ` ` — количество вызовов i-й услуги пользователем j, а `d_i` —количество переходов необходимое для активации i-й услуги.

Тогда задача оптимизации записывается в виде:

`sum_(i=1)^Nsum_(i=1)^N n_(ij) d_i -> min`

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

В рамках данной работы предлагается использование следующего алгоритма.

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

Построим граф меню и найдем в этом графе пустые слоты.

Обозначим граф меню как `G = (V, E)` . На данном этапе можем не учитывать тот факт что граф является ориентированным. Соответственно `v_(i)` обозначим вершину под номером i. Каждой вершине присвоим вес `w_(i)` , определим это число следующим образом.

Если `v_(i)` - лист

`w_(i) = sum_(j=1)^K n_(ij)`

Иначе,

`w_(i) = sum w_(j)d_(i)`

Для всех j, таких что вершина j входит в поддерево с корнем в i.

Иными словами, вес внутренних вершин `v_(i)` равен сумме всех листов исходного дерева, входящих в поддерево с корнем в `v_(i)` , умноженное на длину пути до вершины `v_(i)`.

Пронумеруем все слоты, обойдя граф в ширину. Отсортируем список вершин по весу, присвоим i-ому слоту поддерево i.

Этот процесс запускается для каждого кластера.

` `

` `

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

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

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

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

`D=1- ( sum_(j=1)^K n_(j) )/( sum_(j=1)^K m_(j) ) `

Где K – колличество пользователей кластера, `n_(j)` — количество запросов совершаемых пользователем в оптимизированном меню, `m_(j)` — количество запросов совершаемых пользователем в первоначальном меню.

Было решено проверить алгоритм оптимизации на следующих данных.

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

После проведения оптимизации меню для каждого кластера, было получено 100 различных модификаций исходного меню (10 основных кластеров и 10 подкластеров для каждого из них). Для каждой модификации было подсчитано сокращение количества запросов.

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

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

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

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