Максимальный и закрытый частый - ответ включен

1 : , В , С , Е 2 : , С , Д , Е 3 : В , С , Е 4 : , С , Д , Е 5 : С , Д , E 6 : A , D ,

Я хочу узнать максимальные частые наборы предметов и закрытые частые наборы предметов .

• Частое множество элементов является максимальным, если оно не имеет частых надмножеств.$X ∈ F$
• Частое множество элементов X ∈ F замкнуто, если у него нет надмножества с той же частотой

Поэтому я посчитал вхождение каждого набора предметов.

{A} = 4 ;  {B} = 2  ; {C} = 5  ; {D} = 4  ; {E} = 6

{A,B} = 1; {A,C} = 3; {A,D} = 3; {A,E} = 4; {B,C} = 2; 
{B,D} = 0; {B,E} = 2; {C,D} = 3; {C,E} = 5; {D,E} = 3

{A,B,C} = 1; {A,B,D} = 0; {A,B,E} = 1; {A,C,D} = 2; {A,C,E} = 3; 
{A,D,E} = 3; {B,C,D} = 0; {B,C,E} = 2; {C,D,E} = 3

{A,B,C,D} = 0; {A,B,C,E} = 1; {B,C,D,E} = 0

Min_Support установлен на // Очень важно. Спасибо Штеффен за напоминание об этом.$50%$

Максимально ли = ?$\{{A,B,C,E\}}$

Имеет ли закрыт = ?$\{{A,B,C,D\}} \ and \ \{{B,C,D,E\}}$

Я нашел немного расширенное определение в этом источнике (которое включает в себя хорошее объяснение). Вот более надежный (опубликованный) источник: CHARM: Мохаммед Дж. Заки и Чинг-цзи Сяо - эффективный алгоритм добычи закрытых предметов .

По данным этого источника:

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


Некоторые замечания:

• Необходимо установить min_support (support = количество наборов элементов, содержащих интересующее подмножество, деленное на количество всех наборов элементов), которое определяет, какой набор элементов является частым . Набор элементов является частым, если его поддержка> = min_support.
• Что касается алгоритма, то рассматриваются только наборы элементов с min_support, когда кто-то пытается найти максимально частые и закрытые наборы элементов.
• Важным аспектом в определении закрытого является то, что не имеет значения, существует ли непосредственный надмножество с большей поддержкой, имеют значение только непосредственные надмножества с точно такой же поддержкой.
• максимальная частая => закрытая => частая, но не наоборот.

Приложение к примеру ОП

Замечания:

• Не проверял подсчет поддержки
• Допустим, min_support = 0,5. Это выполняется, если min_support_count> = 3

{A} = 4; не закрыт из-за {A, E}
{B} = 2; не часто => игнорировать
{C} = 5; не закрыт из-за {C, E}
{D} = 4; не закрыто из-за {D, E}, но не максимально из-за, например, {A, D}
{E} = 6; закрыто, но не максимально из-за, например, {D, E}

{A, B} = 1; не часто => игнорировать
{A, C} = 3; не закрыт из-за {A, C, E}
{A, D} = 3; не закрыт из-за {A, D, E}
{A, E} = 4; закрытый, но не максимальный из-за {A, D, E}
{B, C} = 2; не часто => игнорировать
{B, D} = 0; не часто => игнорировать
{B, E} = 2; не часто => игнорировать
{C, D} = 3; не закрыт из-за {C, D, E}
{C, E} = 5; закрыто, но не максимально из-за {C, D, E}
{D, E} = 4; закрытый, но не максимальный из-за {A, D, E}

{A, B, C} = 1; не часто => игнорировать
{A, B, D} = 0; не часто => игнорировать
{A, B, E} = 1; не часто => игнорировать
{A, C, D} = 2; не часто => игнорировать
{A, C, E} = 3; максимально часто
{A, D, E} = 3; максимально часто
{B, C, D} = 0; не часто => игнорировать
{B, C, E} = 2; не часто => игнорировать
{C, D, E} = 3; максимально часто

{A, B, C, D} = 0; не часто => игнорировать
{A, B, C, E} = 1; не часто => игнорировать
{B, C, D, E} = 0; не часто => игнорировать

Вы можете прочитать об алгоритме APRIORI. Это позволяет избежать ненужных наборов элементов путем умного сокращения.

{A} = 4 ;  {B} = 2  ; {C} = 5  ; {D} = 4  ; {E} = 6

Б не частый, удали.

Создайте и посчитайте наборы из двух предметов (никакой магии пока нет, кроме Bуже вышедшей)

{A,C} = 3; {A,D} = 3; {A,E} = 4; 
{C,D} = 3; {C,E} = 5; {D,E} = 3

Все это часто (обратите внимание, что все, что было, Bне может быть частым!)

Теперь используйте префиксное правило. ТОЛЬКО объединяйте наборы предметов, начиная с одинаковых n-1 предметов. Удалите все, где любое подмножество встречается не часто. Подсчитайте оставшиеся наборы предметов.

{A,C,D} = 2; {A,C,E} = 3; {A,D,E} = 3; 
{C,D,E} = 3

Обратите внимание, что {A,C,D}это не часто. Поскольку нет общего префикса, не может быть большего частого набора элементов!

Обратите внимание, как много меньше работы я сделал!

Для максимальных / закрытых наборов элементов, проверьте наборы / супернаборы.

Обратите внимание, что, например {E}=6, и {A,E}=4. {E}является подмножеством, но имеет более высокую поддержку, т.е. оно закрыто, но не максимально. {A}не является ни тем, ни другим, поскольку не имеет более высокой поддержки, чем {A,E}, то есть является избыточным .