中文字幕av专区_日韩电影在线播放_精品国产精品久久一区免费式_av在线免费观看网站

溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

使用golang基本數據結構與算法網頁排名/PageRank實現隨機游走

發布時間：2021-10-18 10:56:49 來源：億速云 閱讀：142 作者：iii 欄目：編程語言

本篇內容介紹了“使用golang基本數據結構與算法網頁排名/PageRank實現隨機游走”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

網頁排名(PageRank/佩奇排名), 隨機游走

網頁排名（PageRank，也叫作佩奇排名）是一種在搜索網頁時對搜索結果進行排序的算法。

網頁排名就是利用網頁之間的鏈接結構計算出網頁價值的算法。
在網頁排名中，鏈入頁面越多的網頁，它的重要性也就越高。

假設沒有鏈入頁面的網頁權重為1。
有鏈入頁面的網頁權重是其鏈入頁面的權重之和。
如果一個網頁鏈向多個頁面，那么其鏈向的所有頁面將平分它的權重。
在網頁排名中，鏈入的頁面越多，該網頁所發出的鏈接的價值就越高。

可以使用“隨機游走模型”（random walk model）來解決網頁互鏈的問題.

用戶瀏覽網頁的操作就可以這樣來定義：
用戶等概率跳轉到當前網頁所鏈向的一個網頁的概率為1-α；
等概率遠程跳轉到其他網頁中的一個網頁的概率為α。

模擬用戶隨機訪問頁面的過程, 
每訪問一個頁面, 其權重加1,
直到訪問的總次數達到N次為止,
每個頁面的權重值代表的是“某一刻正在瀏覽這個網頁的概率”，
可直接將其作為網頁的權重來使用。

摘自 <<我的第一本算法書>> 【日】石田保輝；宮崎修一

目標

  • 實現基于隨機游走模型的PageRank算法, 并驗證其有效性和穩定性(網頁權重在模擬若干次后, 保持穩定)

設計

  • IPage: 網頁模型接口

  • IPageRanking: 網頁排名算法接口

  • tPage: 網頁模型的實現

  • tRandomWalkPageRanking: 基于隨機游走模型的PageRank算法, 實現IPageRanking接口

單元測試

  • page_rank_test.go, 驗證網頁排名算法的有效性和穩定性

  • 首先通過簡單case驗證其有效性

  • 然后隨機生成大批量隨機互鏈的網頁, 驗證在多輪隨機游走后, 網頁權重的穩定性

package others

import (
	"fmt"
	pr "learning/gooop/others/page_rank"
	"math/rand"
	"sort"
	"testing"
	"time"
)

func Test_PageRank(t *testing.T) {
	fnAssertTrue := func(b bool, msg string) {
		if !b {
			t.Fatal(msg)
		}
	}

	t.Log("testing simple case")
	p11 := pr.NewPage("p11")
	p12 := pr.NewPage("p12")
	p13 := pr.NewPage("p13")
	p21 := pr.NewPage("p21")
	p22 := pr.NewPage("p22")
	p31 := pr.NewPage("p31")
	p32 := pr.NewPage("p32")

	p11.AddLink(p21)
	p11.AddLink(p22)
	p12.AddLink(p21)
	p12.AddLink(p22)
	p13.AddLink(p21)
	p13.AddLink(p22)

	p21.AddLink(p31)
	p22.AddLink(p31)

	p31.AddLink(p32)
	p32.AddLink(p31)

	samples := []pr.IPage{
		p11,p12,p13, p21, p22, p31, p32,
	}
	pr.RandomWalkPageRanking.RankAll(samples, 1000)
	sort.Sort(sort.Reverse(pr.IPageSlice(samples)))
	for _,p := range samples {
		t.Log(p)
	}
	fnAssertTrue(samples[0].ID() == "p31", "expecting top.1 = p31")
	fnAssertTrue(samples[1].ID() == "p32", "expecting top.2 = p32")
	fnAssertTrue(samples[2].ID() == "p21" || samples[2].ID() == "p22", "expecting top.3 in (p21,p22)")
	fnAssertTrue(samples[3].ID() == "p21" || samples[3].ID() == "p22", "expecting top.4 in (p21,p22)")


	// generate 1000 random pages
	iPageCount := 1000
	pages := make([]pr.IPage, iPageCount)
	for i,_ := range pages {
		pages[i] = pr.NewPage(fmt.Sprintf("p%02d.com", i))
	}

	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	for i,p := range pages {
		// add random page links
		for j,iPageLinks := 0, r.Intn(10);j < iPageLinks; {
			n := r.Intn(iPageCount)
			if n != i {
				j++
				p.AddLink(pages[n])
			}
		}
	}

	// rank pages and get top 100
	mapTop100 := make(map[string]bool, 0)
	fnTestRanking := func(rounds int) {
		t.Logf("testing page rank with %v rounds", rounds)
		bFirstRound := len(mapTop100) == 0

		// page ranking
		pr.RandomWalkPageRanking.RankAll(pages, rounds)

		// sort pages by ranking
		sort.Sort(sort.Reverse(pr.IPageSlice(pages)))

		hits := 0
		for i,p := range pages {
			if i < 10 {
				t.Log(p)
			}

			if i < 100 {
				if bFirstRound {
					mapTop100[p.ID()] = true
				} else if _,ok := mapTop100[p.ID()];ok {
					hits++
				}
			} else {
				break
			}
		}

		if !bFirstRound {
			t.Logf("hit rate: %s%v", "%", hits)
		}
	}

	// test stability under different rounds
	fnTestRanking(3000)
	fnTestRanking(10000)
	fnTestRanking(30000)
	fnTestRanking(90000)
}

測試輸出

  • 測試表明, 當隨機游走的總次數 >= 網頁數量 * 每個網頁的平均發出鏈接數時, 所得排名是比較穩定的

$ go test -v page_rank_test.go 
=== RUN   Test_PageRank
    page_rank_test.go:19: testing simple case
    page_rank_test.go:47: p(p31,   0.4206, [p32])
    page_rank_test.go:47: p(p32,   0.3673, [p31])
    page_rank_test.go:47: p(p21,   0.0639, [p31])
    page_rank_test.go:47: p(p22,   0.0604, [p31])
    page_rank_test.go:47: p(p11,   0.0300, [p21 p22])
    page_rank_test.go:47: p(p12,   0.0291, [p21 p22])
    page_rank_test.go:47: p(p13,   0.0287, [p21 p22])
    page_rank_test.go:77: testing page rank with 3000 rounds
    page_rank_test.go:89: p(p604.com,   0.0039, [])
    page_rank_test.go:89: p(p807.com,   0.0035, [p709.com p328.com p303.com p110.com p858.com p394.com p231.com p731.com p83.com])
    page_rank_test.go:89: p(p72.com,   0.0034, [p249.com p347.com p604.com p533.com p416.com p958.com p966.com p385.com])
    page_rank_test.go:89: p(p712.com,   0.0033, [p485.com p451.com p236.com p141.com p168.com p693.com])
    page_rank_test.go:89: p(p452.com,   0.0032, [p588.com p344.com p618.com p258.com p394.com p285.com p780.com p606.com p89.com])
    page_rank_test.go:89: p(p709.com,   0.0031, [p666.com p554.com p103.com p202.com p230.com])
    page_rank_test.go:89: p(p975.com,   0.0029, [])
    page_rank_test.go:89: p(p840.com,   0.0029, [p974.com p698.com p49.com p851.com p73.com])
    page_rank_test.go:89: p(p867.com,   0.0028, [p588.com p196.com p931.com p381.com p621.com p848.com])
    page_rank_test.go:89: p(p633.com,   0.0028, [p840.com])
    page_rank_test.go:77: testing page rank with 10000 rounds
    page_rank_test.go:89: p(p604.com,   0.0039, [])
    page_rank_test.go:89: p(p807.com,   0.0034, [p709.com p328.com p303.com p110.com p858.com p394.com p231.com p731.com p83.com])
    page_rank_test.go:89: p(p72.com,   0.0034, [p249.com p347.com p604.com p533.com p416.com p958.com p966.com p385.com])
    page_rank_test.go:89: p(p452.com,   0.0033, [p588.com p344.com p618.com p258.com p394.com p285.com p780.com p606.com p89.com])
    page_rank_test.go:89: p(p712.com,   0.0033, [p485.com p451.com p236.com p141.com p168.com p693.com])
    page_rank_test.go:89: p(p709.com,   0.0031, [p666.com p554.com p103.com p202.com p230.com])
    page_rank_test.go:89: p(p975.com,   0.0029, [])
    page_rank_test.go:89: p(p840.com,   0.0029, [p974.com p698.com p49.com p851.com p73.com])
    page_rank_test.go:89: p(p612.com,   0.0028, [p116.com p562.com p179.com p37.com p761.com])
    page_rank_test.go:89: p(p319.com,   0.0028, [p726.com p63.com p558.com p301.com p185.com p944.com])
    page_rank_test.go:104: hit rate: %98
    page_rank_test.go:77: testing page rank with 30000 rounds
    page_rank_test.go:89: p(p604.com,   0.0039, [])
    page_rank_test.go:89: p(p807.com,   0.0034, [p709.com p328.com p303.com p110.com p858.com p394.com p231.com p731.com p83.com])
    page_rank_test.go:89: p(p72.com,   0.0034, [p249.com p347.com p604.com p533.com p416.com p958.com p966.com p385.com])
    page_rank_test.go:89: p(p452.com,   0.0033, [p588.com p344.com p618.com p258.com p394.com p285.com p780.com p606.com p89.com])
    page_rank_test.go:89: p(p712.com,   0.0032, [p485.com p451.com p236.com p141.com p168.com p693.com])
    page_rank_test.go:89: p(p709.com,   0.0031, [p666.com p554.com p103.com p202.com p230.com])
    page_rank_test.go:89: p(p975.com,   0.0029, [])
    page_rank_test.go:89: p(p840.com,   0.0029, [p974.com p698.com p49.com p851.com p73.com])
    page_rank_test.go:89: p(p319.com,   0.0028, [p726.com p63.com p558.com p301.com p185.com p944.com])
    page_rank_test.go:89: p(p612.com,   0.0028, [p116.com p562.com p179.com p37.com p761.com])
    page_rank_test.go:104: hit rate: %98
    page_rank_test.go:77: testing page rank with 90000 rounds
    page_rank_test.go:89: p(p604.com,   0.0039, [])
    page_rank_test.go:89: p(p807.com,   0.0034, [p709.com p328.com p303.com p110.com p858.com p394.com p231.com p731.com p83.com])
    page_rank_test.go:89: p(p72.com,   0.0034, [p249.com p347.com p604.com p533.com p416.com p958.com p966.com p385.com])
    page_rank_test.go:89: p(p452.com,   0.0033, [p588.com p344.com p618.com p258.com p394.com p285.com p780.com p606.com p89.com])
    page_rank_test.go:89: p(p712.com,   0.0032, [p485.com p451.com p236.com p141.com p168.com p693.com])
    page_rank_test.go:89: p(p709.com,   0.0031, [p666.com p554.com p103.com p202.com p230.com])
    page_rank_test.go:89: p(p975.com,   0.0029, [])
    page_rank_test.go:89: p(p840.com,   0.0029, [p974.com p698.com p49.com p851.com p73.com])
    page_rank_test.go:89: p(p612.com,   0.0028, [p116.com p562.com p179.com p37.com p761.com])
    page_rank_test.go:89: p(p319.com,   0.0028, [p726.com p63.com p558.com p301.com p185.com p944.com])
    page_rank_test.go:104: hit rate: %98
--- PASS: Test_PageRank (13.93s)
PASS
ok      command-line-arguments  13.936s

IPage.go

網頁模型接口

package page_rank

import "fmt"

type IPage interface {
	fmt.Stringer

	ID() string

	GetWeight() float64
	SetWeight(float64)

	GetLinks() []IPage
	AddLink(IPage)
}


type IPageSlice []IPage

func (me IPageSlice) Len() int {
	return len(me)
}

func (me IPageSlice) Less(i,j int) bool {
	return me[i].GetWeight() < me[j].GetWeight()
}

func (me IPageSlice) Swap(i,j int) {
	me[i], me[j] = me[j], me[i]
}

IPageRanking.go

網頁排名算法接口

package page_rank

type IPageRanking interface {
	RankAll(pages []IPage, rounds int)
}

tPage.go

網頁模型的實現

package page_rank

import (
	"fmt"
	"strings"
)

type tPage struct {
	id string
	weight float64
	links []IPage
}

func NewPage(id string) IPage {
	return &tPage{
		id: id,
		weight: 0,
		links: []IPage{},
	}
}

func (me *tPage) ID() string {
	return me.id
}

func (me *tPage) GetWeight() float64 {
	return me.weight
}

func (me *tPage) SetWeight(w float64) {
	me.weight = w
}

func (me *tPage) GetLinks() []IPage {
	return me.links
}

func (me *tPage) AddLink(p IPage) {
	me.links = append(me.links, p)
}

func (me *tPage) String() string {
	linkStrings := make([]string, len(me.links))
	for i,p := range me.links {
		linkStrings[i] = p.ID()
	}
	return fmt.Sprintf("p(%v, %8.4f, [%v])", me.id, me.weight, strings.Join(linkStrings, " "))
}

tRandomWalkPageRanking.go

基于隨機游走模型的PageRank算法, 實現IPageRanking接口

package page_rank

import (
	"math/rand"
	"time"
)

type tRandomWalkPageRanking struct {
}

var gPossiblityToLinkedPage = 85

func newRandomWalkPageRanking() IPageRanking {
	return &tRandomWalkPageRanking{}
}

func (me *tRandomWalkPageRanking) RankAll(pages []IPage, rounds int) {
	iPageCount := len(pages)
	if iPageCount <= 0 {
		return
	}

	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	current := pages[0]

	iVisitCount := iPageCount * rounds
	for i := 0;i < iVisitCount;i++ {
		// visit current page
		current.SetWeight(current.GetWeight() + 1)

		possibility := r.Intn(100)
		if possibility < gPossiblityToLinkedPage && len(current.GetLinks())>0 {
			// goto linked page
			current = me.VisitLinkedPage(current, r)

		} else {
			// goto unlinked page
			current = me.VisitUnlinkedPage(current, pages, r)
		}
	}

	fVisitCount := float64(iVisitCount)
	for _,p := range pages {
		p.SetWeight(p.GetWeight() / fVisitCount)
	}
}


func (me *tRandomWalkPageRanking) VisitLinkedPage(current IPage, r *rand.Rand) IPage {
	links := current.GetLinks()
	next := links[r.Intn(len(links))]
	return next
}

func (me *tRandomWalkPageRanking) VisitUnlinkedPage(current IPage, pages []IPage, r *rand.Rand) IPage {
	mapLinks := make(map[string]bool, 0)
	mapLinks[current.ID()] = true
	for _,p := range current.GetLinks() {
		mapLinks[p.ID()] = true
	}

	n := len(pages)
	for {
		next := pages[r.Intn(n)]
		if _,ok := mapLinks[next.ID()];!ok {
			return next
		}
	}
}

var RandomWalkPageRanking = newRandomWalkPageRanking()

“使用golang基本數據結構與算法網頁排名/PageRank實現隨機游走”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！

向AI問一下細節

免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。

go
AI
助
手
特克斯县| 绥宁县| 仙游县| 察雅县| 敦化市| 汕尾市| 绍兴市| 达日县| 天门市| 灵石县| 麟游县| 浑源县| 宁阳县| 灵台县| 唐海县| 荥阳市| 岗巴县| 个旧市| 汾西县| 武川县| 奉化市| 石景山区| 奈曼旗| 奎屯市| 略阳县| 宁强县| 文山县| 岱山县| 麻阳| 炉霍县| 丰都县| 临桂县| 勃利县| 平泉县| 南宁市| 茌平县| 金阳县| 镇沅| 舒城县| 贺州市| 错那县|