Вопрос или проблема
В настоящее время у нас есть упражнение по кодированию, в котором нас просят реализовать Постоянное Сдвиговое Встраивание (Статья). Это само по себе не является большой проблемой. Для алгоритма все, что вам нужно, это симметричная ненулевая диагональная матрица неоднородности каких-то неметрических данных о близости. С помощью алгоритма вы можете встроить информацию в векторное пространство, и поэтому вы можете использовать широко известные методы шумоподавления и уменьшения размерности, чтобы улучшить результаты, например, кластеризации методом k-средних.
Учитывая электронные коммуникации на основе этого набора данных, как бы вы выбрали разумную матрицу неоднородности?
Данные представляют собой простой список уникальных пар, где по крайней мере одно электронное письмо было отправлено от узла A к узлу B. Это приводит к графу из примерно 1000 узлов и 25000 рёбер.
Создание матрицы смежности этого неориентированного графа может быть первым шагом (что также уже предусмотрено в рамках).
Я благодарен за любые подсказки в правильном направлении.
РЕДАКТИРОВАТЬ: За ночь у меня появилась идея:
Допустим, у нас есть только 8 узлов. Теперь сравните элементы близости двух вершин. Если бы векторы близости выглядели, например, так:
1 0 0 0 1 0 1 1
0 1 0 0 0 1 0 1
Их неоднородность составит 5, поскольку их векторы различаются в 5 точках.
Теперь просто нормализуйте относительно общего числа узлов, следовательно, 5/8.
Таким образом, мы также учитываем информацию о том, сколько соседей разделяют узлы, а не только рассматриваем прямые рёбра, и поэтому можем получить лучшие результаты, когда позже попытаемся сгруппировать узлы.
Дайте знать, что вы об этом думаете.
Возможно, я не совсем понял ваш вопрос, но думаю, что ответ, который вы ищете, один из следующих:
-
Вы можете захотеть заполнить матрицу n на n значением 1, если человек $i$ отправил электронные письма человеку $j$, и 0 в противном случае.
-
Возможно, вы хотите заполнить матрицу n на n количеством электронных писем, отправленных от человека $i$ к человеку $j$.
Оба измерения являются расстояниями в математическом определении.
Для ясности:
Вы можете запрограммировать матрицу неоднородности как $M[i,j] = 1$, если пара людей в ваших данных существует.
Ответ или решение
Краткое описание матрицы несходства для недирективных данных
При работе с графами, основанными на взаимодействиях, таких как электронная почта, создание матрицы несходства может оказаться важным шагом в анализе данных. Ваша задача заключается в том, чтобы рассмотреть, как вы можете разработать и реализовать матрицу несходства на основе данных о взаимодействии между узлами графа.
Основные понятия
- Матрица несходства – это квадратная матрица, где каждый элемент (i, j) указывает степень несходства или различия между двумя объектами (в данном случае, между двумя пользователями электронной почты).
- Недирективные данные – данные, которые не имеют явной метрики для оценки расстояний или различий. В нашем случае это могут быть взаимодействия между пользователями.
- Симметричная матрица – для пользователей A и В расстояние от A до B должно быть равно расстоянию от B до A.
Пример подхода
Для начала, вы можете создать матрицу размера n x n, где n – количество уникальных пользователей. Существует несколько подходов к созданию матрицы несходства:
-
Бинарная матрица: Каждый элемент M[i, j] равен 1, если пользователь i общался с пользователем j, и 0 в противном случае. Это простой способ представить наличие/отсутствие связи между пользователями.
-
Числовая матрица: Каждый элемент M[i, j] может представлять количество сообщений, отправленных от пользователя i к пользователю j. Это даст больше информации о степени взаимодействия.
-
Процентное распределение: Если вы хотите учесть уровень различий на основе общего числа пользователей, вы можете использовать подход, предложенный вами. Например, если два пользователя имеют векторы взаимодействия, вы можете определить их несходство как количество позиций, в которых они имеют разные значения, и затем нормализовать это значение с учетом общего количества пользователей. Это будет выглядеть так:
[
D(i, j) = \frac{\text{Количество различий}}{n}
]где ( n ) — общее количество пользователей.
Выбор метрики
Наиболее подходящая метрика зависит от вашей конкретной задачи. Если ваша цель состоит в том, чтобы найти группы пользователей с похожими паттернами коммуникации, лучше подойдет второй вариант с числовыми значениями. Он даст больше информации для анализа кластеров, чем бинарная матрица.
Дальнейшие шаги
После того, как вы определитесь с формой матрицы несходства, следующим шагом будет реализация алгоритма "Constant Shift Embedding", как описано в указанной вами статье. Это позволит вам использовать полученную матрицу для снижения размерности и дальнейшего анализа, например, для кластеризации с использованием алгоритмов, таких как k-means.
Заключение
Ваша идея о нормализации несходства на основе общего количества пользователей является интересным и многообещающим шагом. Это может улучшить качество кластеризации, учитывая не только прямые связи между узлами, но и их общие характеристики. Постепенно прорабатывая все аспекты, от создания матрицы несходства до применения алгоритмов анализа, вы сможете достичь значительных результатов в исследовании своих данных.