В вашем вопросе более или менее приведены основные варианты использования алгоритма ID3.
Выходные данные ID3 - это классификатор, имеющий структуру двоичного дерева(ID3, C4.5 и др. Часто называют деревьями решений ).Запись в Википедии для Изучение дерева решений на самом деле имеет приличную сводку (на уровне алгоритма) ID3.
Два обычных показателя в ID3, которые определяют, как эта часть данных в данном узлеДолжно быть разделено, называется Информационная энтропия .(Менее используемая метрика - нечистота Джини .) Алгоритм ID3 - это просто анализатор рекурсивного спуска, который проверяет все комбинации переменной / значения и разбивает узел на комбинацию, которая дает наименьшую средневзвешенную энтропию.
Интуитивно, информационная энтропия пытается идентифицировать переменную (столбец) и значение в этой переменной, которая разбивает данные на «лучшие».«Лучший раскол» соответствует нашей интуиции.Это гораздо проще показать, чем описать прозой.Рассмотрим этот набор данных:
Height Weight Age 90 min aerobics/wk? completed 5 mile run?
155 45 31 Yes True
160 51 33 No False
168 52 28 No False
155 61 25 Yes True
169 57 52 Yes True
172 81 35 No False
164 70 23 Yes False
Если данные разбиты на столбец 4 (занимается ли человек аэробикой не менее 90 минут каждую неделю?), Тогда получающиеся две группы меток классов выглядят следующим образом:
Да Группа: [True, True, True, False]
Нет Группа: [False, False, False]
Почти, но не совсем, совершенная гетерогенность средидве группы.Очевидно, что столбец 4 - это «лучшая» переменная для разделения этих данных.
Метрика, используемая в алгоритме ID3 для определения наилучшего разделения, является всего лишь математическим формализмом этой интуиции.
Это не идеальная (математически точная) аналогия, но примерно вы можете думать, что информационная энтропия связана с категориальными переменными (дискретными значениями), поскольку дисперсия связана с непрерывными переменными (числами с плавающей запятой).Другими словами - информационная энтропия (приблизительно) выражает дисперсию (или стандартное отклонение) дискретных данных.
Вот функция python для вычисления энтропии (с использованием NumPy ):
def entropy(arr1) :
import numpy as NP
ue = NP.unique(x)
p, entropy = 0., 0.
for itm in ue :
ndx = arr1 == itm
p += NP.size(x[ndx]) / float(x.size)
entropy -= p * NP.log2(p)
return entropy
Вышеуказанная энтропийная функция - это просто объединение этих двух выражений и приведение к коду:
p(i) = frequency(outcome) = count(outcome) / count(total_rows)
entropy = sum of p(i) x log2(p(i))
Идеальная гетерогенность имеет энтропию = 0, поэтомусамая «различающая» переменная / значение - это такая, при которой при разделении данных на эту переменную и значение средневзвешенная энтропия является самой низкой.Значения энтропии, близкие к 1, почти полностью «смешаны» или почти случайны.
# simulate a data set with three class labels (0 1, 2)
# for your problem, the class labels are the keywords,
# so just map each unique keyword to an integer value (e.g., { 'keyword1' : 0, 'keyword2' : 1}
>>> x = NP.random.randint(0, 3, 20)
>>> x
array([1, 0, 0, 0, 1, 1, 2, 1, 1, 1, 2, 2, 0, 2, 0, 1, 1, 1, 1, 1])
>>> print("{0:.3f}".format(entropy(x)))
0.758
В сумме, для вашей конкретной задачи, чтобы определить наиболее «различающее» ключевое слово, рассчитайте энтропию для каждого из двух классовпометьте списки, затем рассчитайте их средневзвешенное значение (взвешенное по количеству элементов в каждом списке).Ключевое слово, которое приводит к расщеплению с наименьшей средневзвешенной энтропией, - это то, что вы ищете.