Мне очень захотелось сделать спам-фильтр, но с чего начать я не знал. Чисто случайно наткнулся я на книгу «Программируем коллективный разум». В частности в «Главе 6» написана как раз про данные алгоритмы. Вот их я и решил попробовать реализовать. А чтобы было интереснее, а не простое перенабивание кода, я решил сделать простой сервис классификации сообщений.

Реализация

В книге написано как реализовать 2 алгоритма: Наивный метод (Байесовский) и метод Фишера. Что это за алгоритмы и как они работают прекрасно все расписано. Так же в ней написана реализация на Python, но… Мне захотелось попробовать сделать на другом языке программирования и выбрал я Golang.

Сам алгоритм и классы практически переписываются один в один (строчка в строку). Тут ничего сверхординарного нет. Все работает.

type Classifier struct {
	Words       map[string]*Word   `json:"words"`
	Cats        map[string]int     `json:"cats"`
	Thresholds  map[string]float32 `json:"thresholds"`
	Minimums    map[string]float32 `json:"minimums"`
	getFeatures func(str string) (result []string, err error)
}

func NewClassifier(f func(str string) (result []string, err error)) *Classifier {
	classifier := Classifier{}
	classifier.initclassifier(f)
	return &classifier
}

func (classifier *Classifier) initclassifier(f func(str string) (result []string, err error)) {
	classifier.getFeatures = f
	classifier.Cats = make(map[string]int)
	classifier.Words = make(map[string]*Word)
	classifier.Thresholds = make(map[string]float32)
	classifier.Minimums = make(map[string]float32)
}

func (classifier *Classifier) SetThreshold(cat string, t float32) {
	classifier.Thresholds[cat] = t
}

func (classifier *Classifier) GetThreshold(cat string) float32 {
	if _, ok := classifier.Thresholds[cat]; !ok {
		return 1.0
	}
	return classifier.Thresholds[cat]
}

// Тренировка
func (classifier *Classifier) Train(str string, cat string) {

	if len(cat) > 0 {

		words, err := classifier.getFeatures(str)
		if err != nil {
			log.Println(err)
			return
		}

		if len(words) > 0 {
			for _, word := range words {
				classifier.incf(word, cat)
			}
			classifier.incc(cat)
		}

	}

}

// Сколько образцов отнесено к данной категории
func (classifier *Classifier) catcount(cat string) int {
	if _, ok := classifier.Cats[cat]; !ok {
		return 0
	}
	return classifier.Cats[cat]
}

// Общее число образцов
/*func (classifier *Classifier) totalcount() int {
	sum := 0
	if len(classifier.Cats) > 0 {
		for _, val := range classifier.Cats {
			sum += val
		}
	}
	return sum
}*/

// Список всех категорий
func (classifier *Classifier) Categories() []string {
	res := make([]string, 0, len(classifier.Cats))
	for k := range classifier.Cats {
		res = append(res, k)
	}
	return res
}

// Увеличить счетчик применений категории
func (classifier *Classifier) incc(cat string) {
	if _, ok := classifier.Cats[cat]; ok {
		classifier.Cats[cat]++
	} else {
		classifier.Cats[cat] = 1
	}
}

// Увеличить счетчик пар признак/категория
func (classifier *Classifier) incf(word string, cat string) {
	if _, ok := classifier.Words[word]; !ok {
		classifier.Words[word] = &Word{}
	}
	classifier.Words[word].IncCat(cat)
}

// Сколько раз признак появлялся в данной категории
func (classifier *Classifier) fcount(word string, cat string) int {
	if _, ok := classifier.Words[word]; ok {
		if _, ok := classifier.Words[word].Categories[cat]; ok {
			return classifier.Words[word].Categories[cat]
		}
	}
	return 0
}

// Условная вероятность
func (classifier *Classifier) fprob(word string, cat string) float32 {
	//if len(docclass.cats) == 0 {
	if classifier.catcount(cat) == 0 {
		return 0.0

	}
	tmp := float32(classifier.fcount(word, cat)) / float32(classifier.catcount(cat))
	return tmp
}

func (classifier *Classifier) Sampletrain() {
	classifier.Train("Клара у Карла украла караллы.", "good")
	classifier.Train("Шла Саша по шоссе и сосала сушку.", "good")
	classifier.Train("Я вычислю тебя по IP!", "bad")
	classifier.Train("Вычислю тебя", "bad")
}

type WeighteProbeStruct struct {
	Word   string
	Cat    string
	Prf    func(word string, cat string) float32
	Weight float32
	Ap     float32
}

// Взвешенная вероятность
func (classifier *Classifier) weighteprobe(weighteProbeArgs WeighteProbeStruct) float32 {
	if weighteProbeArgs.Weight == 0.0 {
		weighteProbeArgs.Weight = 1.0
	}
	if weighteProbeArgs.Ap == 0 {
		weighteProbeArgs.Ap = 0.5
	}

	basicprob := weighteProbeArgs.Prf(weighteProbeArgs.Word, weighteProbeArgs.Cat)

	totals := 0

	for _, categ := range classifier.Categories() {
		totals += classifier.fcount(weighteProbeArgs.Word, categ)
	}

	bp := ((weighteProbeArgs.Weight * weighteProbeArgs.Ap) + (float32(totals) * basicprob)) / (weighteProbeArgs.Weight + float32(totals))
	return bp
}

func (classifier *Classifier) SetMininun(cat string, val float32) {
	classifier.Minimums[cat] = val
}

func (classifier *Classifier) GetMininun(cat string) float32 {
	val, ok := classifier.Minimums[cat]
	if ok {
		return val
	}

	return 0.0
}

func (classifier *Classifier) Save() (res string, err error) {
	var bytes []byte
	bytes, err = json.Marshal(classifier)
	if err != nil {
		return
	}
	res = string(bytes)
	return
}

func (classifier *Classifier) Load(data string) (err error) {
	err = json.Unmarshal([]byte(data), classifier)
	if err != nil {
		return
	}
	return
}

// Вероятность того, что образец с указанным признаком принадлежит указанной категории, в предположении, что в каждой категории будет одинаковое число образцов
func (fisher *Classifier) cprob(word string, cat string) float32 {
	clf := fisher.fprob(word, cat)
	if clf == 0 {
		return 0.0
	}
	var freqsum float32
	for _, c := range fisher.Categories() {
		freqsum += fisher.fprob(word, c)
	}
	return clf / freqsum
}

func (fisher *Classifier) fisherprobe(str string, cat string) float32 {
	p := float32(1.0)
	words, err := fisher.getFeatures(str)
	if err != nil {
		log.Println(err)
		return 0.0
	}
	for _, word := range words {
		p *= fisher.weighteprobe(WeighteProbeStruct{
			Word: word,
			Cat:  cat,
			Prf:  fisher.cprob,
		})
	}
	fscore := float32(-2.0 * math.Log(float64(p)))
	return fisher.invchi2(fscore, len(words)*2)
}

func (fisher *Classifier) invchi2(chi float32, df int) float32 {
	m := chi / 2.0
	sum := float32(math.Exp(float64(-1.0 * m)))
	term := sum
	for i := 1; i <= int(df/2); i++ {
		term *= m / float32(i)
		sum += term
	}
	if sum < 1.0 {
		return sum
	}
	return 1.0
}

func (fisher *Classifier) FisherClassify(str string, def string) string {
	best := def
	var max float32
	for _, cat := range fisher.Categories() {
		p := fisher.fisherprobe(str, cat)
		if p > fisher.GetMininun(cat) && p > max {
			best = cat
			max = p
		}
	}
	return best
}

func (naivebayes *Classifier) docprobe(str string, cat string) float32 {
	p := float32(1.0)
	words, err := naivebayes.getFeatures(str)
	if err != nil {
		log.Println(err)
		return 0
	}
	for _, word := range words {
		p *= naivebayes.weighteprobe(WeighteProbeStruct{
			Word: word,
			Cat:  cat,
			Prf:  naivebayes.fprob,
		})
	}
	return p
}

func (naivebayes *Classifier) Probe(str string, cat string) float32 {
	catprob := naivebayes.catcount(cat)
	docprobe := naivebayes.docprobe(str, cat)
	return docprobe * float32(catprob)
}

func (naivebayes *Classifier) Classify(str string, def string) string {
	probs := make(map[string]float32)
	max := float32(0.0)
	var best string
	for _, cat := range naivebayes.Categories() {
		probs[cat] = naivebayes.Probe(str, cat)
		if probs[cat] > max {
			max = probs[cat]
			best = cat
		}
	}

	for cat := range probs {
		if cat == best {
			continue
		}
		if probs[cat]*naivebayes.GetThreshold(best) > probs[best] {
			return def
		}
	}
	return best
}

Так же у нас есть структура для групп слов:

type Word struct {
	Categories map[string]int `json:"categories"`
}

func (word *Word) IncCat(cat string) {
	if word.Categories == nil {
		word.Categories = make(map[string]int)
	}
	(*word).Categories[cat]++
}

В книге написано как подготовить входящее сообщение для дальнейшей работы. Алгоритм достаточно прост: разделяем текст на слова с удалением всех знаков препинания и пробелов, составляем массив слов и убираем дублирующие слова, затем прогоняем через цикл и убираем все слова, которые меньше либо равно 2ум символам и больше либо равно 20 символам. Все просто. Но мне не хватило чего-то…

Немного покопавшись в своем сознании я вспомнил, что в Python есть пакет NLTK, который отвечает за обработку естественного языка. В частности в нем есть стеммер. В кратце это такая штука, которая ищет основу слова для заданного слова. К примеру «Саша» может быть записано «Саше», «Сашей», «Сашка», «Сашочек» и т.д. В общем вариантов масса. Так вот вероятность того что одно и тоже слово будет повторять начинает постепенно снижаться. Чтобы обучить нашу модель нуже достаточно большой корпус обучения. Для снижения такого объема и для улучшения качества работы модели можно попробовать применить стеммер.

Библиотека называется SnowBall и написана она на С. Есть и для Go, но хотелось еще что-то. В общем нашел я другую библиотеку и мне она подошла. По факту она так же использует Snowball, только выполнено в виде пакета.

Теперь давайте приведем разбиение текста на слова:

/// Подготовка текста и разбивка на слова
func GetWords(str string, lang string) (result []string, err error) {
	// Подготовим полученный текст
	var stemmer *snowball.Stemmer
	stemmer, err = snowball.New(lang)
	if err != nil {
		return
	}
	var reSplitWords *regexp.Regexp
	switch lang {
	case "ru":
		reSplitWords = regexp.MustCompile(`[^А-Яа-я]+`)
	case "en":
		reSplitWords = regexp.MustCompile(`[^A-Za-z]+`)
	}
	split := reSplitWords.Split(strings.ToLower(str), -1)
	splitted := make(map[string]*string)

	for _, word := range split {
		word = stemmer.Stem(word)
		if len([]rune(word)) > 2 && len([]rune(word)) < 20 {
			if _, ok := splitted[word]; !ok {
				// Нет слова в списке. Добавим
				splitted[word] = nil //&structs.Word{}
			}
		}
	}
	result = make([]string, 0, len(splitted))
	for k := range splitted {
		result = append(result, k)
	}
	return
}

Использование:

сlassifier := structs.NewClassifier(func(str string) (result []string, err error) {
	return GetWords(str, Config.Lang)
})

Тренировка

Наша задача вызвать функцию Train и передать ей 2 параметра: сообщение и группа, к которой относится сообщение. Вот функция:

// Тренировка данных
func train(classifier *structs.Classifier) {
	// TODO
	f, err := os.Open(libs.Config.TraintSetPath)
	if err != nil {
		panic(err)
	}
	defer f.Close()

	csvReader := csv.NewReader(f)

	for {
		row, err := csvReader.Read()
		if err != nil {
			if err == io.EOF {
				err = nil
			}
			return
		}
		classifier.Train(row[0], row[1])
	}
}

Сохранение и загрузка

Сохранять и загружать подготовленные данные можно по разному. Так можно использовать СУБД, а можно напрямую в файлы. Я решил сохранять в файл в формат JSON. Собственно сохранение:

fo, err := os.Create(fmt.Sprintf("./database/%s.json", libs.Config.Lang))
		if err != nil {
			panic(err)
		}
		defer func() {
			if err := fo.Close(); err != nil {
				panic(err)
			}
		}()

		var j string
		j, err = libs.Config.Classifier.Save()
		if err != nil {
			panic(err)
		}
		fo.WriteString(j)

Загрузка:

if _, err := os.Stat(fmt.Sprintf("./database/%s.json", Config.Lang)); !errors.Is(err, os.ErrNotExist) {
		fi, err := os.Open(fmt.Sprintf("./database/%s.json", Config.Lang))
		if err != nil {
			log.Fatal(err)
		}
		defer func() {
			if err = fi.Close(); err != nil {
				log.Fatal(err)
			}
		}()

		b, err := ioutil.ReadAll(fi)
		if err != nil {
			panic(err)
		}
		err = Config.Classifier.Load(string(b))
		if err != nil {
			panic(err)
		}
	}

Сервис

Для работы с программой как с сервисом сделаем для него HTTP-сервер и привяжем функции. Я буду использовать пакет Echo. Подготавливаем:

e := echo.New()
e.Use(middleware.BodyLimit("1M"))
e.Use(middleware.Logger())
e.Use(middleware.Recover())
e.POST("/api/v1/naivebayes", naivebayes)
e.POST("/api/v1/fisher", fisher)

func naivebayes(c echo.Context) error {
	var err error
	var text struct {
		Text string `json:"text"`
	}
	err = json.NewDecoder(c.Request().Body).Decode(&text)
	if err != nil {
		return c.JSON(http.StatusInternalServerError, structs.Result{
			Result:  false,
			Code:    http.StatusInternalServerError,
			Message: libs.PointerString("Не удалось прочитать запрос"),
		})
	}

	return c.JSON(http.StatusOK, structs.Result{
		Result: true,
		Code:   http.StatusOK,
		Data:   libs.PointerString(libs.Config.Classifier.Classify(text.Text, "unknow")),
	})
}

func fisher(c echo.Context) error {
	var err error
	var text struct {
		Text string `json:"text"`
	}
	err = json.NewDecoder(c.Request().Body).Decode(&text)
	if err != nil {
		return c.JSON(http.StatusInternalServerError, structs.Result{
			Result:  false,
			Code:    http.StatusInternalServerError,
			Message: libs.PointerString("Не удалось прочитать запрос"),
		})
	}

	return c.JSON(http.StatusOK, structs.Result{
		Result: true,
		Code:   http.StatusOK,
		Data:   libs.PointerString(libs.Config.Classifier.FisherClassify(text.Text, "unknow")),
	})
}

И моя функция конфигурации:

type Result struct {
	Result  bool    `json:"result"`
	Code    int     `json:"code"`
	Message *string `json:"message"`
	Data    *string `json:"data"`
}

type Config struct {
	IsTrain       bool
	TraintSetPath string

	Lang string

	IsNaivebayes bool
	IsFisher     bool

	Port int

	Classifier *Classifier
}

func LoadConfig() {
	var exists bool
	Config.Lang = "ru"

	var tmp string

	if tmp, exists = os.LookupEnv("PORT"); exists {
		var err error
		Config.Port, err = strconv.Atoi(tmp)
		if err != nil {
			panic(err)
		}
	} else {
		Config.Port = 3000
	}

	prepareArguments(os.Args[1:])

	Config.Classifier = structs.NewClassifier(func(str string) (result []string, err error) {
		return GetWords(str, Config.Lang)
	})

	if _, err := os.Stat(fmt.Sprintf("./database/%s.json", Config.Lang)); !errors.Is(err, os.ErrNotExist) {
		fi, err := os.Open(fmt.Sprintf("./database/%s.json", Config.Lang))
		if err != nil {
			log.Fatal(err)
		}
		defer func() {
			if err = fi.Close(); err != nil {
				log.Fatal(err)
			}
		}()

		b, err := ioutil.ReadAll(fi)
		if err != nil {
			panic(err)
		}
		err = Config.Classifier.Load(string(b))
		if err != nil {
			panic(err)
		}
	}
}

func prepareArguments(args []string) {
	if len(args) > 0 {
		switch args[0] {
		case "train":
			Config.IsTrain = true
			Config.TraintSetPath = args[1]
			prepareArguments(args[2:])
		case "lang":
			Config.Lang = args[1]
			prepareArguments(args[2:])
		case "--naivebayes":
			Config.IsNaivebayes = true
			prepareArguments(args[1:])
		case "--fisher":
			Config.IsFisher = true
			prepareArguments(args[1:])
		}
	}
}

Собственно все.

Где можно применить

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