как найти максимально частые наборы элементов из большого файла транзакционных данных - PullRequest
Новая
       11

как найти максимально частые наборы элементов из большого файла транзакционных данных

0 голосов
/ 24 апреля 2010

У меня входной файл содержит большое количество транзакций, как

Элементы идентификатора транзакции 

T1 Bread, milk, coffee, juice
T2 Juice, milk, coffee
T3 Bread, juice
T4 Coffee, milk
T5 Bread, Milk
T6 Coffee, Bread
T7 Coffee, Bread, Juice
T8 Bread, Milk, Juice
T9 Milk, Bread, Coffee, 
T10 Bread
T11 Milk
T12 Milk, Coffee, Bread, Juice

Я хочу появление каждого уникального предмета, как 

Item Name Count
Bread  9
Milk   8
Coffee 7
Juice  6

альтернативный текст http://www.ade -technologies.com / OrderFP_Tree.jpg

и теперь я хочу создать fp-дерево, пройдя по этому дереву, я хочу получить максимально частые наборы элементов следующим образом

Основная идея метода заключается в расположении узлов в каждом «слое» снизу вверх. Понятие «слой» отличается от общего понятия «слой» в дереве. Узлы в «слое» означают, что узлы соответствуют одному и тому же элементу и находятся в связанном списке из «Таблицы заголовков». Для узлов в «слое» метод NBN будет использоваться для расположения узлов слева направо по связанному списку. Чтобы использовать метод NBN, два дополнительных поля будут добавлены к каждому узлу в упорядоченном дереве FP. Тег поля узла N хранит информацию о том, является ли N максимально частым набором элементов, а счетчик полей хранит информацию подсчета поддержки в узлах слева.

На рисунке первым узлом, который должен быть удален, является «сок: 2». Если min_sup равно или меньше 2, то «хлеб, молоко, кофе, сок» является максимально частым набором элементов. Сначала выведите сок: 2 и установите для тега поля «coffee: 3» значение «false» (изначально тег поля каждого узла был «true»). Затем проверьте, правильно ли выбраны четыре сока наборов: 1 будет подмножеством сока: 2. Если набор элементов одного узла «сок: 1» соответствует подмножеству сока: 2 установите тег поля узла «ложь». В следующем процессе, когда тег поля удаленного узла равен FALSE, мы можем опустить узел после того же тегирования. Если min_sup больше 2, тогда проверьте, правильные четыре сока: 1 является подмножеством сока: 2. Если набор элементов одного узла «сок: 1» соответствует подмножеству сока: 2, то установите счетчик полей «узла с суммой предыдущего счета» и 2 После того, как все узлы «сок» утилизированы, начинайте утилизировать узел «кофе: 3».

Любые предложения или доступный исходный код, добро пожаловать.

заранее спасибо

1 Ответ

0 голосов
/ 27 апреля 2010

Это можно сделать прямо в SQL 

CREATE TABLE dbo.TestTable
( FIELD1 VARCHAR(256) )
GO

INSERT INTO dbo.TestTable(FIELD1) VALUES
('T1 Bread, milk, coffee, juice')
INSERT INTO dbo.TestTable(FIELD1) VALUES
('T2 Juice, milk, coffee')
INSERT INTO dbo.TestTable(FIELD1) VALUES
('T3 Bread, juice')
INSERT INTO dbo.TestTable(FIELD1) VALUES
('T4 Coffee, milk')
INSERT INTO dbo.TestTable(FIELD1) VALUES
('T5 Bread, Milk')
INSERT INTO dbo.TestTable(FIELD1) VALUES
('T6 Coffee, Bread')
INSERT INTO dbo.TestTable(FIELD1) VALUES
('T7 Coffee, Bread, Juice')
INSERT INTO dbo.TestTable(FIELD1) VALUES
('T8 Bread, Milk, Juice')
INSERT INTO dbo.TestTable(FIELD1) VALUES
('T9 Milk, Bread, Coffee,')
INSERT INTO dbo.TestTable(FIELD1) VALUES
('T10 Bread')
INSERT INTO dbo.TestTable(FIELD1) VALUES
('T11 Milk')
INSERT INTO dbo.TestTable(FIELD1) VALUES
('T12 Milk, Coffee, Bread, Juice')
GO

--CREATE INDEX TestIndex ON dbo.TestTable(FIELD1)
--GO

;WITH Numbers AS
(
    SELECT ROW_NUMBER() OVER(ORDER BY (SELECT 0)) AS N
    FROM dbo.TestTable T1
    CROSS JOIN dbo.TestTable T2
),
Base AS
(
    SELECT SUBSTRING(FIELD1, 0, CHARINDEX(' ', FIELD1, 0)) AS TRANID,
    UPPER(REPLACE(SUBSTRING(FIELD1, CHARINDEX(' ', FIELD1, 0)+1, DATALENGTH(FIELD1)), ' ', '')) AS ITEMS
    FROM dbo.TestTable
),
Split AS
(
    SELECT TRANID, ITEMS, N, SUBSTRING(ITEMS, N, CHARINDEX(',', ITEMS + ',', N) - N) AS ELEMENT
    FROM Base 
    JOIN Numbers ON N <= DATALENGTH(Base.ITEMS) + 1
    AND SUBSTRING(',' + Base.ITEMS, N, 1) = ','
)
SELECT ELEMENT, COUNT(*) AS TOTAL
FROM Split
GROUP BY ELEMENT
ORDER BY TOTAL DESC

Возвращает 

BREAD   9
MILK    8
COFFEE  7
JUICE   6
        1

Пустая запись приходит через запятую в конце транзакции T9 

T9 Milk, Bread, Coffee,
...