Алгоритм ТКС

сбор данных

Написано ранее: Последовательный анализ шаблонов уже является широко исследуемой областью, и для решения проблемы неэффективного времени, необходимого для нахождения подходящих порогов, на повестку дня естественным образом ставятся идеи top-k. В поле top-k наиболее важной ссылкой является способ быстрого увеличения порога, поэтому мы в основном изучаем идею исследования локального приоритета этого алгоритма.

Efficient Mining of Top-K Sequential Patterns

вводить

Последовательный анализ шаблонов (sequential pattern mining) — это широко изучаемая проблема интеллектуального анализа данных, которая очень помогает при анализе сетевых кликов, выполнении программ, медицинских данных, биологических данных и т. д. Критерием таких алгоритмов является порог поддержки (support threshold), задав минимальный порог (minsup), ищите тех, чья поддержка (support) больше указанного порога для подпоследовательностей, которые считаются интересными. Но проблема в том, что в большинстве случаев соответствующий порог получить не так просто, и для получения удовлетворительного результата требуется повторное тестирование. Поэтому, интегрируя идею top-k, оставляя в стороне проблему установки порога и выбора наилучшей части в качестве желаемого результата, эта идея в определенной степени снижает затраты памяти и времени алгоритма, а также делает людей более привлекательный, простой для понимания. Алгоритм, представленный в этой статьеTKSоснован наSPAMАлгоритмы улучшены благодаря новым структурам данныхPMAP (Precedence Map)уменьшатьплатитьоперации и, конечно же, некоторые стратегии повышения порога и стратегии обрезки

Решать проблему

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

Стратегия

Повышение порога

похожий наkHMCОбычная стратегия порогового продвижения в алгоритме, каждый раз, когда получается кандидат, удовлетворяющий пороговому условию (не очень частые шаблоны), кандидат записывается и его поддержка сохраняется.Когда количество коллекций больше, чемkкогда первыйkБольшая поддержка используется в качестве текущего порога, а затем используется в следующем процессе майнинга.

Стратегия масштабирования

Общие расширения интеллектуального анализа последовательностей:s-extensionиi-extension,существуетэпизодическая добыча полезных ископаемыхОн уже был представлен в деталях и не будет здесь подробно останавливаться.Алгоритм ТКСПредставлена ​​идея, которая максимально расширяет поддержку/последовательность (Локальная оптимальная идея). Алгоритм использует переменную для отслеживания того, какие элементы/последовательности в настоящее время глубоко расширяются, всегда сначала расширяя шаблоны с наивысшей поддержкой.

Стратегия обрезки

PMAP_structure.png

Вверху слеваАлгоритм спамакаждого предоставленного товараbit vector, по сути, рассматривайте набор данных какдлинная последовательность, когда элемент появляется в наборе элементов, ему присваивается значение 1, в противном случае он равен 0, поэтому можно задать естественный вопрос: если набор данных велик, сколько времени потребуется, чтобы получить этиbit vectors? Во-вторых, просто поbit vectorsПересечение для расчета поддержки более длинных последовательностей позволяет получить последовательности, которых нет в наборе данных, поэтому правая часть приведенного выше рисункаАлгоритм ТКСкаждого предоставленного товараСтруктура карты. Сканируя набор данных, запишите масштабируемый элемент каждого элемента, частоту расширенных условий, а также расширение S-расширения или I-расширения), а алгоритм будет строить точки времени, чтобы уменьшить масштаб. Положите его после удаления Низкое время частоты,Хотя для этого требуется второе сканирование набора данных. Принцип согласуется с Aprioir: элементы низшего порядка не могут формировать наборы элементов высокого порядка благодаря этому вновь созданному набору элементов.PMAP, легко узнать, какие из них не могут создавать высокочастотные наборы элементов высокого порядка, а затем избегать использованияbit vectorвыполнить операцию пересечения

Ps. Оптимизация также упоминается в статье.bit vectorМетод эффективности, вы можете обратиться к следующему процессу реализации кода

	/**
	 * Set a bit to 1 in this bitmap
	 * @param sid the sid corresponding to that bit
	 * @param tid the tid corresponding to that bit
	 * @param sequencesSize the list of sequence length to know how many bits are allocated to each sequence
	 */
	public void registerBit(int sid, int tid, List<Integer> sequencesSize) {
		// calculate the position of the bit that we need to set to 1
		int pos = sequencesSize.get(sid) + tid;
		// set the bit to 1
		bitmap.set(pos, true);
		
		// Update the count of bit set to 1
		if(sid != lastSID){
			support++;
			sidsum += sid;
		}

		if(firstItemsetID == -1 || tid < firstItemsetID){
			firstItemsetID = tid;
		}
		
		// remember the last SID with a bit set to 1
		lastSID = sid;
	}

алгоритм

TKS main procedure

TKS_algorithm.png

Output procedure

Output_procedure.png

Search procedure

Search_procedure.png

Суммировать

По окончательным экспериментальным данным,Алгоритм ТКСПревосходствоkВ случае большого значения правильный результат все же можно получить за короткое время. Однако я лично считаю, что битовый вектор не обязательно должен записывать вхождение всей длинной последовательности.Каждая последовательность может быть пронумерована.Нужно только использовать карту для записи, в каких идентификаторах появляется каждый элемент, что может уменьшить расчет в определенной степени Рабочая нагрузка; я лично считаю, что наиболее достойным упоминания является проведение как можно более глубокого исследования шаблонов с высокой поддержкой, потому что это алгоритм top-k, его можно генерировать более высокая поддержка в случае высокой поддержки (хотя вероятность становится все ниже и ниже), но он также может заранее сократить другие наборы элементов с низкой поддержкой, чтобы избежать избыточной рабочей нагрузки.

Категории