Используйте MapReduce для ранжирования Tf-Idf в среде Node.js и MongoDB
При разработке приложения для поиска документов одной из задач является упорядочение результатов в соответствии с появлением искомого термина. Tf-Idf — это числовая статистика, которая помогает вам взвешивать результаты поиска.
Tf обозначает частоту членов.
Idf обозначает частоту обратных документов.
Чтобы получить представление, мы разработаем образец tf-idf в javascript, как модуль узла.
function TfIdf() {
}
TfIdf.prototype.weights = function(documents,term) {
var results = []
var idf = this.idf(documents,term)
for(var i=0;i<documents.length;i++) {
var tf = this.tf(documents[i],term)
var tfidf = tf*idf
var result = {weight:tfidf,doc:documents[i]}
results.push(result)
}
return results
}
TfIdf.prototype.tf = function(words,term) {
var result = 0
for(var i=0;i<words.length;i++) {
var word = words[i]
if(word.indexOf(term)!=-1) {
result = result+1
}
}
return result/words.length
}
TfIdf.prototype.idf = function(documents,term) {
var occurence = 0
for(var j=0;j<documents.length;j++) {
var doc = documents[j]
if(this.__wordInsideDoc(doc,term)){
occurence = occurence+1
}
}
if(occurence==0) {
return undefined
}
return Math.log(documents.length/occurence)
}
TfIdf.prototype.__wordInsideDoc = function(doc,term) {
for(var i=0;i<doc.length;i++) {
var word = doc[i]
if(word.indexOf(term)!=-1) {
return true
}
}
return false
}
module.exports = TfIdfФункция весов примет документы и термин для поиска.
Пример следует
var TfIdf = require('./TfIdf')
var tfIdf = new TfIdf()
var docs = [["latest","sprint"],["lair","laugh","fault"],["lemma","on"]]
console.log(tfIdf.weights(docs,"la"))Результат:
[ { weight: 0.2027325540540822, doc: [ 'latest', 'sprint' ] },
{ weight: 0.27031007207210955,
doc: [ 'lair', 'laugh', 'fault' ] },
{ weight: 0, doc: [ 'lemma', 'on' ] } ]Теперь мы продолжим с подходом MapReduce.
Я буду использовать node.js.
Сначала мы установим драйвер MongoDB:
npm install mongodbЗатем мы настроим соединение с базой данных Mongo. После инициализации, в случае отсутствия записей, мы заполним базу данных для целей тестирования.
Это будет двухфазный процесс.
На первом этапе мы должны рассчитать IDF.
Для этого мы выпустим MapReduce.
Термин переменная должен быть передан для использования процессом MapReduce.
Чтобы использовать динамическую переменную в MapReduce, мы будем использовать параметр scope.
TfIdfMongo.prototype.__idf = function(connection,term,callback) {
var tfIdfMongo = this
var documents = connection.collection('documents');
documents.mapReduce(
tfIdfMongo.__mapIdf,
tfIdfMongo.__reduceIdf,
{
scope: {permterm:term},
out: "tfidf_results"
},
function(err,results) {
if(err) {
callback(err)
}
results.findOne({},function(err,result) {
if(err) {
callback(err)
}
if(result.value.occurrence==0) {
return;
}
var idf = Math.log(result.value.count/result.value.occurrence)
callback(undefined,idf)
})
}
)
}
TfIdfMongo.prototype.__mapIdf = function() {
var term = permterm
var occurrence = 0
for (var i = 0; i < this.words.length; i++) {
var word = this.words[i]
if (word.indexOf(term) != -1) {
if (occurrence <=0 ) {
occurrence = 1
}
}
}
emit("idf", occurrence)
}
TfIdfMongo.prototype.__reduceIdf = function(key,values) {
var result = {count:values.length,occurrence:0}
for(var i=0;i<values.length;i++) {
if(values[i]==1) {
result.occurrence += 1
}
}
return result
}Результатом является одно число.
На втором этапе мы должны рассчитать tf для каждого документа и умножить результат на значение idf, рассчитанное до этого.
MapReduce будет использоваться и для этого случая.
На этот раз через параметр scope мы пропустим искомый термин, а также переменную idf.
TfIdfMongo.prototype.__tf = function(connection,term,idf,callback) {
var tfIdfMongo = this
var documents = connection.collection('documents');
documents.mapReduce(
tfIdfMongo.__mapTf,
function(key,values) {
return values
},
{
scope: {permTerm:term,permIdf:idf},
out: "tf_results"
},
function(err,results) {
if(err) {
callback(err)
}
results.find({},function(err,docs) {
if(err) {
callback(err)
}
docs.toArray(function (err,documents) {
callback(err,documents)
})
})
}
)
}
TfIdfMongo.prototype.__mapTf = function() {
var term = permTerm
var idf = permIdf
var occurrence = 0
for(var i=0;i<this.words.length;i++) {
var word = this.words[i]
if (word.indexOf(term) != -1) {
occurrence += 1
}
}
var weight = idf*(occurrence/this.words.length)
emit(this, weight)
}Мы реализуем функцию tfIdf, которая объединяет два предыдущих шага.
Функция принимает термин, который нам нужно найти в качестве аргумента.
var MongoClient = require('mongodb').MongoClient
Server = require('mongodb').Server
var url = 'mongodb://localhost:27017/mapreduceexample'
function TfIdfMongo() {
}
TfIdfMongo.prototype.tfIdf = function(term,callback) {
var tfIdfMongo = this
tfIdfMongo.__getConnection(function(err,connection) {
if(err) {
callback(err)
}
tfIdfMongo.__idf(connection,term,function(err,idf) {
if(err) {
callback(err)
}
tfIdfMongo.__tf(connection,term,idf,function(err,documents) {
if(err) {
callback(err)
}
connection.close()
callback(undefined,documents)
})
})
})
}
TfIdfMongo.prototype.__getConnection = function(callback) {
var tfIdfMongo = this
MongoClient.connect(url,function (err, connection) {
if (err) {
callback(err)
} else {
var documents = connection.collection('documents');
documents.count({}, function (error, numOfDocs) {
if (numOfDocs == 0) {
tfIdfMongo.__insertTestRecords(connection,function(err) {
callback(err,connection)
})
} else {
callback(undefined,connection)
}
})
}
})
}
TfIdfMongo.prototype.__insertTestRecords = function(connection,callback) {
var documents = connection.collection('documents');
var latestDocuments = [
{words:["latest","sprint"]},
{words:["lair","laugh","fault"]},
{words:["lemma","on"]}
]
documents.insert(latestDocuments,
function(err,result) {
callback(err)
})
}
TfIdfMongo.prototype.__tf = function(connection,term,idf,callback) {
var tfIdfMongo = this
var documents = connection.collection('documents');
documents.mapReduce(
tfIdfMongo.__mapTf,
function(key,values) {
return values
},
{
scope: {permTerm:term,permIdf:idf},
out: "tf_results"
},
function(err,results) {
if(err) {
callback(err)
}
results.find({},function(err,docs) {
if(err) {
callback(err)
}
docs.toArray(function (err,documents) {
callback(err,documents)
})
})
}
)
}
TfIdfMongo.prototype.__mapTf = function() {
var term = permTerm
var idf = permIdf
var occurrence = 0
for(var i=0;i<this.words.length;i++) {
var word = this.words[i]
if (word.indexOf(term) != -1) {
occurrence += 1
}
}
var weight = idf*(occurrence/this.words.length)
emit(this, weight)
}
TfIdfMongo.prototype.__idf = function(connection,term,callback) {
var tfIdfMongo = this
var documents = connection.collection('documents');
documents.mapReduce(
tfIdfMongo.__mapIdf,
tfIdfMongo.__reduceIdf,
{
scope: {permterm:term},
out: "tfidf_results"
},
function(err,results) {
if(err) {
callback(err)
}
results.findOne({},function(err,result) {
if(err) {
callback(err)
}
if(result.value.occurrence==0) {
return;
}
var idf = Math.log(result.value.count/result.value.occurrence)
callback(undefined,idf)
})
}
)
}
TfIdfMongo.prototype.__mapIdf = function() {
var term = permterm
var occurrence = 0
for (var i = 0; i < this.words.length; i++) {
var word = this.words[i]
if (word.indexOf(term) != -1) {
if (occurrence <=0 ) {
occurrence = 1
}
}
}
emit(this.__id, occurrence)
}
TfIdfMongo.prototype.__reduceIdf = function(key,values) {
var result = {count:values.length,occurrence:0}
for(var i=0;i<values.length;i++) {
if(values[i]==1) {
result.occurrence += 1
}
}
return result
}
module.exports = TfIdfMongoНаш тестовый кейс:
var TfIdf = require('./TfIdf')
var TfIdfMongo = require('./TfIdfMongo')
var tfIdf = new TfIdf()
var docs = [["latest","sprint"],["lair","laugh","fault"],["lemma","on"]]
console.log("The results are "+JSON.stringify(tfIdf.tfIdf(docs,"la")))
var tfIdfMongo = new TfIdfMongo()
tfIdfMongo.tfIdf("la",function(err,results) {
console.log("The results are "+JSON.stringify(results))
})И мы получаем одинаковые результаты для обоих случаев.
The results are [{"weight":0.2027325540540822,"doc":["latest","sprint"]},{"weight":0.27031007207210955,"doc":["lair","laugh","fault"]},{"weight":0,"doc":["lemma","on"]}]
The results are [{"_id":{"_id":"55f46602947446bb1a7f7933","words":["latest","sprint"]},"value":0.2027325540540822},{"_id":{"_id":"55f46602947446bb1a7f7934","words":["lair","laugh","fault"]},"value":0.27031007207210955},{"_id":{"_id":"55f46602947446bb1a7f7935","words":["lemma","on"]},"value":0}]Почему я должен использовать MapReduce для этой проблемы?
Проблема ранжирования tf-idf — это проблема, которая включает в себя вычисления, которые можно распараллелить.
Последовательный подход может быть вариантом для других сред, но для Node.js есть много недостатков.
Node.js — это однопоточная среда, она не была разработана для сложных вычислительных задач.
Его магия связана с тем, насколько хорошо он выполняет операции ввода-вывода.
Рассмотрим сценарий большой проблемы с набором данных.
Хотя процесс Node.js будет выполнять трудоемкие вычисления, выполненные запросы не смогут быть выполнены соответствующим образом.
Однако есть некоторые обходные пути для решений на основе Node.js, такие как создание дополнительных узлов и реализация способа связи между ними.
Подводить итоги
MapReduce хорошо подходит для задачи ранжирования. Это не только устраняет большую часть вычислительных затрат, но и накладных расходов на реализацию.