Изменения

'''Иерархия навигируемых малых мировИерархический маленький мир''' (англ. ''Hierarchical Navigable Small World'') {{---}} структура данных, позволяющая эффективно находить K искать <tex>k</tex> почти что ближайших соседейна больших множествах вершин. Поиск ближайших соседей нужен в задачах [[Общие понятия|классификации]] и [[кластеризация|кластеризации]]. По своей концепции напоминает [[список с пропусками]]. == Применение ==Представим себе ситуацию:* У социальной сети есть <tex>10^{11}</tex> пользовательских фотографий с отмеченными лицами на них.* По новой фотографии требуется быстро узнать кто на ней и предложить пользователю отметить этого человека. Возможный процесс:# Обучаем [https://github.com/davidsandberg/facenet FaceNet] выдавать <tex>128</tex>-мерные вектора по изображению лица, такие, что у фотографий одного человека похожие значения векторов.# Добавляем <tex>10^{11}</tex> векторов в иерархический маленький мир.# При добавлении новой фотографии, вычисляем соответствующий лицу вектор.# Ищем <tex>k</tex> его ближайших соседей.# Классифицируем лицо с использованием [[Метрический классификатор и метод ближайших соседей#Использование ядер сглаживания|ядер сглаживания]].# Если пользователь подтвердил нашу догадку, добавляем этот вектор в иерархический маленький мир.

Чёрные ребра {{---}} короткие связи с ближайшими соседямив небольшом радиусе <tex>R</tex>, красные рёбра {{---}} длинные связи, созданные по какой-то эвристике, обеспечивающие малое логарифмическое мат. ожидание длины пути.

Для маленького мира на точках в Евклидовом пространстве, приближенный жадный поиск K <tex>k</tex> ближайших соседей будет выглядеть так: '''KNNknn'''(V, E, request, m, k)''':''' nearest W = new TreeSet() <tex>\emptyset</tex> <font color="green">// Ближайшие к q вершины упорядочены по возрастанию расстояния до request . </font> candidates C = <tex>\emptyset</tex> <font color= new TreeSet()"green">// Вершины, которые предстоит посетить. </font> visited V = new HashSet()<tex>\emptyset</tex> <font color="green">// Посещённые вершины. </font>

candidates.add(случайная вершина графа)C = С <tex>\bigcup</tex> <tex>random_v</tex> v <tex>\in</tex> G tempNearest TN = <tex>\emptyset</tex> <font color= new TreeMap()"green">// Ближайшие вершины в этом проходе.</font>

current u = candidates{q1 | <tex>\forall</tex> q2 <tex>\in</tex> C, |q - q1| <= |q - q2|} <font color="green">// Ближайшая к q вершина из C.popMin() </font> C = C <tex>\setminus</tex> u '''if''' current u дальше чем k-й элемент nearestW

'''for''' v e: смежные с current вершины(u, e) '''in''' G '''if''' !visited.contains(v)e <tex>{\notin}</tex> V candidates.add(v)C = C <tex>\bigcup</tex> e visited.add(v)V = V <tex>\bigcup</tex> e tempNearest.add(v)TN = TN <tex>\bigcup</tex> e nearest.addAll(tempNearest)W = W <tex>\bigcup</tex> TN '''return''' k первых ближайших к q вершин из nearestW

Расстояние между вершинами графа может измеряться [[Метрический классификатор и метод ближайших соседей#Использование различных метрик расстояния|различными метриками]]. <br/>Очевидный недостаток этого алгоритма {{---}} опасность свалиться в локальный минимум, остановившись в каком-то кластере. С увеличением числа <tex>m</tex>, вероятность такого застревания экспоненциально падает.

'''Иерархический Маленький мир''' (англ. ''Hierarchical Navigable Small World'') {{---}} слоистая структура графов. На нулевом слое представлены все '''<tex>N''' </tex> вершин из исходной выборки. Вершина, присутствующая на уровне '''<tex>L''' </tex> так же присутствует на уровне '''<tex>L + 1''' </tex> с вероятностью '''<tex>P'''</tex>. Т.е. кол-во слоёв растет как <tex>O(\log N)</tex>. Количество соседей каждой вершины на каждом уровне ограниченно константой, что позволяет делать запросы на добавление и удаление вершины за <tex>O(\log N)</tex>.

Жадно идём по уровню в сторону запроса. '''searchLayer'''(q, ep, ef, lclayer)''':''' <font color="green">// ВводВходные данные: иерархия графов hnsw, запрос q, входная точка входные точки ep, искомое количество ближайших соседей ef, номер слоя lclayer.</font> <font color="green">// ВыводВозвращает: ef ближайших соседей qв слое layer.</font> candidates W = new TreeSet() {ep} <font color="green">// Вершины упорядочены по возрастанию расстояния до requestБлижайшие к q вершины. </font> result C = {ep} <font color= new TreeSet()"green">// Вершины, которые предстоит посетить. </font> visited V = {ep} <font color= new HashSet()"green">// Посещённые вершины. </font> '''while''' candidates.isNotEmpty()C != <tex>\emptyset</tex> current u = {q1 | <tex>\forall</tex> q2 <tex>\in</tex> C, |q - q1| <= |q - q2|} <font color= candidates"green">// Ближайшая к q вершина из C.getMin()</font> furthest f = {q1 | <tex>\forall</tex> q2 <tex>\in</tex> W, |q - q1| >= |q - q2|} <font color= result"green">// Самая дальняя от q вершина из W.getMax()</font> '''if''' distance(current, |u - q) | > distance(furthest, |f - q)|

'''for''' v e : смежные с current вершины(u, e) '''in''' G '''if''' !visited.contains(r)e <tex>{\notin}</tex> V visited.add(v)V = V <tex>\bigcup</tex> e furthest f = result{q1 | <tex>\forall</tex> q2 <tex>\in</tex> W, |q - q1| >= |q - q2|} <font color="green">// Самая дальняя от q вершина из W.getMax()</font> '''if''' distance(v, |e - q) | < distance(furthest, |f - q) | or result.count() |W| < ef candidates.add(v)C = C <tex>\bigcup</tex> e result.add(v)W = W <tex>\bigcup</tex> e if result.count() |W| > ef result.removeLast()W = W \ f '''return''' resultW

===Вставка элемента===# Случайным образом выбираем максимальный слой, на котором будет представлена <tex>q</tex>.# На каждом уровне, где будет представлена <tex>q</tex>, сверху вниз:## Жадно ищем <tex>m</tex> ближайших к <tex>q</tex> вершин.## Добавляем связи <tex>q</tex> с ними.## Удаляем лишние связи у новообразовавшихся соседей. '''knninsert'''(hnsw, q, Km, mMax, ef, mL)''':''' <font color="green">// ВводВходные данные: граф иерархия графов hnsw, запрос на добавление q, искомое желаемое количество связей m, максимальное количество ближайших соседей Kсвязей вершины </font> <font color="green">// на одном слое mMax, количество кандидатов при поиске ef, коэффициент выбора высоты mL. </font> <font color="green">// ВыводВозвращает: K ближайших соседей hnsw с вставленным элементом q. </font> result W = new TreeSet() <tex>\emptyset</tex> <font color="green">// Вершины упорядочены по возрастанию расстояния до requestБлижайшие к q вершины. </font> mL = |hnsw| - 1 ep = случайная вершина из верхнего слоя <tex>random_v</tex> v <tex>\in</tex> hnsw[mL] maxLevel qL = индекс самого высокого слоя в hnsw-ln(rand(eps, 1.0)) * mL <font color="green">// Верхний слой для вершины q. </font> '''for''' level = maxLevel mL to qL + 1 result W = searchLayer(q, ep, ef=1, level) ep = W '''for''' level = min(mL, qL) to 0 W = searchLayer(q, ep, ef, level) neighbours = M ближайших к q вершин из W '''for''' n <tex>\in</tex> neighbours: <font color="green">// Добавляем двусторонние связи между n и q. </font> hnsw[level] = hnsw[level] <tex>\bigcup</tex> (n, q) hnsw[level] = hnsw[level] <tex>\bigcup</tex> (q, n) nNeighbours = {v| (v, n) '''in''' hnsw[level]} <font color="green">// На каждом Ищем всех соседей n на уровнеlevel. </font> <font color="green">// Убираем лишние связи, кроме нижнего мы ищем всего одну ближайшую вершинуесли требуется. </font> ep = result '''if''' nNeighbours.getMinCount()> mMax <font color="green">// Самая дальняя от n вершина, смежняя с ней. </font> result v = searchLayer{q1 | (qq2, epn) <tex>\in</tex> nNeighbours & <tex>\forall</tex>q2 <tex>\in</tex> hnsw[level], ef|q - q1| >= |q - q2|} hnsw[level] = hnsw[level] <tex>\setminus</tex> (n, lcv) hnsw[level] =0hnsw[level] <tex>\setminus</tex> (v, n) ep = W '''returnif''' qL > mL '''for''' первые K элементов из resultlevel = mL to qL hnsw.append({q, {}})

==Практическое использование =Вставка элемента=В библиотеке [https://github.com/nmslib/hnswlib Hnswlib] есть реализация иерархического маленького мира. Эта библиотека написана на C++, с биндингами на python.Пример использования: '''import''' hnswlib '''import''' numpy '''as''' np dim =128 num_elements =10000 <font color="green"># Создаём тестовые данные.</font> data = np.float32(np.random.random((num_elements, dim))) data_labels = np.arange(num_elements) <font color="green"># Создаём иерархический маленький мир в L2.</font> <font color="green"># Возможные метрики {{---}} l2, cosine, ip (L2, косинус угла между векторами, скалярное произведение).</font> p = hnswlib.Index(space = 'l2', dim = dim) <font color="green"># Инициализируем структуру.</font> p.init_index(max_elements = num_elements, ef_construction = 200, M = 16) <font color="green"># Добавляем данные (можно вызывать много раз).</font> p.add_items(data, data_labels) <font color="green"># Настраиваем качество, выставляя ef:</font> p.set_ef(50) <font color="green"># ef должно быть > k</font> <font color="green"># Делаем запрос.</font> <font color="green"># k - количество ближайших вершин</font> labels, distances = p.knn_query(data, k = 1)

== Примечания ==* [[Общие понятия]]* [[Метрический классификатор и метод ближайших соседей]]* [[Список с пропусками]] 

* [https://arxiv.org/abs/1603.09320 Yu. A. Malkov, D. A. Yashunin {{---}} Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs]* [https://ru.wikipedia.org/wiki/%D0%9C%D0%B8%D1%80_%D1%82%D0%B5%D1%81%D0%B5%D0%BD_(%D0%B3%D1%80%D0%B0%D1%84) Википедия {{---}} Мир тесен (граф)]* [https://en.wikipedia.org/wiki/Small-world_network Wikipedia {{---}} Small-world network]* [https://github.com/sgjurano/ysda-celebrity-faces Поиск знаменитостей на фотографии с помощью иерархического маленького мира]* [https://m.habr.com/ru/company/mailru/blog/338360/ Статья на википедии о маленьких мирахот Mail.ru об использовании иерархического маленького мира] [[Категория: Машинное обучение]]