13

我们今天在课堂上设置了一个算法问题,作为“如果你想出一个解决方案,你就不必做这门课”。所以当然,我们都认为我们会试一试。

基本上,我们得到了一个包含 100 个单词和 10 个类别的数据库。单词或类别之间不匹配。所以它基本上是一个 100 个单词和 10 个类别的列表。

我们必须将单词“放置”到正确的类别中——也就是说,我们必须“弄清楚”如何将单词放入正确的类别中。因此,我们必须“理解”这个词,然后在算法上把它放在最合适的类别中。

即其中一个词是“钓鱼”类别“运动”-> 所以这将进入这一类别。单词和类别之间存在一些重叠,因此某些单词可能属于多个类别。

如果我们弄清楚了,我们必须增加样本量,并且具有“最佳”匹配百分比的人获胜。

有谁知道如何开始这样的事情?或者任何资源?最好在 C# 中?

即使是关键字数据库或其他东西可能会有所帮助?有谁知道免费的吗?

4

21 回答 21

17

首先你需要对样本文本进行分析,得到单词之间的关系。潜在语义分析的分类在分类的潜在语义分析方法中进行了 描述。

另一种方法是朴素贝叶斯文本分类。需要具有指定类别的示例文本。在学习步骤中,程序会学习不同的类别以及单词在分配给类别的文本中出现的可能性,请参阅贝叶斯垃圾邮件过滤。我不知道这对单个单词有多好。

于 2009-06-04T11:39:55.007 回答
11

真的很差的答案(表明没有“理解”) - 但作为一个疯狂的刺,你可以(通过代码)点击谷歌(例如)“+钓鱼+运动”,“+钓鱼+烹饪”等(即交叉加入每个单词和类别) - 让谷歌战斗获胜!即选择具有最多“命中”的组合...

例如(结果优先):

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;
}
于 2009-06-04T11:26:30.680 回答
8

也许你们都让这太难了。

显然,您需要某种外部参考来对 X 属于 Y 类的概率进行排名。是否有可能他正在测试您的“开箱即用”思维并且您可能是外部参考?也就是说,算法是一个简单的问题,遍历每个类别和每个单词并询问您(或坐在终端的任何人)单词 X 是否在显示的类别 Y 中。这个主题有一些简单的变化,但它们都是涉及通过简单地切割它来吹过Gordian结。

或不...取决于老师。

于 2009-06-04T12:25:29.080 回答
3

所以看起来你在这里有几个选择,但在大多数情况下,我认为如果你想要准确的数据,你将需要使用一些外部帮助。我能想到的两个选择是使用字典搜索或众包。

对于字典搜索,您可以浏览数据库,查询并解析结果以查看页面上是否显示了某个类别名称。例如,如果您搜索“ red ”,您会在页面上找到“color”,同样,搜索“ fishing ”会在页面上返回“sport”。

另一个稍微超出框框的选项是利用众包,请考虑以下几点:

  1. 从或多或少随机分配名称-值对开始。
  2. 输出结果。
  3. 将结果加载到Amazon Mechanical Turk (AMT) 上,以从人类那里获得关于配对工作情况的反馈。
  4. 将 AMT 评估的结果与随机分配一起输入回系统。
  5. 如果一切都通过了,那么我们就完成了。
  6. 否则,保留正确的命中并对其进行处理以查看是否可以建立任何模式,生成一组新的名称-值对。
  7. 返回步骤 3。

当然,这将需要一些财务支出,但它也可能是您将在相当容易的基础上获得的数据的最简单和准确的版本之一。

于 2009-06-04T12:16:54.947 回答
2

您可以使用自定义算法专门处理该数据,例如以“ing”结尾的单词是动词(现在分词)并且可以是运动。

创建一组像上面那样的分类规则,看看你得到的准确度有多高。

编辑:

窃取 wikipedia 数据库(无论如何它是免费的)并获取您的十个类别中的每个类别下的文章列表。计算您的 100 个单词在每个类别下的所有文章中的出现次数,该词的“关键字密度”最高的类别(例如钓鱼)获胜。

于 2009-06-04T11:30:31.763 回答
2

这听起来像您可以使用某种贝叶斯分类,因为它用于垃圾邮件过滤。但这仍然需要某种提供上下文的文本库形式的“外部数据”。

没有它,问题就无法解决。这不是算法问题,而是人工智能问题。但即使是人工智能(以及自然智能,就此而言)也需要某种输入来学习。

我怀疑教授给你一个不可能的问题,让你明白你可以在什么不同的层次上思考一个问题。

这里的关键问题是:谁来决定什么是“正确”的分类?这个决定是基于什么?这个决定如何以编程方式重现,它需要什么输入数据?

于 2009-06-04T11:42:26.560 回答
1

有趣的问题。您正在查看的是单词分类。虽然您可以学习和使用传统的信息检索方法,如 LSA 和基于此类的分类 - 我不确定这是否是您的意图(如果是,那么一定要这样做!:)

既然你说你可以使用外部数据,我建议使用 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 构建相似性度量的资源。当教授说“不要使用谷歌”时,我认为他的意思是编程而不是作为获取信息以进行阅读的手段!)

至于带有 wordnet 的 C# - http://opensource.ebswift.com/WordNet.Net/怎么样

于 2009-06-05T00:15:28.300 回答
1

我假设这个问题允许使用外部数据,否则我无法想出一种方法来从算法上推断出单词的含义。

也许可以用同义词数据库来做一些事情,并寻找“单词”单词和“类别”单词之间的最小距离?

于 2009-06-04T11:26:54.457 回答
1

是的,我会选择 wordnet 方法。查看本教程关于基于 WordNet 的语义相似度测量。您可以在princeton.edu(google it)上在线查询Wordnet,因此为您的问题编写解决方案应该相对容易。希望这可以帮助,

X。

于 2009-06-04T12:19:06.033 回答
1

解雇这位老师。

解决这个问题的唯一方法是已经有了问题的解决方案。IE。您需要一个关键字和类别表来构建将关键字分类的代码。

除非按照您的建议,添加一个“理解”英语的系统。这是坐在电脑前的人,或专家系统。

如果你正在构建一个专家系统并且甚至不知道它,那么老师就不擅长提出问题。

于 2009-06-04T11:49:48.527 回答
1

谷歌是被禁止的,但他们有一个几乎完美的解决方案——谷歌集

因为您需要了解需要外部数据源的单词的语义。您可以尝试使用WordNet。或者您可以尝试使用Wikipedia - 查找每个单词的页面(或者可能仅查找类别)并查找出现在页面或链接页面上的其他单词。

于 2009-06-04T11:52:27.180 回答
0

您也许可以使用 WordNet 数据库,创建一些度量来确定两个单词(单词类别)的联系程度,然后选择将单词放入的最佳类别

于 2009-06-10T09:15:05.253 回答
0

您可以使用蒙特卡罗方法和人工反馈来实现学习算法。让系统随机对单词进行分类,然后要求您将它们投票为“匹配”或“不匹配”。如果匹配,则该词被分类并且可以被消除。如果不是,系统会在未来的迭代中将其排除在该类别之外,因为它知道它不属于该类别。这将得到非常准确的结果。

这将相当容易地解决 100 字的问题。对于更大的问题,您可以将其与有根据的猜测相结合,以使过程更快。在这里,正如上面许多人所提到的,您将需要外部资源。google 方法可能效果最好,因为 google 已经在这方面做了很多工作,但是除非您可以使用 facebook api 从您的 facebook 帐户中提取数据并尝试找出哪些词在统计上更有可能与以前分类的单词一起出现。

但是,无论哪种方式,如果没有某种外部输入(在某些时候来自人类),就无法做到这一点。除非您想厚脸皮,例如,通过名称的 ascii 文本中包含的一些序列化值来定义类别:P

于 2013-04-19T21:37:08.637 回答
0

我的第一个想法是利用外部数据。编写一个程序,用谷歌搜索每个单词,并采用在搜索结果中出现的第一个/最高的“类别”:)

不过,这可能被认为是作弊。

于 2009-06-04T11:27:39.010 回答
0

因为当你解决这个“谜题”时你不需要参加这个主题,所以我认为这并不容易。尽管如此,我还是会做这样的事情(以非常简单的方式讲述)

建立一个神经网络,你可以给它一些输入(一本(电子)书,一些(电子)书)=>不需要谷歌

该网络对单词进行分类(神经网络非常适合“不确定”分类)。我想你可能只是因为文本中的出现而知道哪个单词属于哪个类别。(“钓鱼”可能会在“运动”附近提及)。在对神经网络进行一些训练之后,它应该将您的单词“链接”到类别。

于 2009-06-04T14:55:17.077 回答
0

爬取delicious.com 并搜索每个单词,查看集体标签计数等。

关于这一点我能说的不多,但美味是古老的、巨大的、令人难以置信的重标签,并且包含大量当前相关的语义信息可供借鉴。以这种方式构建语义数据库将非常容易,使用您的单词列表作为抓取的基础。

知识在标签中。

于 2009-06-04T13:36:19.733 回答
0

使用现有的分类大型数据集(例如RCV1)来训练您选择的系统。你可以做得更糟然后开始阅读现有的研究和基准

来自 Google 的 Appart 还存在您可以构建的其他“百科全书”数据集,其中一些作为公共数据集托管在Amazon Web Services上,例如英语维基百科的完整快照。

要有创意。除了谷歌,还有其他数据。

于 2009-06-04T11:56:37.080 回答
0

好吧,你不能使用谷歌,但你可以使用雅虎、Ask、Bing、Ding、Dong、Kong……我会做几遍。首先针对 2-3 个搜索引擎查询 100 个单词,获取前 y 个结果文章(y 是实验的阈值。我认为 5 是一个好的开始)并扫描文本。特别是,我将搜索 10 个类别。如果一个类别出现超过 x 次(x 再次是您需要试验的某个阈值),则它是匹配的。基于该 x 阈值(即一个类别出现在文本)以及它出现在前 y 页面中的可能性如何分配给单词类别对的权重。为了获得更高的准确性,您可以使用单词类别对(带有AND 关系)并将结果页数应用于该对的权重。他们只是假设权重最高的词-类别对是正确的(假设您甚至有多个选项)。如果权重足够接近(可能是 z 阈值),您还可以将一个单词多重分配给多个类别。基于此,您可以引入任意数量的单词和任意数量的类别。你会赢得你的挑战。我也认为这种方法可以很好地评估潜在广告词在广告中的权重。但这是另一个话题...... 我也认为这种方法可以很好地评估潜在广告词在广告中的权重。但这是另一个话题...... 我也认为这种方法可以很好地评估潜在广告词在广告中的权重。但这是另一个话题......

祝你好运

哈雷尔

于 2009-06-04T12:02:39.157 回答
0

使用(在线或下载)WordNet,找出你必须遵循的单词和每个类别之间的关系数量。

于 2009-06-04T12:06:33.050 回答
0

我天真的方法:

  1. 像这样创建一个巨大的文本文件(阅读文章以获得灵感
  2. 对于每个单词,扫描文本,每当您匹配该单词时,计算出现在其左右 N(最大,又名无线电)位置的“类别”。
  3. 这个词很可能属于计数器最大的类别。
于 2009-06-04T12:07:07.073 回答
0

我的尝试是使用CRM114的工具集来提供一种分析大型文本语料库的方法。然后,您可以利用其中的匹配项进行猜测。

于 2009-06-04T12:09:03.137 回答