Shyhartskoi 30 янв 2023 в 17:01

Введение в нечёткую логику

9 мин

18K

Блог компании Timeweb CloudПрограммирование*Алгоритмы*

Туториал

Перевод

Автор оригинала: Daniel Sioson

Вы когда-нибудь подумывали написать такой алгоритм, в соответствии с которым приложение само принимало бы решения, либо справлялось с какими-нибудь странными действиями, при помощи которых клиент отчаянно пытается его сломать?

Создавая такой алгоритм, вы заметите, что просто замусориваете ваш код логикой if-else (пока он не превратится в кашу), а самим вам начинает казаться, что вот так просто не прокатит.

Итак, если только вас не пробирает дрожь от математики – читайте дальше. Здесь в дело вступает нечёткая логика! Немного контекста: слово «нечёткий» (англ. «fuzzy») в данном случае означает «труднопонимаемый» — таков может быть, например, код вашего коллеги.

В этом посте я постараюсь объяснить нечёткую логику и объяснить, как она работает.

❯ Что такое нечёткая логика?

Если просто – это логика, имитирующая мышление живого человека. Теперь представьте, чего можно добиться нечёткой логикой, помноженной на вычислительную мощность вашего ЦП – совершенно очевидно, что такой алгоритм сможет принимать решения быстрее вас.

Это просто расширение булевой логики – той самой, что оперирует 0 и 1.

❯ С какой же целью она создавалась?

Профессор Заде, автор нечёткой логики, считал, что людям не требуется такой ввод как машинам, но люди крайне адаптивны. Думаю, вам не нужно устанавливать в мозг специальную программу, чтобы разобраться, как есть пиццу.

Чтобы алгоритм нечёткой логики думал «по-нашему», он должен действовать как человек. Правила, задаваемые нами, выражаются на естественном языке. Например, вот правила, по которым работает воздушный кондиционер:

Если сейчас в комнате холодно, и вы ставите кондиционер на обогрев, то он должен поднять температуру в комнате.
Если сейчас в комнате тепло, а вы ставите кондиционер на поддержание тепла, то температура в комнате не должна измениться.
Если сейчас в комнате жарко, а вы ставите кондиционер на охлаждение, то постепенно кондиционер должен снизить температуру в помещении.

Ниже мы разберём такие правила подробнее.

❯ Использование нечёткой логики

Если вы заинтересовались, может ли нечёткая логика применяться в программировании для решения каких-либо задач кроме использования кондиционера, который мог бы заморозить офис – вот вам примеры:

1. Проверка правописания

Возможно, в детстве задавали по географии домашнюю работу по описанию какой-нибудь реки, и вам достаточно было просто скопировать и вставить нужную информацию из Википедии…

…а вы взяли и выбрали Миссисипи. Конечно, это хорошо, но вы не знали, как именно пишется «Миссисипи», поэтому, берясь за домашнее задание, вы попробовали просто угадать.

К счастью, поисковик умеет предлагать правильную орфографию, подбирая её при помощи нечёткого соответствия (fuzzy matching) и функции проверки правописания.

2. Поиск

Итак, домашнюю работу вы сделали, и готовы отправиться в кроватку – но случайно споткнулись о сетевой кабель, и он оборвался. На родительском компьютере пропал Интернет.

Так что, прежде, чем родители вернутся, вы решаете потратить часть карманных денег и заменить повреждённый кабель. Для начала его нужно купить.

Берёте ноутбук брата, выходите с него в любимый интернет-магазин и вводите в поисковой строке «Провод для интернета». Поскольку не знаете, что такое Ethernet-кабель.

Тадам! Вашему вниманию представлены разнообразные Ethernet-кабели и, даже если вы задали ключевое слово «интернет», алгоритм нечёткого поиска, действующий в магазине, «догадывается», что вам нужно.

3. Рекомендации

Вы оформили покупку и просто ждёте, пока вам доставят новый Ethernet-кабель, а тем временем решили полистать раздел с одеждой, вот так вам хочется. Через несколько секунд натыкаетесь на раздел «Recommend Items» («Рекомендуемые товары»).

Приложение с механизмом нечёткого подбора рекомендаций будет подсказывать вам товары в зависимости от того, что вы покупали ранее, и даже от того, какие товары вы успели посмотреть.

Теперь, чтобы вам было проще разобраться в том, как устроена нечёткая логика, давайте углубимся в тему и начнём с основ. Вы готовы?

❯ Классическая теория множеств

Для начала обратимся к простому разделу математики, в котором изучаются множества –это классическая теория множеств.

В классической трактовке множество – это совокупность определённых вполне различаемых объектов. Рассмотрим следующее изображение:

У нас есть множество чисел от 1 до 5, множество символов от A до E и даже множество слов, например, HTML, JavaScript, CSS и PHP.

❯ Нечёткие множества

Нечёткие множества могут рассматриваться как продолжение классических. В классическом случае элемент может относиться либо не относиться к множеству, тогда как к нечёткому множеству элемент может относиться как целиком, так и на половину, на четверть или на крошечную долю.

Например, говоря: «сейчас холодно» мы не имеем в виду страшный мороз, а говоря: «сейчас жарко» не имеем в виду испепеляющий зной. Обычно мы указываем, в какой степени сейчас жарко или холодно, обычно выражая это значение как температуру в градусах Цельсия.

Разумеется, именно от вас зависит, как вы расположите реальные значения в диапазоне от 0 до 1. Считайте, что 0 и 1 – это процентные значения, записанные в десятичной системе. 1 соответствует 100% и присваивается наилучшему значению, тогда как 0 соответствует 0% и присваивается наихудшему значению.

❯ Лингвистические переменные и значения

Лингвистическими называются такие переменные, в которых слова и даже выражения берутся из обычного разговорного языка. Лингвистические значения – это, в сущности, значения лингвистических переменных.

temperature (t) = {cold, warm, hot}

В вышеприведённом примере temperature – это наша лингвистическая переменная, а cold, warm и hot – это лингвистические значения.

❯ Функция принадлежности и нечёткие правила

В нечётком множестве функция принадлежности определяет значение или точку.

В данном примере мы подаём на ввод три функции принадлежности, скажем:

Холодно
Тепло
Жарко

На вывод также имеем три функции принадлежности:

1. Холодно
2. Без изменений
3. Жарко

Нечёткая логика основана на простом правиле IF-THEN с условием и заключением.

Если сопоставить функции принадлежности с правилами нечёткой логики, то получим следующие инструкции:

IF (temperature is COLD) AND (target is COLD) THEN command is NO-CHANGE

IF (temperature is COLD) AND (target is WARM) THEN command is HEAT

IF (temperature is COLD) AND (target is HOT) THEN command is HEAT

IF (temperature is WARM) AND (target is COLD) THEN command is COOL

IF (temperature is WARM) AND (target is WARM) THEN command is NO-CHANGE

IF (temperature is WARM) AND (target is HOT) THEN command is HEAT

IF (temperature is HOT) AND (target is COLD) THEN command is COOL

IF (temperature is HOT) AND (target is WARM) THEN command is COOL

IF (temperature is HOT) AND (target is HOT) THEN command is NO-CHANGE

В следующей таблице в формате 3 x 3 представлены правила нечёткой логики:

❯ Операции с нечёткими множествами

Вычисления в соответствии с правилами нечёткой логики и комбинирование результатов выполнения отдельных правил – это особый набор операций над нечёткими множествами.

Операции над нечёткими множествами отличаются от стандартных логических операций.

1. Объединение
В данном случае вывод содержит все элементы обоих множеств.

2. Пересечение
В данном случае вывод содержит только общую часть обоих множеств.

3. Отрицание
В данном случае вывод содержит всё то, что не нашлось в множестве.

4. Агрегация
В данном случае вывод содержит комбинацию нечётких множеств, каждое из которых представляет вывод одного из правил.

❯ Дефаззификация

Поскольку вывод операций над нечёткими множествами представляет собой нечёткое значение, нужен способ как-то превратить этот вывод в значения, понятные машинам. Такой процесс называется «дефаззификация».

Нечёткое значение можно дефаззифицировать разными способами. Вот некоторые из них:

Сумма центров
Центроидный метод
Метод центра площади
Средневзвешенный метод
Метод максимума функции принадлежности

❯ Применение нечёткой логики в PHP

Однажды к нам в отдел разработки обратились из HR-отдела и попросили написать приложение, которое позволило бы выбирать наилучшего кандидата из всех, претендующих на позицию веб-разработчика.

В данном посте я опишу эту задачу в упрощённом виде и перечислю только следующие критерии, по которым предполагалось судить о кандидатах:

Опыт соискателя – сколько лет он занимается разработкой веб-приложений.
Балл, набранный соискателем при практическом тестировании.
Балл, набранный соискателем на собеседованиях с командой и с HR.

Допустим, у нас есть следующий список соискателей с соответствующими признаками:

❯ Пишем код

Первым делом мы собирались реализовать нужные нам функции принадлежности и агрегации. Существует много функций агрегации, но ради простоты мы используем одну из самых известных, вычисляющую среднее арифметическое.

/**
 * Получить среднее арифметическое всех признаков
 * @param array $aParams
 * @return float|int
 */
private function getArithmeticMean(array $aParams)
{
    $mCount = (float)count($aParams);
    $mSum = (float)array_sum($aParams);

    return $mSum / $mCount;
}

Функция агрегации – среднее арифметическое

Затем воспользуемся треугольной функцией в качестве функции принадлежности.

/**
 * Треугольная функция принадлежности
 * @param $fApplicantValue
 * @param $aTrimfValues
 * @return float|int
 */
private function getTrimf(float $fApplicantValue, array $aTrimfValues)
{
    $aTrimfValues[0] = (float)$aTrimfValues[0];
    $aTrimfValues[1] = (float)$aTrimfValues[1];
    $aTrimfValues[2] = (float)$aTrimfValues[2];


    if ($fApplicantValue < $aTrimfValues[0]) {
        return 0;
    }

    if ($fApplicantValue >= $aTrimfValues[0] && $fApplicantValue <= $aTrimfValues[1]) {
        return ($fApplicantValue - $aTrimfValues[0]) / ($aTrimfValues[1] - $aTrimfValues[0]);
    }

    if ($fApplicantValue > $aTrimfValues[1] && $fApplicantValue <= $aTrimfValues[2]) {
        return ($aTrimfValues[1] - $fApplicantValue) / ($aTrimfValues[2] - $aTrimfValues[1]) + 1;
    }


    return 0;
}

Треугольная функция в качестве функции принадлежности

Написав функции агрегации и принадлежности, добавим остальной код, который понадобится нам для обработки ввода.

/**
 * Анализируем следующие функции и соискателей
 * @param array $aSetFeatures
 * @param array $aApplicants
 * @return array
 */
public function analyzeItems(array $aSetFeatures, array $aApplicants): array
{
    $aResults = [];

    for ($iCount = 0, $iCountMax = count($aApplicants); $iCount < $iCountMax; $iCount++) {
        $aResults[$iCount]['identifier'] = $aApplicants[$iCount]['identifier'];
        $aResults[$iCount]['score'] = $this->aggregateSet($aApplicants[$iCount], $aSetFeatures);
    }

    return $aResults;
}

/**
 * @param array $aApplicant
 * @param array $aSetFeatures
 * @return float|int
 */
private function aggregateSet(array $aApplicant, array $aSetFeatures)
{
    $aFeatureScores = [];

    for ($iCount = 0, $iCountMax = count($aSetFeatures); $iCount < $iCountMax; $iCount++) {
        $aFeatureScores[$iCount] = $this->getTrimf($aApplicant['features'][$aSetFeatures[$iCount]['identifier']], $aSetFeatures[$iCount]['values']);
    }

    return $this->getArithmeticMean($aFeatureScores);
}

Анализируем элементы и функции агрегации множеств

Добавив этот процесс, нужно указать признаки, которыми мы будем пользоваться при анализе списка соискателей. Поскольку мы применяем треугольную функцию принадлежности, второй параметр в values и есть наше идеальное значение.

Например, в experience_years у нас следующие значения: 0, 3, 5. Таким образом, для нас предпочтительны люди с 3 годами опыта на фоне тех, у кого нет и года опыта и тех, чей опыт уже составляет 5 лет и более.

$this->aSetFeatures = [
    [
        'identifier' => 'experience_years',
        'values'     => [0, 3, 5]
    ], [
        'identifier' => 'practical_test_score',
        'values'     => [0, 100, 100]
    ], [
        'identifier' => 'team_interview_score',
        'values'     => [0, 5, 5]
    ], [
        'identifier' => 'hr_interview_score',
        'values'     =>  [0, 10, 10]
    ]
];

Массив признаков

Теперь необходимо указать входные значения для каждого соискателя:

$this->aApplicants = [
    [
        'identifier' => 'Applicant A',
        'features' => [
            'experience_years'     => 3,
            'practical_test_score' => 87.30,
            'team_interview_score' => 5,
            'hr_interview_score'   => 9
        ]
    ], [
        'identifier' => 'Applicant B',
        'features' => [
            'experience_years'     => 4,
            'practical_test_score' => 88.25,
            'team_interview_score' => 3,
            'hr_interview_score'   => 8
        ]
    ], [
        'identifier' => 'Applicant C',
        'features' => [
            'experience_years'     => 4,
            'practical_test_score' => 81.67,
            'team_interview_score' => 5,
            'hr_interview_score'   => 7
        ]
    ], [
        'identifier' => 'Applicant D',
        'features' => [
            'experience_years'     => 1,
            'practical_test_score' => 91.90,
            'team_interview_score' => 4,
            'hr_interview_score'   => 7
        ]
    ], [
        'identifier' => 'Applicant E',
        'features' => [
            'experience_years'     => 1,
            'practical_test_score' => 89.58,
            'team_interview_score' => 4,
            'hr_interview_score'   => 8
        ]
    ], [
        'identifier' => 'Applicant F',
        'features' => [
            'experience_years'     => 2,
            'practical_test_score' => 89.49,
            'team_interview_score' => 4,
            'hr_interview_score'   => 7
        ]
    ], [
        'identifier' => 'Applicant G',
        'features' => [
            'experience_years'     => 4,
            'practical_test_score' => 98.94,
            'team_interview_score' => 4,
            'hr_interview_score'   => 8
        ]
    ], [
        'identifier' => 'Applicant H',
        'features' => [
            'experience_years'     => 4,
            'practical_test_score' => 80.80,
            'team_interview_score' => 4,
            'hr_interview_score'   => 8
        ]
    ], [
        'identifier' => 'Applicant I',
        'features' => [
            'experience_years'     => 2,
            'practical_test_score' => 82.97,
            'team_interview_score' => 4,
            'hr_interview_score'   => 8
        ]
    ], [
        'identifier' => 'Applicant J',
        'features' => [
            'experience_years'     => 2,
            'practical_test_score' => 81.91,
            'team_interview_score' => 3,
            'hr_interview_score'   => 7
        ]
    ]
];

Массив соискателей

Наконец, остаётся добавить код, который запускал бы анализатор и выводил результаты на экран.

/**
 * Запустить анализатор и отобразить результаты
 * @return Factory|View
 */
public function index()
{
    $aResults = $this->analyzeItems($this->aSetFeatures, $this->aApplicants);
    return view('index', compact($aResults));
}

Функция индекса

❯ Вывод

Воспользовавшись треугольной функцией принадлежности и агрегацией по среднему арифметическому, можем сказать, что соискатель A наиболее предпочтителен на фоне других, и ему должно быть сделано предложение.

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

Подробнее эта тема разобрана в репозитории на Github. Именно на его основе написана большая часть представленного здесь демо-кода. Также можете познакомиться со ссылками, приведёнными ниже.
Всем мира! ✌

Ссылки:

Теги:

Хабы:

Если эта публикация вас вдохновила и вы хотите поддержать автора — не стесняйтесь нажать на кнопку