人工知能とコンピュータ期末レポート

##課題2 研究室配属決定問題 ###Q. 80名の学生が8つの研究室に配属される。学生が希望順位を申請し,できるだけ希望を叶える配属先を決定する最適解探索問題と考える時,これを全数探索(全ての場合の評価値を計算)する場合の候補数の数を,研究室の定員が10名丁度とする場合と,定員数に制限がない場合(1研究室に80名が集中しても可)について,それぞれ計算せよ
また、毎秒1,000万回評価値を計算できる計算機でどれくらいの時間(もしくは日数や年数)がかかるかをそれぞれ計算せよ
###A. 定員数10とする場合
(aCb) は a個から b個を取る組み合わせの数
(80C10) * (70C10) * ... * (10C10)
Rubyスクリプトで演算した結果
ruby 2.1.5p273 (2014-11-13 revision 48405) [x86_64-linux]

def comb_num(n, k)
  range_fact(n, k).div(range_fact(k, k))
end
def range_fact(n, k)
  (n-k+1..n).inject(1) {|r, v| r * v}
end
p (1..8).inject(1) {|r, v| r * comb_num(80, v * 10)}

パターン数
2380254854046163126683949421708285053672305429067135034327451648000
毎秒1,000万回計算できる計算機であると
nを2.3 * 10^66とする
n = x * 10^7 / sec
1 yearは (60 * 60 * 24 * 365) sec
1 year = 31536000 sec つまり sec = (1 / 31536000) year
n = x * 10^7 / ((1 / 31536000) year)
x = n * ((1 / 31536000) year) / 10^7
x = (n / 3.1536000 * 10^14) year

n = (1..8).inject(1) {|r, v| r * comb_num(80, v * 10)}
p n / 315360000000000

結果
7547738629014976936466100398618356968773165363607099
=> 約 7.5 * 10^51 年

同じ要領で制限なしについても計算する
組み合わせ方は単純になり8 の 80乗であるため

p n = 8 ** 80
p n / 315360000000000

結果
1766847064778384329583297500742918515827483896875618958121606201292619776
5602635289124760050682703896318234766068886025100263058477
=> 約 1.7 * 10^72 パターン
=> 約 5.6 * 10^57 年かかる

解
それぞれ,約 7.5 * 10^51 年, 約 5.6 * 10^57 年かかる

##課題3 相関ルール ###Q. 最小支持度 = 0.2, 最小確信度 = 0.7 を満たす相関ルールが下記だけとなるようなトランザクション数が10のトランザクション型データを例示せよ.
{A, B} => C, {D} => E (ただし A, B, C, D, E はアイテム)

###A. アプリオアルゴリズムから

まず最小支持度 0.2 を満たすために (A, B, C)全て, また(D, E)全てを含むトランザクションは2つ以上必要となる
最小確信度 0.7のためルールに該当するトランザクションの割合として 3:4, 4:5 はオーバー 3:5, 2:3 がアンダーであることを意識する
{A, B, C} に対して {A, B}の組み合わせのみ確信度を上げる必要がある.
よって {A, C}∧Bなし {B, C}∧Aなし 3つのうちひとつだけのトランザクションが必要
さらに上記ルールにおいて最小確信度 0.7 を満たすために {E} => D の確信度を下げる必要があるため {D}∧E無しトランザクションが必要
最小支持度 0.2のため２つ組み合わせが一度しか出現しないパターンは意味のないトランザクションとなる
以上を踏まえたトランザクション10個の予想を適当に作る

Python 3.4.2

# -*- coding: utf-8 -*-
'''
最小支持度 = 0.2, 最小確信度 = 0.7
{A, B} => C, {D} => E, トランザクション数10
の例を探す

'''
import random
import itertools

def sample5():
    """
    aからeの中から2から4個をサンプルして返す
    """
    ra = random.sample(list('abcde'), random.randint(2, 4))
    random.shuffle(ra)
    return ra

def ap5(tras, support, confidence):
    c = len(tras)
    pas1 = { 'a':0, 'b':0, 'c':0, 'd':0, 'e':0 }
    for tra in tras:
        for item in tra:
            pas1[item] += 1
    pas1 = {i:pas1[i] for i in pas1 if pas1[i] / c >= 0.2 }
#    print(pas1)
    pas2 = {i:0 for i in list(itertools.combinations(pas1, 2))}
    for tra in tras:
        for (sa, sb) in pas2:
            if (sa in tra) and (sb in tra):
                pas2[(sa, sb)] += 1
    pas2 = {i:pas2[i] for i in pas2 if pas2[i] / c >= 0.2 }
#    print(pas2)
    pas3 = {i:0 for i in list(itertools.combinations(pas1, 3))}
    for ps in pas3:
        pas3 = {i:0 for i in pas3 if len(list(1 for j in list(itertools.combinations(i, 2)) if j in pas2)) == 3}
    for tra in tras:
        for (sa, sb, sc) in pas3:
            if (sa in tra) and (sb in tra) and (sc in tra):
                pas3[(sa, sb, sc)] += 1
    pas3 = {i:pas3[i] for i in pas3 if pas3[i] / c >= 0.2 }
#    print(pas3)
#    if ('a', 'b', 'c') not in pas3:
#        return False
    igrules = []
    for ps in pas3:
        igrules.extend({i:0 for i in list(itertools.combinations(ps, 2))})
    igrules = list(set(igrules))

    rules = {}
    for a, b in pas2:
        if (a, b) in igrules:
            continue
        v = pas2[(a, b)]
        rules[a, b] = v
        rules[b, a] = v

    for ps in pas3:
        v = pas3[ps]
        for (a, b, c) in list(itertools.permutations(ps, 3)):
            rules[(a, b), c] = v
            rules[a, (b, c)] = v

    res = []
    for a, b in rules:
        vp = 0
        va = rules[a, b]
        if len(a) == 2:
            if a not in pas2:
                continue
            vp = pas2[a]
        else:
            vp = pas1[a]
        if va / vp >= confidence:
            res.append((a, b))
    return res

queue = []
for i in range(10):
    queue.append(sample5())

for i in range(10000):
    res = ap5(queue, 0.2, 0.7)
    if len(res) == 2 and ((('a', 'b'), 'c') in res) and (('d', 'e') in res):
        print(queue)
        print(res)
    queue.pop()
    queue.insert(0, sample5())

Python でアプリオアルゴリズムによるフィルターを行うプログラムを組んでパターンを探してみた
2〜4のアイテムのみの組み合わせでランダムにサンプリングした結果50000パターンに一つ程度の割合で発見できた
[['a', 'e'], ['e', 'a', 'd', 'c'], ['b', 'c', 'a', 'e'], ['e', 'b', 'd'], ['d', 'e'], ['e', 'c'], ['e', 'b'], ['a', 'c'], ['b', 'c', 'a'], ['c', 'b']]

A, B, C, E
A, B, C
A, C
A, C, D, E
A, E
B, C
B, D, E
B, E
D, E
C, E

アプリオアルゴリズムでルールを抽出して検証
パス1
Item,Count

{A} 5
{B} 5
{C} 6
{D} 3
{E} 7 最小支持率 0.2, トランザクション数 10 より
全て対象

パス2 Item,Count

{A, B} 2
{A, C} 4
{A, D} 1 x
{A, E} 3
{B, C} 3
{B, D} 1 x
{B, E} 2
{C, D} 1 x
{C, E} 3
{D, E} 3 最小支持率 0.2, トランザクション数 10 より
Item,Count
{A, B} 2
{A, C} 4
{A, E} 3
{B, C} 3
{B, E} 2
{C, E} 3
{D, E} 3

パス3

{A, B}, {B, C}, {A, C} より {A, B, C}
{A, B}, {B, E}, {A, E} より {A, B, E}
{A, C}, {C, E}, {A, E} より {A, C, E}
{B, C}, {C, E}, {B, E} より {B, C, E} Item,Count
{A, B, C} 2
{A, B, E} 1 x
{A, C, E} 2
{B, C, E} 1 x 最小支持率 0.2, トランザクション数 10 より
{A, B, C} 2
{A, C, E} 2

確信度を出していく

{A} 5 x
{B} 5 x
{C} 6 x
{D} 3 x
{E} 7 x
{A, B} 2 x
{A, C} 4 x
{A, E} 3 x
{B, C} 3 x
{B, E} 2
{C, E} 3 x
{D, E} 3
{A, B, C} 2
{A, C, E} 2

{B, E}, {D, E}, {A, B, C}, {A, C, E} ->

{B} => {E}
2 / 5 = 0.4 x
{E} => {B}
2 / 7 = 0.28 x

{D} => {E}
3 / 3 = 1.0 o
{E} => {D}
3 / 7 = 0.42

{A, B} => {C}
2 / 2 = 1.0 o
{A, C} => {B}
2 / 4 = 0.5 x
{B, C} => {A}
2 / 3 = 0.66 x

{A} => {B, C}
2 / 5 = 0.4 x
{B} => {A, C}
2 / 5 = 0.4 x
{C} => {A, B}
2 / 6 = 0.33 x

{A, C} => {E}
2 / 4 = 0.5 x
{A, E} => {C}
2 / 3 = 0.66 x
{E, C} => {A}
2 / 3 = 0.66 x

{A} => {E, C}
2 / 5 = 0.4 x
{C} => {A, E}
2 / 6 = 0.33 x
{E} => {A, C}
2 / 7 = 0.28 x
最小確信率 0.7から
{A, B} => {C}
{D} => {E}
のみとなるためこの組み合わせは問の条件を満たす解である

プログラムから求められた10個のトランザクション

A, B, C, E
A, B, C
A, C
A, C, D, E
A, E
B, C
B, D, E
B, E
D, E
C, E

手動で導くための考察
A, B, Cまたは D, Eのそれぞれの組み合わせを含むトランザクションを絞ってから調節をする
最小確信度0.7を満たすために
A, B, Cを含むトランザクションの数が2つの時について考える
上の2つのトランザクション以外に, {A, B, C}3つのうち A, Bのみ含むトランザクションの数は1つもあってはならない
上の2つのトランザクション以外に, {A, B, C}3つのうち {A, C}のみ, {B, C}のみ, {A}のみ, {B}のみ, {C}のみ含むトランザクションの数は1つ以上なくてはならない

A, B, C
A, B, C
A
B
C
A, C
B, C さらにD, Eを含むトランザクションの数が3つの時について考える上の3つのトランザクション以外に, {D, E}2つのうち Dのみ含むトランザクションの数は1つもあってはならない上の3つのトランザクション以外に, {D, E}2つのうち Eのみ含むトランザクションの数は1つ以上なくてはならない
A, B, C
A, B, C
A, D, E
B
C, E
A, C
B, C
D, E
D, E

{A, B, C}と{D, E}それぞれの支持率が上がらないようにばらけさせる

A, B, C
A, B, C
A, D, E
B
C, E
A, C
B, C
D, E
D, E
A, C, E トランザクション数が10になるように前述条件に沿ってトランザクションを追加する
作ったPythonスクリプトでユニットチェックしてみる

q = [['a', 'b', 'c'], ['a', 'b', 'c'], ['a', 'd', 'e'], ['b'], ['c', 'e'], ['a', 'c'], ['b', 'c'], ['d', 'e'], ['d', 'e'], ['a', 'c', 'e']]
res = ap5(q, 0.2, 0.7)
print(res)

出力 [(('a', 'b'), 'c'), ('d', 'e')]

見事に問のルールに絞ることが出来た

解(2例)

[['a', 'e'], ['e', 'a', 'd', 'c'], ['b', 'c', 'a', 'e'], ['e', 'b', 'd'], ['d', 'e'], ['e', 'c'], ['e', 'b'], ['a', 'c'], ['b', 'c', 'a'], ['c', 'b']]
[['a', 'b', 'c'], ['a', 'b', 'c'], ['a', 'd', 'e'], ['b'], ['c', 'e'], ['a', 'c'], ['b', 'c'], ['d', 'e'], ['d', 'e'], ['a', 'c', 'e']]

##課題5 認証システムの detection rate (DR) と false positive rate (FPR) ###Q. DR と、 FPR はトレードオフの関係にあるが、システムの用途に応じて妥協点の設定方針が変わってくるはずである。下記の2種類の応用システムに関してどういう方針を取るべきか、その理由を添えて詳しく論じよ
(a) ショーウィンドウを振り返って見る人数のカメラ画像による計測
(b) 入室管理のための指紋認証
###A. (a)
DRつまり検出率を重視するべきである
誤検知率が大きすぎない限り検出するサンプルの数が多い事が重要であると思われるため
(b)
FPRつまり正確性を重視するべきである
入室管理のため誤検知があってはシステムに影響があるため

##課題6 関数型言語LISP と論理型言語Prolog ###Q. 階乗を n! とするとき, n! x (n -1) ! x ... x 2! x 1! を計算する multifact を LSIP と Prolog でそれぞれ記述せよ ###A.

LISP GNU CLISP 2.49 (2010-07-07) (built on var-lib-archbuild-extra-x86_64-barthalion) Software: GNU C 4.8.2 20131219 (prerelease)

(defun fact (n)
  ;; 階乗関数
  (cond ((= n 0) 1)
    (t (* n(fact (- n 1))))
  )
)
(defun multifact (n)
  ;; マルチファクト関数
  (cond ((= n 0) 1)
    (t (* (fact n) (multifact (- n 1))))
  )
)

;;; マルチファクト 3 の結果出力
(write (multifact 3))

Prolog SWI-Prolog version 6.6.6 for x86_64-linux

fact(N, 1) :-
    N < 1, !.
fact(N, X) :-
    N1 is N - 1,
    fact(N1, Y),
    X is N * Y.
multifact(N, 1) :-
    N < 1, !.
multifact(N, X) :-
    N1 is N - 1,
    multifact(N1, Y),
    fact(N, Z),
    X is Z * Y.

elzup/report.md

Select an option

No results found

Select an option

No results found

人工知能とコンピュータ期末レポート

elzup/report.md

人工知能とコンピュータ 期末レポート

人工知能とコンピュータ期末レポート