Вы можете запустить DBSCAN с функцией произвольного расстояния без каких-либо изменений. Часть индексации будет более сложной, поэтому вы, скорее всего, получите только O(n^2) сложность.
Но если вы внимательно посмотрите на DBSCAN, все, что он делает, это вычисляет расстояния, сравнивает их с порогом и подсчитывает объекты. Это является ключевым преимуществом, его можно легко применять к различным типам данных, все, что вам нужно, это определить функцию расстояния и пороговые значения.
Я сомневаюсь, что существует версия DBSCAN с одним проходом, так как она основана на попарных расстояниях. Вы можете обрезать некоторые из этих вычислений (здесь вступает в действие индекс), но, по сути, вам нужно сравнивать каждый объект с любым другим объектом, поэтому он находится в O(n log n), а не в одном проходе.
Однопроходный: я полагаю, что оригинальное k-среднее было алгоритмом однопроходного Первые k объектов - это ваши начальные средства. Для каждого нового объекта вы выбираете среднее значение и закрываете его (постепенно) новым объектом. До тех пор, пока вы не сделаете еще одну итерацию для своего набора данных, это был «однопроходный». (Результат будет даже хуже, чем у k-средних в стиле Ллойда).