Клавиатурный почерк - поведенческая биометрическая характеристика, которую описывают, в частности, следующие параметры:

-количество ошибок при наборе;

-интервалы между нажатиями клавиш;

-время удержания клавиш;

-число перекрытий между клавишами;

-степень аритмичности при наборе;

-скорость набора.

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

Задача классификации в машинном обучении — это задача отнесения объекта к одному из заранее определенных классов на основании его формализованных признаков. Каждый из объектов в этой задаче представляется в виде вектора в N-мерном пространстве, каждое измерение в котором представляет собой описание одного из признаков объекта.

Один из самых простых алгоритмов классификации – метод k ближайших соседей – это метод, относящий объекты к классу, которому принадлежит большинство из k его ближайших соседей в многомерном пространстве признаков. Благодаря своей простоте, этот метод является хорошим примером, с которого можно начать знакомство с областью Machine Learning. Для вычисления расстояния между двумя точками x=(x1,x2) и y=(y1,y2) можно использовать Евклидову метрику: d(x,y)=((x1-y1)^2+(x2-y2)^2)^{1/2} Число k – это количество соседних объектов в пространстве признаков, которое сравнивается с классифицируемым объектом. Классом объекта считается тот класс, представителей которого больше всего среди его k ближайших соседей.

К примеру, для задачи аутентификации по клавиатурному почерку в качестве тестовой группы могут быть выбраны 3 категории работников: лаборанты кафедр (стабильный и аккуратный стиль набора текста), программисты (характерен «рваный» эмоциональный стиль набора), руководители (используют компьютер как дополнительный рабочий инструмент)

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

-время удержания клавиш;

-интервалы между нажатиями клавиш.

Keyboard handwriting is a behavioral biometric characteristic, which is described, in particular, by the following parameters: -number of errors when typing;

-intervals between keystrokes;

-time of holding the keys;

- number of overlaps between keys;

- the degree of arrhythmia when typing;

-set speed.

For example, the time intervals between keystrokes on the keyboard and the holding time (pressing) of the keys make it possible to unambiguously describe the handwriting of the user's work on the keyboard, as evidenced by a number of experiments. The time intervals between keystrokes characterize the pace of work, and the time of holding the keys is the style of working with the keyboard (sudden impact or smooth pressing). The task of classification in machine learning is the problem of assigning an object to one of the predetermined classes on the basis of its formalized characteristics. Each of the objects in this problem is represented as a vector in an N-dimensional space, each measurement in which is a description of one of the characteristics of the object.

One of the simplest classification algorithms - the k nearest neighbors method is the method that relates objects to a class that owns most of its k nearest neighbors in a multidimensional feature space. Due to its simplicity, this method is a good example, from which you can begin to get acquainted with the field of Machine Learning. To calculate the distance between two points x=(x1,x2) amd y=(y1,y2), we can use the Euclidean metric: d(x,y)=((x1-y1)^2+(x2-y2)^2)^{1/2}. The number k is the number of neighboring objects in the feature space that is compared with the object being classified. The class of the object is that class whose representatives are the most among its k nearest neighbors. For example, for the authentication task for keyboard handwriting as a test group, three categories of employees can be selected: laboratory assistants (stable and accurate style of typing), programmers (characterized by a "torn" emotional style of the set), managers (use the computer as an additional working tool )

The analysis of the user's handwriting can be carried out by two criteria: -time of holding the keys; -intervals between keystrokes.

В первой строке дано натуральное число К – количество «соседей», которые должны учитываться в классификации пользователя.

В следующей строке натуральное число С – количество классов, 1\leq С \leq10.

В следующей строке натуральное число MC – количество элементов каждого класса, 1\leq MC \leq1000.

Далее идут C*MC строк, каждая из которых состоит из трех чисел разделенных пробелами: целого числа (категория работника, возможные значения 1, 2, 3 и далее) и двух вещественных чисел (характеризующих время удержания клавиш и интервалы между нажатиями).

В следующей строке дано целое число M — количество пользователей, которых надо классифицировать (1 \leq M \leq 1000).

В следующих M строках: пары вещественных чисел, разделенных пробелами — время удержания клавиш и интервалы между нажатиями.

The first line contains the natural number K - the number of "neighbors" that must be taken into account in the user's classification.

In the next line, the natural number C is the number of classes, 1\leq С \leq10.

In the next line, the natural number MC is the number of elements of each class, 1\leq MC \leq1000. Next come C * MC lines, each of which consists of three numbers separated by spaces: an integer (employee category, possible values 1, 2, 3 and on) and two real numbers (characterizing the hold time of keys and intervals between clicks).

The next line gives the integer M - the number of users that need to be classified (1 \leq M \leq 1000). In the next M lines: pairs of real numbers separated by spaces - hold time of keys and intervals between clicks.

Для каждого из M пользователей вывести в отдельную строку целое число 1, 2 или 3 — его категорию.

For each of the M users, print a single integer 1, 2, or 3 - its category.