0x00 сводка
В этой статье используются примеры, которые помогут вам глубже понять концепцию энтропии и алгоритма дерева решений ID3.
0x01 ИТ-концепция
1. Информация и информационная энтропия вещей
1.1 Информация о вещах (чем больше информации, тем больше достоверность)
Информация меняет ваше незнание и любопытство к вещам. Чем больше у вас информации, тем больше вы знаете о вещах, и вам меньше любопытно, потому что вы более уверены в вещах. Если вы уверены, что вероятность наступления события равна 100%, вы считаете, что информативность этого события равна 0 - не так ли, раз оно подтверждено, информативности нет; наоборот, если вы не уверен в этом событии, Вам нужно понимать его по-разному, а значит, это дело содержательное и информативное.
1.2 Информационная энтропия
Чтобы абстрагировать приведенную выше модель, умный Шеннон обобщил понятие информационной энтропии. Информационная энтропия используется для выражения степени неопределенности вещи.Чем выше неопределенность вещи и больше ваше любопытство, тем выше будет информационная энтропия вещи. Неопределенность исхода близкой игры выше, чем у игры, где исход виден, насколько он интуитивен!
Другими словами, количество информации обратно пропорционально вероятности события. Например, событие восхода солнца с востока имеет высокую вероятность, а объем информации будет очень мал. Напротив, солнце встает с запада, вероятность очень мала, а объем информации будет большим (мир кардинально изменится). Поэтому информационная энтропия часто используется как количественный показатель информативности системы, который в дальнейшем может быть использован как цель оптимизации уравнений системы или критерий выбора параметров. Другими словами, информационная энтропия используется для измерения количества информации, которое может иметь событие в нескольких состояниях, и ее также можно рассматривать как ожидаемое значение количества информации о вероятностном распределении событий:
H(x) = -Σp*log(p)。
其中事件x共有n个状态，i表示第i个状态，底数b通常设为2，也可设为10或e。
H(x)即用以消除这个事件的不确定性所需要的统计信息量，就是信息熵。
Следует также отметить, что когда это событие должно произойти, вероятность его возникновения равна 1, тогда его количество информации равно 0, а информационная энтропия равна 0.
2. Почему информационная энтропия определяется как -Σp*log(p)?
В Интернете можно найти несколько надежных и простых для понимания объяснений:
2.1 Пояснение 1
Количество возможностей для части информации увеличивается экспоненциально с количеством битов. Если выразить в двоичных битах, 1 бит имеет 2 состояния, 2 бит имеет 4 состояния, а N бит имеет 2 ^ N возможных состояний. Количество возможностей увеличивается экспоненциально, а затем экспонента возвращается к линейной форме, которая является логарифмической. Не имеет значения, является ли основание логарифма e или 2, это просто коэффициент масштабирования. Один фрагмент информации — это log, а N фрагментов информации — Nlog. Наконец, энтропия представляет собой степень путаницы со знаком минус, придаваемым физическому смыслу.
2.2 Пояснение 2
Информационная энтропия представляет собой длину кодирования.Чем длиннее кодирование, тем больше количество информации и тем больше информационная энтропия. Итак, есть такое уравнение: p=1/a^np представляет вероятность получения определенного значения, a представляет количество единиц хранения, которые можно сохранить, если оно битовое, то оно равно 2, а n представляет длину кодирования , что можно понимать под информационной энтропией, поэтому общая вероятность должна быть равна a^n, а вероятность получения одного значения равна p=1/a^n. Формула для вывода информационной энтропии: n=-loga(p)
2.3 Пояснение 3
Первый объем информации должен зависеть от распределения вероятностей, поэтому определение энтропии должно быть монотонной функцией вероятности. Второе допущение состоит в том, что две случайные величины независимы друг от друга, тогда количество информации, полученное при наблюдении за двумя переменными по отдельности, должно быть таким же, как количество информации, полученное при одновременном наблюдении за двумя переменными. То есть: h(x+y)=h(x)+h(y). Третье количество информации должно быть больше 0, а четвертое количество информации должно постоянно зависеть от изменения вероятности. Можно показать, что функциональная форма, удовлетворяющая приведенным выше условиям, единственна — logx и, конечно, может быть умножена на произвольную константу.
2.4 Пояснение 4
Из вышесказанного солнце встает на востоке, а заходит на западе, и нетрудно увидеть, что количество информации уменьшается с увеличением вероятности появления, и оно не может быть отрицательным. Кроме того, если у нас есть два несвязанных события A и B, то мы можем знать, что информация об этих двух событиях, происходящих одновременно, равна сумме информации об их соответствующих событиях. То есть h(A,B) = h(A) + h(B). И, согласно теореме Байеса, p(A,B) = p(A) * p(B). Согласно вышеизложенному, определение энтропии должно быть монотонной функцией вероятности. Легко видеть, что определение энтропии h должно быть логарифмической функцией вероятности p(x), поэтому энтропию случайной величины можно определить, используя следующее: h(x)=-log_2p(x). Знак минус здесь нужен только для того, чтобы энтропия была положительной или нулевой, а основание 2 логарифмической функции может быть любым числом, но по общепринятой традиции в качестве основания логарифма используется 2. Мы используем энтропию для оценки среднего информационного содержания всей случайной величины x, и наилучшей мерой среднего значения является математическое ожидание случайной величины.
2.5 Пояснение 5
Если в чемпионате мира участвуют 32 команды, то некоторые команды очень сильны и имеют больше шансов на победу в чемпионате, а некоторые команды имеют очень маленькую вероятность выиграть чемпионат. Точное количество информации должно быть: H = -(p1 * logp1 + p2 * logp2 + ... + p32 * logp32), где p1, ..., p32 - вероятности победы 32 команд в чемпионате соответственно. Когда вероятность каждой команды выиграть чемпионат равна 1/32, H = -(32 * 1/32 * log1/32) = 5. Согласно принципу максимальной энтропии, когда вероятность каждого события одинакова , энтропия самая большая.Эти вещи более неопределенны. Здесь мы только что говорили о том, как его вычислить, так почему же общее количество информации просто суммируется со всеми -p*logp ? Википедия разъяснила мне одним предложением: -logp - количество информации о возможности.Общее количество информации о событии - это количество информации о каждой возможной ситуации, умноженное на вероятность их возникновения, что на самом деле является количество информации Математическое ожидание.
3. Энтропия, соответствующая алгоритму дерева решений ID3
3.1 Энтропия
Он характеризует чистоту любого набора проб. Энтропия количественно определяет единообразие, существующее в наборе образцов, чем чище, тем ниже энтропия.
Предположим, множество S. Если все члены S принадлежат к одному и тому же классу, то Энтропия(S)=0; если количество положительных и отрицательных примеров S равно, то Entropy(S)=1; если количество положительных и отрицательных примеров S не равно, то Entropy(S ) находится между 0 и 1;
То есть: когда все члены принадлежат к одной и той же группе, энтропия множества равна 0. Это значение 0 означает, что в этом наборе нет примеси, и все члены в этом примере истинны. Во втором примере половина элементов положительна, а половина — отрицательна, и в этом случае энтропия имеет максимальное значение, равное 1. В бинарной классификации ансамблевая энтропия находится в диапазоне от 0 до 1.
3.2 Мера получения информации: энтропия.
Прирост информации от атрибута — это ожидаемое снижение энтропии, вызванное использованием этого атрибута для разделения выборок (или, другими словами, ожидаемое уменьшение энтропии при разделении выборок в соответствии с определенным атрибутом). То есть, насколько набор данных становится упорядоченным.
3.3 Душа дерева решений
Опираясь на определенный индекс для разделения дерева для достижения цели классификации/регрессии, всегда надеются, что чем выше чистота, тем лучше.
3.4 Основная идея алгоритма ID3
Основная идея алгоритма ID3 заключается в использовании прироста информации для измерения выбора атрибута и выборе атрибута с наибольшим приростом информации после разделения для разделения. Алгоритм ID3 использует прирост информации как жадный алгоритм для разделения алгоритма и всегда выбирает функцию с наибольшим приростом информации для разделения данных, делая данные более упорядоченными. То есть, если атрибут может получить максимальное ожидаемое снижение энтропии, то позиция этого атрибута ближе к корневому узлу.
Gain(子树的信息增益) = 现在熵 - 如果按照某一个特征来分类得到子树熵 = 熵的变化值
4. Вывод
信息增益（熵减）越大越好 ----> 子树的熵越小越好 -----> 树越不平均越好(越不平均表示纯度越高效果越好，越平均表示某值属于各种不同分类的可能性越大则熵最大) ----> 通过这个特性越能强烈区分开对象越好。
Например, используя хромосомы для суждения о мужчинах и женщинах, разделите их на две группы: «женская» группа должна быть женской, а «мужская» — мужской. Этот эффект лучший. Если судить о мужчинах и женщинах по тому, носят ли они юбки, то в этих двух группах должны быть мужчины и женщины, поэтому стандарт суждения не является хорошим.
5. Как рассчитать энтропию?
def calc_shannon_ent(dataset):
entropy = 0
for 所有类别:
p(本类概率，或者说本类数据在所有数据中的比例) = 本类别出现的个数 / 所有数据个数
entroy -= p * math.log(p,2)
Например, набор данных [1, "да"], [1, "да"].Количество всех данных равно 2, и только этот тип данных "да", поэтому p = 2/2 = 1 . вход = 1 * журнал (1,2) = 0. Например, набор данных [1, "да"], [1, "да"], [1, "нет"]. Тогда количество всех данных равно 3, есть два типа данных "да", «нет», р соответственно 2/3 и 1/3. вход = - (2/3) * журнал ((2/3), 2) - (1/3) * журнал ((1/3), 2) = 0,918.
Секрет этой формулы в том, что 2/3 — это отношение количества записей, у которых значение атрибута «да», к общему количеству записей, а 1/3 — это отношение количества записей, у которых значение «нет», к общему количеству записей.
0x02 Используйте Liangshan Hero, чтобы узнать, как выбирать атрибуты
Ляншаньский герой пообедал и решил, есть ли булочки с зеленым луком. Сейчас есть следующие лидеры: Лу Чжишэнь, У Сун, Гунсунь Шэн, Сун Цзян, У Юн, Чжу Ли, Ли Ин, Янь Шунь, Ле Хэ, Жуань Сяоци.
Соответствующий код
_data_set = [
[0, 1, "yes"], #宋江不是佛教徒，是山东人，吃大葱
[0, 1, "yes"], #吴用不是佛教徒，是山东人，吃大葱
[0, 1, "yes"], #朱仝
[0, 1, "yes"], #李应
[0, 1, "yes"], #燕顺
[0, 1, "yes"], #乐和
[0, 1, "yes"], #阮小七
[1, 1, "yes"], #武松
[1, 0, "no"], #鲁智深是佛教徒，不是山东人，不吃大葱
[1, 0, "no"]] #公孙胜
_labels = ["Buddhist", "山东"]
Yes表示吃大葱，No表示不吃大葱。
1. Рассчитайте «исходную энтропию».
исходная энтропияПросто используйте соотношение есть или не есть зеленый лук для расчета.
Entropy(原有的熵) = Entropy(Yes) + Entropy(No) = 8/10 * log(8/10,2) + 2/10 * log(2/10, 2) = 0.8 * log(0.8,2) + 0.2 * log(0.2, 2) = 0.721928
2. Рассчитайте «новую энтропию» и усиление
2.1 Различать по признаку "монах он или нет"
Если различать по признаку "монах он или нет", то
出家人：鲁智深，公孙胜 ---> 不吃大葱 / 武松 ---> 吃大葱
俗人：宋江，吴用，朱仝，李应，燕顺，乐和 ---> 吃大葱
Мы выяснили, что: один монах ест зеленый лук, а два человека не едят зеленый лук / миряне едят зеленый лук. Думается, что надежнее делить по монахам.
Как рассчитать энтропию и усиление в это время?
俗人：7个人，7个yes。
出家人：3个人，其中1yes，2no
Entropy(按出家人分) = Entropy(俗人) + Entropy(出家人) = (7/10) * Entropy(7 yes) + (3/10) * Entropy(1 yes, 2 no)
Entropy(7 yes) = 7/7 * log(7/7,2) = 0
Entropy(1 yes, 2 no) = 1/3 * log(1/3, 2) + 2/3 * log(2/3, 2) = 0.918
Entropy(按出家人分) = 0.7 * 0 + 0.3 * 0.918 = 0.2754
Gain(按出家人分) = Entropy(原有的熵) - Entropy(按出家人分) = 0.721928 - 0.2754
2.2 Различать по «родному городу»
鲁智深(甘肃平凉)，公孙胜(天津蓟县) ---> 不吃大葱
宋江，吴用，朱仝，李应，燕顺，乐和，武松 (宋朝时候全是山东人) ---> 吃大葱
Это делает различие более тщательным. Поэтому лучше судить об атрибутах по месту происхождения.
Как рассчитать энтропию и усиление в это время?
非山东：2个人，2个no。
山东：8个人，8yes
Entropy(按籍贯分) = Entropy(非山东) + Entropy(山东) = (2/10) * Entropy(2 no) + (8/10) * Entropy(8 yes)
Entropy(2 no) = 2/2 * log(2/2,2) = 0
Entropy(8 yes) = 8/8 * log(8/8, 2) = 0
Entropy(按籍贯分) = 0 + 0 = 0
Gain(按籍贯分) = Entropy(原有的熵) - Entropy(按籍贯分) = 0.721928 - 0
Данные также оказываются разделенными по месту происхождения.
В общем, если вы понимаете, как генерируются ветки, вы понимаете алгоритм ID3. Этот метод выбирает ветви (атрибуты) путем вычисления прироста информации для каждого атрибута и выбора атрибута с наибольшим приростом информации в качестве нового подразделения. Алгоритм считает, что важность атрибута отражается через влияние на энтропию системы.Если много неопределенности можно уменьшить, то это важный атрибут.
0xEE Личная информация
★★★★★★Думая о жизни и технологиях★★★★★★
Публичный аккаунт WeChat:мысли Росси
Если вы хотите получать своевременные новости о статьях, написанных отдельными лицами, или хотите видеть технические материалы, рекомендованные отдельными лицами, обратите внимание.
ссылка 0xFF
blog.CSDN.net/ стабилизировалось…
блог woo woo woo.cn on.com/wang kang/afraid/100…
Блог Woohoo.cn на.com/played nice/afraid…
woohoo.brief.com/afraid/7AC73Поделиться 5No…
woohoo.brief.com/afraid/4 ох 2 не голоден 2 не 56…