23. Алгоритм к внутригрупповых средних.

Пусть задано мн-во образов X₁,…,X_N.

1 шаг. Выбир-ся К исходных центров кластеров

z₁(1), z₂(1), z₃(1),…, z_k(1) Обычно берутся 1-ые К рез-тов выборки из заданного мн-ва образов

2 шаг. На К-ом шаге итерации заданное мн-во Х распред-ся по К кластерам след. образом xSj(k) если ||x-Zj(k)||<=||x-z_i(k)|| i=1…k i<>j,

где Sj(k) - мн-во образов, входящих в кластер с центром z_j(k)

3 шаг. На основании результата 2шага выбир-ся новые центры кластеров z(k+1) исходя из того, что расстояние м/у всеми образами в S_j(k) и новым центром будет минимально.

j=1,2,..k

где Nj — число выборочных образов, входящих в множество S_j(k)

4 шаг. Если z_j(k+1)=z(k), то алг-м останавливается Иначе происходит новое разбиение и алг-м продолжается до тех пор, пока не будет найдено оптим. решение.

24. Алгоритм isodata.

Общая стр-ра алг-ма такова:

Задан набор исходных центров кластеров

z₁, z₂,…, z_Nc и набор образов {x₁, x₂,…, x_N}.

1. Формир-ие подмн-в выборочных множ-в Sj.

2. Слияние кластеров(если треб-ся с переходом на 1).

3. Расщепление кластеров (если требуется с переходом на 1).

При этом исп-ся след. эвристики:

1. Ликвидация кластеров с числом эл-тов меньше заданного знач-я.

2. Объедин-е кластеров, нах-ся близко др.к др.

При объед-и кластеров с центрами Zi и Zj образ-ся 1 кластер с центром

Расщепление кластера м/т происходить по одному из след. критериев:

1. При достаточно сильной разбросанности образов расщепляемого кластера в масштабе общего множ-ва образов.

2. Если треб-ся получить дост-но большое число кластеров.

25. Дост-ва и нед-ки алг-ов обуч-я без учителя.

-: необх-ть проведения обширных экспериментов, трудность применения к данным сложной стр-ры.

+: простота реализ-и, примин-е эвристич. подходов.

26. Изображающие числа и базис.

Базис - табли­ца, к-рая представляет все возможные комбинации значений истинности нек-го набора элементов А, В, С, ... .

Для п элем-в А₁, ..., А_п базис содержит п строк и 2ⁿ колонок. Тогда базис для одного элемента:

#A=0 1;

для двух элементов A и B:

0 1 2 3

#A = 0 1 0 1

#B = 0 0 1 1

Строки базиса наз-т изображающими числами соотв-щих элем-в и обоз-ют приписыванием слева от элем-та знака #.

Операции над изобр числами: 1) ИЧ дизъюнкции 2х элем-в = сумме ИЧ слагаемых: #(A + B)= #А + #B, 2) ИЧ конъюнкции 2х элем-в опред-я как произведение ич сомножителей: #(A•B)=( #А)•(#B ), 3) ич отрицания А^- получ-ся из ич А заменой в каждом разряде 0 на 1 и 1 на 0.

27. Восстан-е булевой ф-ции по ич.

Пусть есть мн-во, состоящее из п элементов

А₁, ..., А_п. Произв-ие вида А₁ •А2...А_п-1 •А_п, составленное из эл-тов Ai, или их отрицаний Аi^- и содержащее п сомножителей, наз-ся элемен­тарным произв-ем. Из п элементов м/о составить 2ⁿ различ. элем-ых произведений. ИЧ каждого элем-го произв-я имеет только одну “1” в одном из 2ⁿ разрядов.

(СДНФ) булевой ф-ции — сумма элемент. произв-й. Чтобы по данному ИЧ восстановить булеву функ­цию в СДНФ, нужно суммир-ть элемент. произвед-я, изображающие числа к-рых имеют единицы в тех же разря­дах, что и изобр.числа булевой ф-ции

(КНФ). Элементарными суммами для п элементов А₁, ..., А_п называются суммы вида A₁+A₂+...A_n-1+A_n, составленные из элементов A_i или их отри­цаний A_j и содержание п слагаемых. Из п элементов можно составить 2ⁿ элементарных сумм. Изображающие числа элемен­тарных сумм содержат только один 0 в одном из 2ⁿ разрядов

КНФ булевой функции пред­ставляет собой произв-ие элем-ых сумм. Для того чтобы написать булеву функцию, соответствующую данному изображ-му числу в КНФ, необходимо перемножить эле­мен-ые суммы, изображ. числа кот-х имеют те же 0, что и изображ-ее число булевой функции.