Блог

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

 A, B, F, G, A, T, S, B, S, B, S, Q, Z, B, Q, S
  

Вот список, показывающий, как часто встречается каждая буква (вхождения):

 A - 2
B - 4
F - 1
G - 1
Q - 2
T - 1
S - 4
Z - 1
  

Таким образом, частота возникновения как таковая (возникновение случаев):

 4 - 2
2 - 2
1 - 4
  

Приведенный выше крошечный пример, но я приложил изображение, которое представляет собой простой линейный график более крупной системы

На этом графике цифры внизу не очень важны. Они просто отмечают количество уникальных частот. И ось Y отмечает значение этой частоты.

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

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

Для пояснения, мой текущий алгоритм создает список встречаемости пар чисел с частотой встречаемости. Мое использование слова «частота» никоим образом не относится к электромагнитным сигналам, а скорее к тому, как часто происходит событие. Но я подумал, что выражение «случаи возникновения» будет более запутанным!

В этой системе общая тенденция заключается в том, что несколько объектов будут отображаться в большом количестве взаимодействий, больше объектов будет отображаться в среднем количестве взаимодействий, но наибольшее количество объектов будет отображаться всего в нескольких или даже в отсутствие взаимодействий. Было бы сложно представить сценарий, в котором он отличался бы от этого … худшим случаем, вероятно, было бы плато. Но после прыжка определенно может быть провал в любой момент от начала до конца. На иллюстрации выше этого просто нет. Мы не можем предположить, что наступит момент, когда он начнет расти без каких-либо падений после этого.

Вот мои данные. (Простой график выше был создан только с данными столбца частоты встречаемости):

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

 "2 entities occur 309 times"
"1 entity occurs 130 times"
etc.
  

В конечном счете, я пытаюсь определить важность объекта на основе того, как часто он встречается в системе. Мне нужно иметь возможность помечать определенные элементы как «важные», но все элементы не могут быть важными. И метод / алгоритм, который я ищу, помогли бы определить, в какой точке этого списка я перестаю считать важные элементы.

Если вы посмотрите на список, вы можете увидеть, где более низкие вхождения начинают становиться более частыми. Я не думаю, что смогу выполнить сортировку по правому столбцу, потому что левый столбец — это действительно ключевые данные. Большее количество случаев = большее значение.

Но мне все еще нужно выяснить, как это определить.

Есть ли какая-либо причина, по которой больший пример не отсортирован? Если вы отсортируете его по возрастанию значений Y, то вы можете взять наклон каждой последовательной пары и вызвать точку останова, где наклон значительно меняется.

Вы можете настроить правила для «значительных изменений» в соответствии с вашими конкретными потребностями. Это может быть так же просто, как «наклон, который увеличивается больше всего по сравнению с предыдущим», или «первый наклон, который отличается более чем на X% от текущего среднего наклона». Или, может быть, наибольший rss различий между наклоном в контрольной точке и наклоном до и после.

После редактирования, я думаю, это может быть так же просто, как взять процент. Умножьте каждый X и Y и возьмите сумму по всем записям. Это общее количество наблюдаемых событий. Теперь начните снизу, если ваша таблица, и начните вычитать произведение каждой строки из общей суммы, пока не получите менее X% от первоначальной суммы. То, что у вас осталось, — это «значимые» события, которые внесли наибольший вклад в общую сумму.

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

Все, что вам нужно сделать, это уточнить это «найти точку, где эта линия начинает ломаться вверх». Исходя из того, что вы говорите, я могу предположить и принять в качестве предварительного условия, что линия всегда тормозит вверх, и с этого момента она никогда не опустится (даже на один шаг). Это означает, что в вашем примере он вернет 33, а не 32.

Также предполагается, что у вас будет как минимум 2 значения… если у вас есть один, его не с чем сравнивать, верно? 🙂

Итак, алгоритм для решения этой проблемы будет примерно таким:

 repeat
    $previousYValue = get the highest Y value
    $previousXValue = get the X value corresponding to $previousYValue
    $currentXValue = $previousXValue - 1
    $currentYValue = get the Y value for $currentXValue
until ($currentYValue > $previousYValue)
print "The line breaks upwards at point: $previousXValue with value $previuosYValue"
  

Надеюсь, это поможет

На основе вашего заявления:

В конечном счете, я пытаюсь определить важность объекта на основе того, как часто он встречается в системе. Мне нужно иметь возможность помечать определенные элементы как «важные», но все элементы не могут быть важными. И метод / алгоритм, который я ищу, помогли бы определить, в какой точке этого списка я перестаю считать важные элементы.

Я бы рассмотрел проблему с точки зрения вероятности и статистики, а не графика функций. Используя ваши выборочные данные, вероятность появления определенной буквы x — это просто количество x в данных, деленное на общее количество букв.

Несколько простых возможностей для тестирования:

• выберите набор наиболее вероятных событий, на которые приходится 50% от общего количества событий
• выберите все события с вероятностью> 0,1
• выберите n наиболее вероятных событий.

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