Ссылка выше:Ересь Инквизитор! Реализация общей модели кластеризации текста (1)
В прошлый раз мы предложили концепцию, что пока вы вводите кучу строк, вы можете выбирать «меньшинства» на основе структуры строк для выявления аномальных параметров. Мы называем это «Испытание ереси».
В предыдущей статье мы определили некоторые необходимые понятия и написали реализацию функции. Наша программа постепенно определяет разницу между символами, разницу между строками и, наконец, разницу между наборами строк. С этим индикатором мы можем завершить сортировку.
В жизни мы часто сталкиваемся с тем, что несколько рядов людей фотографируются вместе. Иногда передний ряд сидит на корточках, а задний ряд стоит, а иногда низкий человек стоит в первом ряду, а более высокий человек находится в заднем ряду. Представьте, если бы вы были фотографом, приказывающим всем выстроиться в очередь, как бы вы привыкли выстраивать строй?
Обычно вы просто просите встать примерно ровными рядами, а затем корректируете детали одну за другой, пока вся формация не будет выглядеть удовлетворительно.
Это вдохновляет нас на идентификацию «еретиков».
Представьте себе «епископа», стоящего на балконе минарета и смотрящего на толпу под башней, теперь ему нужно разделить людей на две категории, одна в целом заслуживающая доверия, другая несколько подозрительная, а затем одна одним в последнем Когда верующие переходят в первое, «ересь», естественно, остается позади.
В этой статье мы собираемся сделать именно это.
Классифицировать от универсального для всех
Мы начинаем с обработки каждого ввода как отдельного класса, чтобы начать процесс. весь корпусC.
# 初始化
# 输入一个列表，如['a','b','c']
# 输出一个把每个元素都封装为列表的列表，如[['a'],['b'],['c']]
def init(sample_list):
C = []
for x in sample_list:
C.append([x])
return C
На основе ранее определенного расстояния между строками (называемого в статье расстоянием между классами) выбираются и объединяются два ближайших класса.
Этот шаг кажется простым и на самом деле очень простым, но мы столкнемся с некоторыми проблемами: мы использовали списки, чтобы просто представить математическую концепцию множеств, и они не все одинаковы. Из трех основных свойств множеств списки не удовлетворяют беспорядку и взаимности, поэтому требуется дополнительная обработка.
Например, чтобы найти два ближайших класса, нам все равно нужно вычислить расстояния n^2, что является непростой задачей. Обозначим минимальное расстояние какd——
def find_min(C):
# 逻辑告诉我们无论怎样做都必须计算两两之间的全部距离，这里用一个二维列表来记录
# 数学告诉我们 a->b 与 b->a 的距离是一样的，其实开销可以减小一半
# 作者告诉大家由于我很懒，就不做这个优化了……
scale = len(C)
d = [[0 for i in range(scale)] for i in range(scale)]
min_d = classesDistanse(C[0], C[1])
where_min_d = [0, 1]
for i in range(scale):
for j in range(scale):
d[i][j] = classesDistanse(C[i], C[j])
if i != j and d[i][j] < min_d:
min_d = d[i][j]
where_min_d = [i, j]
return where_min_d
нашел самый маленькийdПозже пришло время их объединить. При выполнении операции объединения мы столкнемся с такими проблемами, как разница между свойствами списка и множества и разница в представлении логической операции И. Мы переопределяем функцию операции, чтобы компенсировать эти отклонения.
Если эта часть вызывает у вас небольшое головокружение, не беспокойтесь об этом. Вы можете думать о них обоих как о грязных хаках, помните, что мы просто делаем простую вещь: объединяем два набора с наименьшими расстояниями между классами, которые мы только что нашли, и объединяем их в один.
# C:=C-Ci-Cj+CiUCj
# 输入全集列表C及其选出的两个子列表Ci、Cj，如C=[['a'],['b'],['c']]，Ci=['a'], Cj=['b']
# 需要注意的是，逻辑上，集合Ci与集合Cj是集合C的【元素】，而交并差都是【集合】之间的运算
# 输出合并Ci与Cj之后的全集列表，如[[['a'],['b']],['c']]
def merge(C, i, j):
# 在数学上，集合[[1],[2]]与集合[[1,2]]的并集有三个元素，因为[1],[2],[1,2]都是完全不同的元素。但在这里的逻辑上，需要结果为[[1,2]]，所以另外定义了特殊的“交集”运算
# 交集与差集的运算是针对集合的（如[[1]]）而非元素（如[1])，所以需要手动装进列表再传参。（其实已经特殊处理的交集运算无必要这样做，但为了逻辑一致遵守了统一的写法）
C_u = special_union([C[i]], [C[j]])
C_d = difference(difference(C, [C[i]]), [C[j]])
C_n = C_d
C_n.append(C_u)
return C_n
Мы объединили два ближайших класса в один класс, и цель состоит в том, чтобы «подогнать всех под одну гребенку», то есть разделить весь корпус примерно даже на два класса. Поэтому мы продолжаем искать два ближайших класса и объединять их до тех пор, пока не будет найден набор, сумма которого превышает половину полного набора.
# 查找规模最大的一个子列表
# 输入全集C，如[[['a'],['b']],['c']]
# 输出规模最大即集合内元素最多的列表的下标，如 0
def find_largest(C):
s = [0] * len(C)
max_s = len(C[0])
where_max_s = 0
for x in range(len(C)):
s[x] = len(C[x])
if s[x] > max_s:
max_s = s[x]
where_max_s = x
return where_max_s
Каждый шаг был определен, и весь рабочий процесс выглядит следующим образом:
def layerClassification(sample_list):
C = init(sample_list)
while True:
where_min_d = find_min(C)
i, j = where_min_d
C = merge(C, i, j)
where_max_s = find_largest(C)
if count_elem(C[where_max_s]) > 0.5 * len(C):
break
CM = C[where_max_s]
CN = difference(C, [CM])
return flatten(CM), flatten(CN)
В этом коде упоминаются две вспомогательные функции, гдеcount_elem()Он используется для рекурсивного обхода количества строк, фактически содержащихся в каждом наборе (вместо количества подэлементов).Конечным результатом классификации может оказаться сложный многомерный список, и нам нужны только два простых -мерные списки для представления двух наборов, определитьflatten()расширить гнездо.
ты! Иди туда!
После только что проведенной классификации у нас теперь есть два набора. Один из них содержит элементы, которые изначально были сгруппированы, они могут выглядеть очень похоже, а оставшаяся половина просто оставлена.
Далее настало время «тонкой настройки»: нужно по одному переместить «верующих» из набора, забитого грязью и песком, в относительно аккуратный набор впереди, чтобы изолировать «ересь».
Дело здесь в том, когда остановиться: в какой момент в этом хаотическом множестве останется только «ересь» и ни одной ошибочно прощенной «ереси»?
К счастью, нашему епископу не нужно ни о чем сожалеть: если он сделает неправильный ход, он вернется. Он даже может приказать перечислить все результаты и позволить ему решить, какой план лучше.
Тогда мы могли бы также игнорировать процесс принятия решений и предоставить все решения.
Обозначим классификационную схему какS, схема классификации состоит из двух множеств, а именно {C1, C2}, и снова мы используем списки для их представления. Чтобы хранить C1 и C2 в каждый момент в процессе непрерывного движения, а не следовать за изменениями как ссылки, нам нужно использовать глубокие копии.
def note_solution(S, C1, C2, N):
_C1 = copy.deepcopy(C1)
_C2 = copy.deepcopy(C2)
S.append([_C1, _C2])
N = N + 1
return S
На основе ранее определенных межклассовых расстояний мы можем выбрать образцы в C2, наиболее близкие к C1:
def select_min(C1, C2):
min_x = C2[0]
min_d = classesDistance(C1, min_x)
for x in C2:
temp = classesDistance(C1, x)
if temp < min_d:
min_d = temp
min_x = x
return min_x
Поместите этот образец из C2 в C1:
def update(min_x, C1, C2):
C1.append(min_x)
C2.remove(min_x)
return [C1, C2]
Мы продолжаем перемещать элементы, пока не опустеет некластеризованный C2. Задокументируйте все схемы классификации во время этого процесса. В дополнение к полной схеме классификации S мы также поддерживаем еще один список перемещенных элементов для облегчения вызова. Поскольку все элементы в этом списке являются элементами с наименьшим расстоянием до C1, выбранным на каждом шаге, мы могли бы также назвать этот список какM, весь процесс выглядит следующим образом:
def iterateClassification(C):
N = 0
S = []
M = []
C1 = C[0]
C2 = C[1]
while True:
note_solution(S, C1, C2, N)
min_x = select_min(C1, C2)
M.append(min_x)
update(min_x, C1, C2)
if len(C2) == 0:
break
del(S[0])
return S, M
До сих пор мы неоднократно использовали межклассовое расстояние, определенное в предыдущей статье, делали грубую выборку и перечисляли все сгенерированные решения тонкой настройки. Лучшее решение должно быть одним из них, и у нашего архиепископа осталась только одна оптимизационная задача.
Увидимся в следующий раз~
Примечание редактора:
Эта статья еще не закончена, ждите продолжения. Ссылки и сопоставленный пример кода будут даны в конце полной статьи.
Искусство /YvesX
Вы все равно не можете догадаться, что я делаю
Монтаж/Флуоресценция
Эта статья авторизована и опубликована автором Chuangyu Front-end, а авторские права принадлежат автору, созданному Chuangyu Front-end. Пожалуйста, укажите источник для перепечатки этой статьи. Ссылка на статью:woohoo.yves.com/archives/ и…
Если вы хотите подписаться на другие сообщения с передовой линии KnownsecFED, выполните поиск и подпишитесь на нашу общедоступную учетную запись WeChat: KnownsecFED. Добро пожаловать, чтобы оставить сообщение для обсуждения, мы ответим как можно скорее.
Спасибо за чтение.