Найти наиболее часто встречающиеся комбинации для списка предметов - PullRequest
Новая
       7

Найти наиболее часто встречающиеся комбинации для списка предметов

0 голосов
/ 30 октября 2018

В моем приложении asp.net c # у меня есть следующий список появлений комбинаций элементов. Я хочу перечислить наиболее часто встречающиеся комбинации.

  1. Элемент1
  2. Item1, Item2
  3. Item3
  4. Item1, Item3, Item2
  5. Item3, Item1
  6. Item2, Item1

В соответствии с приведенным выше примером, я должен получить ниже вывод.

Чаще всего встречаются комбинации;

  1. Item1 & Item2 - Количество вхождений равно 3 (# 2, # 4 & # 6)
  2. Item1 & Item3 - Количество случаев 2 (# 4 & # 5)

Моя структура, как показано ниже. 

public class MyList
{
    public List<MyItem> MyItems { get; set; }
}

public class MyItem
{
    public string ItemName { get; set; }
}

Ответы [ 4 ]

0 голосов
/ 30 октября 2018

Вот приблизительный O (N ^ 2) подход:

  • Перебор внешней коллекции (List<List<Item>>)
  • Придумайте способ определения текущей строки, назовите ее rowId
  • Теперь повторяем известные идентификаторы строк (внутренняя итерация).
  • Считайте, когда один из них является полным подмножеством другого; либо текущая строка содержится в предыдущем наборе, либо предыдущий набор содержится в текущей строке. (Это решение, которое вы хотите.) Это работает, увеличивая количество строк, которые вы видели ранее, если они являются подмножеством текущей строки, или отслеживая, сколько раз текущая строка является подмножеством ранее увиденных комбинаций, и устанавливая, что в конце каждой внутренней итерации.

Некоторые предположения:

  • Вас не волнует каждая возможная комбинация предметов, только комбинации, которые уже были замечены.
  • Предметы имеют уникальный идентификатор

Как я уже говорил выше, это O (N ^ 2) подход, поэтому производительность может быть проблемой. Есть также две проверки на членство в подмножестве, что может быть проблемой производительности. Я также просто объединяю и разделяю идентификаторы как строки, вы, вероятно, можете получить более оптимальное решение, настроив другой словарь, который отслеживает идентификаторы. Также есть место для улучшения с Dictionary.TryGetValue. Извлечение нужных наборов предметов оставлено читателю в качестве упражнения, но оно должно быть простым OrderBy(..).Where(...). Но это должно помочь вам начать. 

public class MyItem
{
    public string ItemName { get; set; }
}

class Program
{
    public static void GetComboCount()
    {
        var itemsCollection = new List<List<MyItem>>() {
            new List<MyItem>() { new MyItem() { ItemName = "Item1" } },
            new List<MyItem>() { new MyItem() { ItemName = "Item1" }, new MyItem() { ItemName = "Item2" } },
            new List<MyItem>() { new MyItem() { ItemName = "Item3" } },
            new List<MyItem>() { new MyItem() { ItemName = "Item1" }, new MyItem() { ItemName = "Item3" }, new MyItem() { ItemName = "Item2" } },
            new List<MyItem>() { new MyItem() { ItemName = "Item3" }, new MyItem() { ItemName = "Item1" } },
            new List<MyItem>() { new MyItem() { ItemName = "Item2" }, new MyItem() { ItemName = "Item1" } }
        };

        var comboCount = new Dictionary<string, int>();

        foreach (var row in itemsCollection)
        {
            var ids = row.Select(x => x.ItemName).OrderBy(x => x);
            var rowId = String.Join(",", ids);
            var rowIdCount = ids.Count();

            var seen = false;

            var comboCountList = comboCount.ToList();
            int currentRowCount = 1;

            foreach (var kvp in comboCountList)
            {
                var key = kvp.Key;
                if (key == rowId)
                {
                    seen = true;
                    currentRowCount++;
                    continue;
                }

                var keySplit = key.Split(',');
                var keyIdCount = keySplit.Length;

                if (ids.Where(x => keySplit.Contains(x)).Count() == keyIdCount)
                {
                    comboCount[kvp.Key] = kvp.Value + 1;
                }
                else if (keySplit.Where(x => ids.Contains(x)).Count() == rowIdCount)
                {
                    currentRowCount++;
                }
            }

            if (!seen)
            {
                comboCount.Add(rowId, currentRowCount);
            }
            else
            {
                comboCount[rowId] = currentRowCount;
            }
        }

        foreach (var kvp in comboCount)
        {
            Console.WriteLine(String.Format("{0}: {1}", kvp.Key, kvp.Value));
        }
    }

    static void Main(string[] args)
    {
        GetComboCount();
    }
}

вывод на консоль: 

Item1: 5
Item1,Item2: 3
Item3: 3
Item1,Item2,Item3: 1
Item1,Item3: 2
0 голосов
/ 30 октября 2018

Вы можете создать взвешенный график из вашего списка с весом между двумя узлами, представляющими частоту появления. Этот пост StackExchange содержит некоторую информацию, а также вы можете узнать о матрице смежности на этом предыдущем SO посте здесь .

По-моему, было бы разумно использовать HashSet<Tuple<Item1, Item2>> для представления соединения и сохранения его значения в словаре.

Для нескольких элементов проблема похожа на выяснение того, какой путь был пройден больше всего, в алгоритме обхода пути для графов.

Хотя для очень большого набора данных я рекомендую использовать службы SSAS и SSIS через операторы SQL и запросы анализа динамически с C # для создания анализа корзины рынка, который должен генерировать для вас желаемую статистику.

0 голосов
/ 30 октября 2018

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

Скрипка: https://dotnetfiddle.net/yofkLf

public static void Main()
{
    List<MyItem[]> MyItems = new List<MyItem[]>()
    {
        new MyItem[] { new MyItem("Item1") },
        new MyItem[] { new MyItem("Item1"), new MyItem("Item2") },
        new MyItem[] { new MyItem("Item3") },
        new MyItem[] { new MyItem("Item1"), new MyItem("Item3"), new MyItem("Item2") },
        new MyItem[] { new MyItem("Item3"), new MyItem("Item1") },
        new MyItem[] { new MyItem("Item2"), new MyItem("Item1") }
    };
    Dictionary<Tuple<string, string>, int> results = new Dictionary<Tuple<string, string>, int>();      
    foreach (MyItem[] arr in MyItems)
    {
        // Iterate through the items in the array. Then, iterate through the items after that item in the array to get all combinations.
        for (int i = 0; i < arr.Length; i++)
        {
            string s1 = arr[i].ItemName;
            for (int j = i + 1; j < arr.Length; j++)
            {
                string s2 = arr[j].ItemName;
                // Order the Tuple so that (Item1, Item2) is the same as (Item2, Item1).                    
                Tuple<string, string> t = new Tuple<string, string>(s1, s2);
                if (string.Compare(s1, s2) > 0)
                {
                    t = new Tuple<string, string>(s2, s1);  
                }
                if (results.ContainsKey(t))
                {
                    results[t]++;
                }
                else
                {
                    results[t] = 1;
                }
            }
        }
    }
    // And here are your results.
    // You can always use Linq to sort the dictionary by values.
    foreach (var v in results)
    {
        Console.WriteLine(v.Key.ToString() + " = " + v.Value.ToString());
        // Outputs:
        // (Item1, Item2) = 3
        // (Item1, Item3) = 2
        // (Item2, Item3) = 1
    }
}

... 

public class MyItem
{
    public string ItemName { get; set; }
    public MyItem(string ItemName)
    {
        this.ItemName = ItemName;   
    }
}

Конечно, это было бы иначе, если бы у вас не было этого строкового свойства в MyItems.

0 голосов
/ 30 октября 2018

Вдобавок к моей голове, я бы отобразил все возможные комбинации, используя хэш, где ab - это то же самое, что и ba (или вы могли бы упорядочить элементы в алфавитном порядке, например, а затем хэшировать их), а затем просто подсчитывать вхождения хешей ...

...