распределить цены по группам, если они находятся в пределах 0,5% друг от друга

Question

Спасибо за ответы, я раньше не использовал StackOverflow, поэтому я был удивлен количеством ответов и скоростью их - это фантастика.

Я еще не получил правильных ответов, но подумал, что мне следует добавить некоторую информацию в спецификацию проблемы. Смотрите изображение ниже.

Я не могу опубликовать изображение в этом, потому что у меня недостаточно очков, но вы можете увидеть изображение в http://journal.acquitane.com/2010-01-20/image003.jpg

Это изображение может более точно описать то, чего я пытаюсь достичь. Таким образом, вы можете видеть на горизонтальных линиях на странице ценовые точки на графике. Теперь, когда вы получаете кластеризацию линий в пределах 0,5% от каждой, это считается хорошей вещью, и поэтому я хочу автоматически идентифицировать эти кластеры. На графике видно, что на S2 и MR1, R2 и WPP1 есть кластер.

Таким образом, каждый день я создаю эти ценовые точки, а затем я могу вручную определить те, которые находятся в пределах 0,5%. - но цель этого вопроса в том, как сделать это с помощью Python.

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

[YR3,175.24,8] [SR3,147.85,6] [YR2,144.13,8] [SR2,130.44,6] [YR1,127.79,8] [QR3,127.42,5] [SR1,120.94,6] [QR2,120.22,5] [MR3,118.10,3] [WR3,116.73,2] [DR3,116.23,1] [WR2,115.93,2] [QR1,115.83,5] [MR2,115.56,3] [DR2,115.53,1] [WR1,114.79,2] [DR1,114.59,1] [WPP, 113.99,2] [ДПП, 113.89,1] [MR1,113.50,3] [DS1,112.95,1] [WS1,112.85,2] [DS2,112.25,1] [WS2,112.05,2] [DS3,111.31,1] [МРР, 110.97,3] [WS3,110.91,2] [50mA, 110.87,4] [MS1,108.91,3] [QPP, 108.64,5] [MS2,106.37,3] [MS3,104.31,3] [QS1,104.25,5] [SPP, 103.53,6] [200MA, 99.42,7] [QS2,97.05,5] [ППМС, 96.68,8] [SS1,94.03,6] [QS3,92.66,5] [YS1,80.34,8] [SS2,76.62,6] [SS3,67.12,6] [YS2,49.23,8] [YS3,32.89,8]

Я допустил ошибку с первоначальным списком в том, что группа C неверна и не должна быть включена. Спасибо что подметил это.

Также 0,5% не является фиксированным, это значение будет меняться изо дня в день, но я просто использовал 0,5% в качестве примера для определения проблемы.

Еще раз спасибо. Mark

PS. Сейчас я начну проверять ответы.

Привет:

Мне нужно сделать некоторые манипуляции с ценами на акции. Я только начал использовать Python (но, думаю, у меня возникнут проблемы с реализацией этого на любом языке). Я ищу некоторые идеи о том, как реализовать это в Python.

Спасибо Mark

Проблема : У меня есть список списков (FloorLevels (см. Ниже)), где у подсписка есть два элемента (stockprice, weight). Я хочу поместить цены в группы, когда они находятся в пределах 0,5% друг от друга. Сила группы будет определяться ее общим весом. Например:

Group-A
115.93,2
115.83,5
115.56,3
115.53,1
-------------
TotalWeight:12
-------------
Group-B
113.50,3
112.95,1
112.85,2
-------------
TotalWeight:6
-------------    

FloorLevels[   
[175.24,8]
[147.85,6]
[144.13,8]
[130.44,6]
[127.79,8]
[127.42,5]
[120.94,6]
[120.22,5]
[118.10,3]
[116.73,2]
[116.23,1]
[115.93,2]
[115.83,5]
[115.56,3]
[115.53,1]
[114.79,2]
[114.59,1]
[113.99,2]
[113.89,1]
[113.50,3]
[112.95,1]
[112.85,2]
[112.25,1]
[112.05,2]
[111.31,1]
[110.97,3]
[110.91,2]
[110.87,4]
[108.91,3]
[108.64,5]
[106.37,3]
[104.31,3]
[104.25,5]
[103.53,6]
[99.42,7]
[97.05,5]
[96.68,8]
[94.03,6]
[92.66,5]
[80.34,8]
[76.62,6]
[67.12,6]
[49.23,8]
[32.89,8]
]

Answer 1

Я предлагаю повторное использование k-средних кластеров - для краткости будем называть это KMC. KMC - это простой и мощный алгоритм кластеризации ... но ему нужно «указать», сколько кластеров, k, к которым вы стремитесь. Вы не знаете этого заранее (если я вас правильно понимаю) - вам просто нужно наименьшее k, чтобы никакие два элемента, «сгруппированные вместе», не были бы более чем на X% друг от друга. Итак, начните с k равно 1 - все сгруппировано, проход кластеризации не требуется ;-) - и проверьте диаметр кластера («диаметр» кластера, исходя из использования термина в геометрии, равен наибольшее расстояние между любыми двумя членами кластера).

Если диаметр равен > X%, установите k += 1, выполните KMC с k в качестве числа кластеров и повторите проверку итеративно.

В псевдокоде:

def markCluster(items, threshold):
    k = 1
    clusters = [items]
    maxdist = diameter(items)
    while maxdist > threshold:
        k += 1
        clusters = Kmc(items, k)
        maxdist = max(diameter(c) for c in clusters)
    return clusters

при условии, конечно, что у нас есть подходящие функции diameter и Kmc Python.

Это похоже на то, что вы хотите? Если это так, то мы можем перейти к тому, чтобы показать вам, как писать diameter и Kmc (на чистом Python, если у вас есть относительно ограниченное число items, с которыми можно иметь дело, в противном случае, возможно, воспользовавшись мощным сторонним дополнением - на таких фреймворках, как numpy) - но не стоит идти на такие неприятности, если вы действительно хотите что-то совсем другое, откуда эта проверка! -)

Answer 2

Вам необходимо указать свою проблему более подробно. Что означает «поместить цены в группы, когда они находятся в пределах 0,5% друг от друга»?

Возможности:

(1) каждый член группы находится в пределах 0,5% от каждого другого члена группы

(2) отсортировать список и разбить его, где разрыв больше 0,5%

Обратите внимание, что 116,23 находится в пределах 0,5% от 115,93 - abs((116.23 / 115.93 - 1) * 100) < 0.5 - но вы поместили один номер в группу A и один в группу C.

Простой пример: a, b, c = (0.996, 1, 1.004) ... Обратите внимание, что a и b соответствуют, b и c соответствуют, но a и c не подходят. Как вы хотите их сгруппировать и почему? Соответствует ли порядок в списке ввода?

Возможность (1) создает правило разрыва связи ab, c или a, bc ..., пожалуйста
Возможность (2) производит abc (без больших пробелов, поэтому только одна группа)

Answer 3

Акция s принадлежит группе G, если для каждой акции t в G, s * 1,05> = t и s / 1,05 <= <code>t, справа

Как мы добавляем акции в каждую группу? Если у нас есть акции 95, 100, 101 и 105, и мы начинаем группу с 100, а затем добавляем 101, мы получим {100, 101, 105}. Если бы мы сделали 95 после 100, мы бы получили {100, 95}.

Нужно ли нам просто рассмотреть все возможные перестановки? Если это так, ваш алгоритм будет неэффективным.

Answer 4

Вы не сможете классифицировать их по категориям. Если у вас есть цены (1.0,1.05, 1.1), то первое и второе должны быть в одной группе, а второе и третье - в одной группе, но не первая и третья.

Быстрый, грязный способ сделать что-то полезное:

def make_group_function(tolerance = 0.05):
    from math import log10, floor
    # I forget why this works. 
    tolerance_factor = -1.0/(-log10(1.0 + tolerance))
    # well ... since you might ask
    # we want: log(x)*tf - log(x*(1+t))*tf = -1, 
    # so every 5% change has a different group. The minus is just so groups 
    # are ascending .. it looks a bit nicer.
    #
    # tf = -1/(log(x)-log(x*(1+t)))
    # tf = -1/(log(x/(x*(1+t))))
    # tf = -1/(log(1/(1*(1+t)))) # solved .. but let's just be more clever
    # tf = -1/(0-log(1*(1+t)))
    # tf = -1/(-log((1+t))
    def group_function(value):
        # don't just use int - it rounds up below zero, and down above zero
        return int(floor(log10(value)*tolerance_factor))
    return group_function

Использование:

group_function = make_group_function()
import random
groups = {}
for i in range(50):
    v = random.random()*500+1000
    group = group_function(v)
    if group in groups:
        groups[group].append(v)
    else:
        groups[group] = [v]

for group in sorted(groups):
    print 'Group',group
    for v in sorted(groups[group]):
        print v
    print

Answer 5

Для элемента группировки не могли бы вы использовать itertools.groupby ()? Поскольку данные отсортированы, большая часть работы по их группировке уже выполнена, и затем вы можете проверить, было ли текущее значение в итерации отличным от последнего на <0,5%, и сделать так, чтобы itertools.groupby () разбился на новая группа каждый раз, когда ваша функция возвращает false. </p>

Answer 6

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

Я сделал здесь два класса с минимумом желаемого поведения, но это может значительно упростить классификацию - вы получаете одно очко, чтобы играть с ним в классе группы.

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

from copy import copy

class Group(object):
    def __init__(self,data=None, name=""):
        if data:
            self.data = data
        else:
            self.data = []
        self.name = name

    def get_mean_stock(self):
        return sum(item[0] for item in self.data) / len(self.data)

    def fits(self, item):
        if 0.995 < abs(item[0]) / self.get_mean_stock() < 1.005:
            return True
        return False

    def get_weight(self):
        return sum(item[1] for item in self.data)

    def __repr__(self):
        return "Group-%s\n%s\n---\nTotalWeight: %d\n\n" % (
            self.name,
            "\n".join("%.02f, %d" % tuple(item) for item in self.data ),
            self.get_weight())


class StockGrouper(object):
    def __init__(self, data=None):
        if data:
            self.floor_levels = data
        else:
            self.floor_levels = []

    def get_groups(self):
        groups = []
        floor_levels = copy(self.floor_levels)
        name_ord = ord("A") - 1
        while floor_levels:
            seed = floor_levels.pop(0)
            name_ord += 1
            group = Group([seed], chr(name_ord))
            groups.append(group)
            to_remove = []
            for i, item in enumerate(floor_levels):
                if group.fits(item):
                    group.data.append(item)
                    to_remove.append(i)
            for i in reversed(to_remove):
                floor_levels.pop(i)
        return groups

Тестирование:

floor_levels = [  [stock. weight] ,... <paste the data above> ]
s = StockGrouper(floor_levels)
s.get_groups()

Answer 7

Для данного набора цен на акции, возможно, существует более одного способа сгруппировать акции, которые находятся в пределах 0,5% друг от друга. Без каких-либо дополнительных правил группировки цен невозможно быть уверенным, что ответ сделает то, что вы действительно хотите.