Категоризация слов и значений категорий

Question

Сегодня в классе нам поставили задачу алгоритма, как «если вы найдете решение, вам не нужно заниматься этим предметом». ТАК конечно, мы все думали, что попробуем.

В основном нам была предоставлена ​​БД из 100 слов и 10 категорий. Нет совпадения между словами или категориями. Так что это в основном список из 100 слов и 10 категорий.

Мы должны «поместить» слова в правильную категорию, то есть мы должны «выяснить», как поместить слова в правильную категорию. Таким образом, мы должны «понять» слово, а затем поместить его в наиболее подходящую категорию.

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

Если мы выясним это, мы должны увеличить размер выборки, и победит человек с «лучшим» соответствием%.

У кого-нибудь есть идеи, как начать что-то подобное? Или какие-нибудь ресурсы? Желательно в C #?

Даже ключевое слово DB или что-то может быть полезным? Кто-нибудь знает какие-нибудь бесплатные?

Answer 1

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

Другим подходом была бы наивная байесовская классификация текста. Образец текста с назначенной категорией не требуется. На этапе обучения программа изучает различные категории и вероятность того, что слово встречается в тексте, назначенном категории, см. фильтрация спама Байеса . Я не знаю, насколько хорошо это работает с отдельными словами.

Answer 2

Действительно плохой ответ (демонстрирует отсутствие «понимания») - но в качестве сумасшедшего удара вы можете нажать Google (через код) для (например) «+ Fishing + Sport», «+ Fishing + Cooking» и т. Д. каждое слово и категория) - и пусть бой Google победит! то есть выбирается комбинация с большинством "хитов" ...

Например (сначала результаты):

weather: fish
sport: ball
weather: hat
fashion: trousers
weather: snowball
weather: tornado

С кодом (TODO: добавить многопоточность ;-p):

static void Main() {
    string[] words = { "fish", "ball", "hat", "trousers", "snowball","tornado" };
    string[] categories = { "sport", "fashion", "weather" };

    using(WebClient client = new WebClient()){
        foreach(string word in words) {
            var bestCategory = categories.OrderByDescending(
                cat => Rank(client, word, cat)).First();
            Console.WriteLine("{0}: {1}", bestCategory, word);
        }
    }
}

static int Rank(WebClient client, string word, string category) {
    string s = client.DownloadString("http://www.google.com/search?q=%2B" +
        Uri.EscapeDataString(word) + "+%2B" +
        Uri.EscapeDataString(category));
    var match = Regex.Match(s, @"of about \<b\>([0-9,]+)\</b\>");
    int rank = match.Success ? int.Parse(match.Groups[1].Value, NumberStyles.Any) : 0;
    Debug.WriteLine(string.Format("\t{0} / {1} : {2}", word, category, rank));
    return rank;
}

Answer 3

Может быть, вы все делаете это слишком сложно.

Очевидно, что вам нужна какая-то внешняя ссылка для ранжирования вероятности того, что X находится в категории Y. Возможно ли, что он проверяет ваше мышление "из коробки" и что вы можете быть внешней ссылкой? То есть алгоритм - это простой процесс прохождения каждой категории и каждого слова и вопрос ВАС (или тому, кто сидит за терминалом), находится ли слово X в отображаемой категории Y. Есть несколько простых вариантов этой темы, но все они вовлеките удар в гордиев узел, просто порезав его.

Или нет ... зависит от учителя.

Answer 4

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

Что касается поиска по словарю, вы можете просто просмотреть базу данных, запросить ее и проанализировать результаты, чтобы увидеть, отображается ли одно из названий категорий на странице. Например, если вы ищете « red », вы найдете «color» на странице и, аналогично, поиск « fishing » возвращает «sport» на странице.

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

1. Начните с более или менее случайного назначения пар имя-значение.
2. Вывод результатов.
3. Загрузите результаты на Amazon Mechanical Turk (AMT), чтобы узнать мнение людей о том, насколько хорошо работают пары.
4. Ввести результаты оценки AMT обратно в систему вместе со случайными назначениями.
5. Если все было одобрено, то мы закончили.
6. В противном случае сохраните правильные совпадения и обработайте их, чтобы увидеть, можно ли установить какой-либо шаблон, сгенерируйте новый набор пар имя-значение.
7. Вернуться к шагу 3.

Конечно, это повлечет за собой некоторые финансовые затраты, но это также может быть одна из самых простых и точных версий данных, которые вы собираетесь получить на довольно простой основе.

Answer 5

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

Без этого проблему невозможно решить. Это не проблема алгоритма, это проблема ИИ. Но даже ИИ (и в данном случае природный интеллект) нуждается в некотором вкладе, чтобы извлечь уроки.

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

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

Answer 6

Вы можете создать собственный алгоритм для работы именно с этими данными, например, слова, оканчивающиеся на 'ing', являются глаголами (настоящее причастие) и могут быть спортивными.

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

EDIT:

Украдите базу данных Википедии (она в любом случае бесплатна) и получите список статей по каждой из десяти категорий. Подсчитайте вхождения каждого из ваших 100 слов во всех статьях в каждой категории, и выиграет категория с самой высокой «плотностью ключевых слов» этого слова (например, вылов).

Answer 7

Google запрещен, но у них есть почти идеальное решение - Google Sets .

Поскольку вам нужно понимать семантику слов, вам нужны внешние источники данных. Вы можете попробовать использовать WordNet . Или вы можете попробовать Wikipedia - найти страницу для каждого слова (или, может быть, только для категорий) и найти другие слова, появляющиеся на странице или связанных страницах.

Answer 8

Уволить этого учителя.

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

Если, как вы предлагаете, вы не добавите систему, которая "понимает" английский. Это человек, сидящий перед компьютером или экспертной системой.

Если вы строите экспертную систему и даже не знаете об этом, учитель не умеет давать проблемы.

Answer 9

Интересная проблема. То, что вы смотрите, это классификация слов. Хотя вы можете изучать и использовать традиционные методы поиска информации, такие как АЛП и категоризация, основанные на них, я не уверен, что это ваше намерение (если оно есть, тогда сделайте это всеми средствами!:)

Поскольку вы говорите, что можете использовать внешние данные, я бы предложил использовать wordnet и его связь между словами. Например, используя wordnet,

# S: (n) **fishing**, sportfishing (the act of someone who fishes as a diversion)
* direct hypernym / inherited hypernym / sister term
      o S: (n) **outdoor sport, field sport** (a sport that is played outdoors)
      + direct hypernym / inherited hypernym / sister term
            # S: (n) **sport**, athletics 
            (an active diversion requiring physical exertion and competition) 

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

Теперь, если вы получите дрейф - можно использовать это соотношение для вычисления вероятности классификации «рыбалка» на «спорт», скажем, на основе линейного расстояния цепочки слов или числа вхождений, и другие. (должно быть тривиально найти ресурсы о том, как построить меры подобия, используя wordnet. Когда проф говорит «не использовать Google», я предполагаю, что он имеет в виду программно, а не как средство для получения информации для чтения!)

Что касается C # с Wordnet - как насчет http://opensource.ebswift.com/WordNet.Net/

Answer 10

Да, я бы пошел на подход к Wordnet. Проверьте это руководство на Измерение семантического сходства на основе WordNet . Вы можете запросить Wordnet онлайн по адресу princeton.edu (Google google), так что должно быть относительно легко написать решение вашей проблемы. Надеюсь, это поможет,

X.