ORと統計の融合

数理計画法を用いた最適線形判別関数（1）一理論的な背景一
新村 秀一…Fr＝‖＝＝＝‖＝＝‖‖＝＝＝＝＝＝‖＝＝‖‖＝‖＝＝＝‖‖帖刷州…【Lllll…1111州Il…LLllll【Llll【＝＝＝………＝llm州【LL＝＝＝‖‖＝＝…ll州＝＝…＝＝…＝＝L‖＝＝‖＝＝…＝＝側帖＝…Lll＝…＝＝冊削＝＝…＝＝＝刷川＝＝＝＝＝＝刑＝‖＝＝川＝＝＝＝＝州

はが提案されています．本講経では，こ本講座の目的タを川のデー

いて、2次判別関数やLlノルム型の判別関数より，

甘より『」近くて遠きは男女の仲』といいますが，ORと統計の関係も似たようなものでしょう．私l′1身，

OLDFが健れている1−：（，あるいはモデル．沖佃に川いる決定係数のI！り題∴1．（などを指摘します．

統計ソフトと数均とi汁画i去ソフトの普及や研究i舌重力を過4‖り一では，115組の2変端正税乱数デー

して，ORと統計に囲う・していながら，これらを結び．甘仙を行います［15］．このデータは，現実のデータでつける機会になかなかめぐり合いませんでした．このはそト、にくいクロスバリデーションを暮川くノとしており

坤由としては，ORは研究対象をモデルとして扱うのます．クロスバリデー

に対して，統計はデータを確率分布としてとらえ理論るデータでモデルを作成し，その結果を．沖仙します．

展開する∴l．くに，なかなか柵イ7二に理解できない，深い溝

これをInternalCheckと呼びます． 夫際のデータをがあるのではないかと思、つています．

分析する場介，この成績だけが示されることが多いの

今回，整数計画法を用いた新しい線形判別関数

タによるションとは，l畑酢櫻本と呼ばれですが，モデル構築に川いていないデータ（外部標（OptimalLinear Discriminant Function，略して本）でExternalCheckをする必安があります．これOLDF）を開発し，3樺類の異なったデータで評価をを行うのは，InternalCheckの結果は内部標本のデ行い良い結米を得たので，その概安を以下のように紹ータが少ないほど，また川いる説明変数が多いほど，過人に．沖価 りユかけ卜，良い結果が得られる）される介するナ定です．

本号て、は，判別分析の概略とOLDFグ）定式化を紹からです［1］．クロスバリデーションを行った後，得られたモデルを現尖の問題に過川すべきでしょう．最介します．

2‖圭一では，Fisherのアイ1）スデータによる評価を

近問題になっている介護保険の評価システムは，内部行います［14］．このデータは，判別分析やクラスタ岬

標本での結果が良かったので，クロスバリデーション

分析の．刑l附こ川いられ，Iけ二界lいの統計家が知識を共有を十分行わず，システム化したことに問題があるようする共有財であります．このデ岬タで，OLDFの和です．統計！、iキの社会への大きな貢献の事例になったか解が深まることを意lズⅠしています．また，このデータもしれないのに，逆の結果になり非常に残念そこです．

を川いた統計の教科書を作成していますので参考にしクロスバリデーてください［13］．

ておろそかにしていけなし、プリンシプルであります．

3‖ゝユーでは，多束共敵性のある際、予デー

タによる評ションは，応用統計家にとって，決し

一方，理論家は従来新しい埋諭を開発した場合，そ仙を行います［14］．川堀分析では，謝明変数悶＝こ高いの評佃を他人化せにしてきました．しかし，PCの能相関があれば㌣測結果が不安定になることは良く知ら

力が㈹躍r畑こ向上している今，れています．これが多市共線性と呼ばれている悩まし

省「1らが．沖佃すべきであると考えています．例えば，

い関越です．判別分析においてもI■iJじことがいえます．

2次判別関数は理論の卜でも二重要であり，興味ある認

文献［7，12］では，このデータを川いて多重共線関係

識を我々に提供しています．すなわち，判別される2のある説明変数の検出，その解消法とモデル決定のノJ群が多次フt1L配分布で等分散であればFisherの線形提案する新手法は提案

判別関数を，そうでなければ2次、判別関数をf†巨−るべしんむJ〕 しゅういち
成踵人一、戸綿済サ部

きということが，これまでの常識でした．しかし，l矢〒18（卜8633武蔵野IIJ．Hけ寺北町33√1！、；÷データという呪一夫のデータと乱数データで，この指38（38）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

針が止しくない多くの■糾列が示されています．

これが，今回3種類のデータで評価を行った成果で基準とする手法である．この基準は，確率分布を考えないので，多くの統計′束には受け入れ難い基準である．

すなわち，これまでは標本誤分類数はバイアスに弱く，あります．
5‖号で、は，従来の推測統計′！㌢に対して深刻な問題

判別境界点が変わるにつれ変化するので使えないと考を提起しているデータマイニングの小核rlくノな手法であえられてきた．しかし，l刃部標本の誤分類数を直接まl麦る決定本分析による判別結果を紹介する予定でいます．

小化する基準を耽れば，計算時間がかかることを別とすなわち，これまでの統計一芋は小標本を想定し，確率

して，判別分析の理論に黄献できることが分かった．

分布から仰無仮説がl卜しいか否かを有志確率（p値）

ベイズの定理とOLDF以外の手法は，最近の統i汁でもって判断していました．しかし，データが増えてパッケージに含まれている．

いけばp値は′トさくなっていき，やがて棄却される形式でデータ空間を分割するlズ分一川別関数のように，運命にあります．すなわち，検定諭はデータを多く集提案されたが現渓に応川されていない判別了・法も数多

めればイ川ーになってしまうわけです．この一・ご、（で，デー

くある．これは，理論の提案者が，自分Fl身でその有タマイニングは従来の推測統計学に対して深刻な問題

川性を実証しないで他人任せにしてきた結果であろう．

を提示しているわけであります．ORにとっての黒船

今後は，新しい理論は簡単に検証できるので，その有はいつどこから現れるのでしょうか．

＝＝隼もホし，多くのユーザーを得るように努める必要

一ガ，データマイニングも，かつてのAIブームのこれに対して，複数の線がある．

ように熱狂に包まれ，冷静さを欠く面があるようです．

しかし，従来の推測統計学のアンチテーゼとして脚今回は決定本分析でIP−OLDFの結果を比較すること

光を浴びているデータマイニングの手法には，統i汁パ

をtl的としていますが，逆に決定木分析の各・丁・法を伝ッケージで忘れ上られたベイズの定理による判別丁・法統的な判別分析と比較評価することにもなります．

を含むものもあるようだ．それゆえ，理論一束が，役に）ンニとうが立つまいが，色々な理論を開発することは轟1．判別分析について要である．それほど才能のない私のような後世の人た

1．1判別分析の分類

ちの選択肢が広がるということはありがたいことだ．

判別分析の代表的な手法として，Fisherの線形判

後仲に残る理論を開発できる天才の椅子は限られてい別関数と2次判別関数がある．これらはパラメトリッ

るが，それらを現実の問題に応用し役立てる作業は数クな手法で，、I朋りされる2群が多次元正規分布である

多くあるのではなかろうか．豊かな社会になればなると仮定し，説明変数の1次式と2次式で表される．2ほど，この比車は高まっていくものと考えられる．

群の分散共分散行列が等しければ線形判別関数を，等

本講座では，繋数計内法を川いた新しいIP−OLDF

しくなければ2次判別関数を別いればよいとされてきと，これまでも提案されているLP を川いたLP線形

た．

1勺川り関数（LP−OLDF）を提案し，従来の判別手法とこれに対し，ノンパラメトリックな手法として，離散変量に対してはベイズの定理による判別手法があり，比較許佃することにより，これまでと異なった視点で判別分析を見漉したい．

連続変昼に対しては崩近隣ルールによる手法（複数の1．2 Fisherの線形判別関数と2次判別関数

群からのマハラノビウスの距離を求め，一番小さな抑（1）Fisherの線形判別関数

離を持つ群に判別する．多群判別にも過川【Ir能）があFisherの線形判別関数は，p偶の説明変数をもつ2群が，次式で表わされるp変量多次元正規分布に従る．

また，分散比，尤度比，誤分類数（あるいは正しく分類された数）という，判定に川いる基準によって分けることができる．分散比による手法としては，Fi−う確率密度関数をもつと仮定して導出できる．
fi（x）＝（1／SQRT（（27r）P＊L∑lL））＊e〈卜（x，ml）′＊∑rl（x−mt）／2］

sherの線形判別関数，il三準判別関数，林の数騒化II

x：説明変数のp次元行ベクトル類がある．Fisherの線形判別関数は，2群が多次元正

mi：i群のⅩの、ド均行ベクトル

規分布に従い分散共分散が等しいことを仮定している．

∑1：i群の分散共分散行列（i＝1，2）

尤度比による手法としては，多重ロジスティックモデ

2群の分散共分散行列が等しい（∑1＝∑2＝∑）として，

ルがある．本講座で紹介するOLDFは，誤分類数を次の尤度比fl（X）／f2（X）の対数をとった関数F（x）を2002年1Jjり・© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（39）39

そえる．

1．3 判別関数の問題点

判別関数の問題点は色々あるが，本講座では内部標

F（x）＝log［f．（X）／f2（X）】＝（x−（ml十m2）／2〉′∑¶1（mrm2）

本と相集川（あるいは外部標本）の関係，■拝前確率と＝x′∑■l（mrm2）▼（m．＋m2）′

リスクの抜い，モデル選択のノバ去論の3点に関してホ
したい．

×∑▼l（ml−m2）／2

このF（x）は，F（x）＝X′β＋β0というxの線形関数に（1）内部標本と外部ノ標本の関係なっている．これをFisherの線形判別関数と呼ぶ．

（丑 吋マハラノビスの蝉離と標本マハラノビスの抑

一〟，2群のデータ件数をIllとn2として，データをl群と2肝の順に並べ竹えて，新しい＝的変数y酢

各群は多次元】仁規分布であると仮定する．そして，の仙として1群に1／Ill（あるいは0），2群に−1／n2

各ケースxと紆群の平均miとのマハラノビス（Ma−（あるいは1）をり▲える．このようにして判別分析のhalanobis）の神経MD2は，次の式で定義される．

データをl叶甘分析のソフトウエアで解析すれば，回帰MD2＝（x−mi）′∑「1（x−mj）

分析によって得られる回帰係数は，Fisherの線形 川

そして，マハラノビスの距離MI）2の大小で，どの肝別関数の、ドIj別係数と比例関係になる．すなわち，、t勺川りに属するかがi火定される．すなわちマハラノビスの抑分析は卜小届分斬・の特殊応川例に還元される．

離は，判別空一日＝こおける2つのデータl別の跡継を表し

これにより，巨車11‡分析で開発された逐次変数選択法ている．マハラノビスの抑離が人きいほど離れており，に代表されるモデル選択の知識や統計ソフトが利川で小さいほど近いことになる．この抑離はユークリド抑きる．また，統計の朝一リ 束でない場合，、川別分析の坤

離の上に，データの確率密度を考慮したものと埋解し．諭を特別に一、㌣習しないで回帰分析で代目できる．本講ておけばよいだろう．

仲では触れないが，データを工人することで数斌化Ⅰ

このとき，2肝の吋マハラノビスの抑離∂と標本マ

増や数二‡‡し化ⅠⅠ粕も回帰分析や判別分析で代川できる

ハラノビスの抑離Dとの関係は，次のように要約さ［9］．このような主張は，林の数量化理論を矯めにす

れる［1］．

る怒見ではなく，ORワーカーとして現実l甘越に対応

標本マハラノビスの粧離は，標本数が少ないほど，する場合，思考の節約ができることと，鳥のように広あるいは変数が多いほど，吋マハラノビスの抑離よりく対象を傭嘩できる利一・1（からの指摘である．

大きくなる確率が−；▲古くなる．すなわち，少ないデー（2）2次判別関数

や，多くの変数を川いて判別分析を行うと，標本誤判

2群の分散共分散行列が等しくない場合は，F（x）

別率￠（−D／2）は捗萬判別率￠（−∂／2）より過小．沖は次のようなxの2次形式になり．2次判別関数と呼伸される確率が−tlJiくなる．ただし，￠は規準正規分

ばれる．

布関数である．
すなわち，少ないデータで多くの説明変数を川いてF（x）＝1og［fl（X）／f2（X）］

分析すれば，判別成絨カゞよくなって、1たり舶で，それ＝X′（∑iし∑「1）x／2
十（nl；∑「1−nl昌∑il）x

を現実のデータに過川すればl劉倍たる結果になること＋（m；∑ilm2−mi∑Tlml）／2十cを意味する．あるいはシミュレーションなどで，制御

c：log［l∑21／l∑．1］

吋能な変数を数多くfIJいてモデル化すれば，作成者の線形判別関数に比べて，2次の係数がp（p−1）／2だけ意匝1のままどのような結米を得ることも可能であるこ咽える．このため，l勺部標本での兄かけ卜の誤判別率とと対応している．

は一般「1くノに良くなるのは、うたリIiiiのことである．

2群の分散共分散行列が等しい（l∑1l＝l∑2】）という

このため，判別結果が0verestimateされない良いモデルを作成するためには，モデル構築に刑いる質のタをできるだけ多く集めるか，モデル作成に

帰無仮説に対し，ズ2検定で棄却されれば2次判別関高し、デー数を採用し，棄却されなければ線形判別関数を選ぶこ

川いる変数はできるだけ少ないノノがよいという「ケチとが拙論「畑こ推奨されてきた．

の原理（Principalof parsimony）」あるいは「オッ

本講座では，この頗の［いで考え出された指針が，′夫際のデータへ適用して，妥三l与か′テかもホしたい．

カムの剃刀」の警たに従う必二安がある．このため，回帰分析では，変数を少なくするために逐次変数選択法などの手法が提案されてきた．本講座では，従来の変40（4（））

オペレーションズ・リサーチ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

タ数選択法の手法で用し、られてきた逐次F検定といわF（x）＞0であればGl群（あるいはG2群）と判別し，れるまったく無意味な停止Iiりに疑問を接げかけ，そのF（Ⅹ）く0であればG2群（あるいはGl群）と判別す推論的な意義は認めつつ，件．1＝iljを川いない基本系列

ることになる．

で比率交評晒することの有川J性をl匁学データで示す．ま（参：事前確率とリスクた，モデルの良さをホす決定係数のような従来の統計

しかし，2群の呼集川のサンプルサイズが異なる場介，その違いを事前確率爪，穐で表し，尤度比とし騒に対して，最小誤分類数の有川性を紹介する．
（卦 ExternalCheckて（方．fl）／（穐f2）を考える．すなわち，判別境軋・ご．くは0

一ノブ，甘矧寸は標本の関係を′実際に比較することはの代わりに，log（乃／れ）になる．
さらに，医療診断で正常群と疾病群（企業診断では，できないので，それに代わって外部標本による
ExternalCheckや，Jack knife法が川いられる．

優良企業と倒産企業と読み替える）を考えた場合，疾ExternalCheckは，l勺部標本で得られた判別関数を，病群の事前確率が小さくても謹も分類によるリスクは止外部標本に適川して−秤仙することである．すなわち，常群より人きく考える必要がある．この場合，リスク

相集川と標本集L寸】の関係は，「少ないデータや，多く

をr】，r2とすると，尤度比は（r17rlfl）／（r27Tうf2）になる．

の変数を川いて得られた判別関数は，外部標本に過川

締りのところ，事前確率やリスクを考えた場合の判別

すると一般的に恐くなる」と読み替えることができる．

境界は0でなく，log（（r27E2）／（r17rl））になる．

すなわち，l勺部標本で訳判別率が良くても，外部標本

以上の通り，事前確率とリスクは現実問題においての誤判別率が感ければ，その判別関数を採用しないこは重要であるが，その値を決定することは難しい佃もある．また，判別分析の評価のために椎々の統計量がとになる．

提案されているが，医・羊や企業などの実務分野では分

データが少ない場介，それらを内部標本と外部標本に分割することは心理的に紙抗が大きいので，Jack

かりやすい誤分類数がよく糾いられている．しかしすknife法などの代替法が川いられる．

でに述べた通り，事前確率とリスクの違いで，誤分類数が異なるという問題点がある．

③ 問題一rl（③ ROC曲線

この．r∴（から，同じデータに対してFisherの線形判

別開放と2次判別関数を適用しても，後、者は推定する

そこで，事前確率とリスクの違いは，F（x）の定数

パラメータ数が増えるので，兇かけの誤判別率は良く項の違いで表されることを利用して，それらの判別境なって当たり前である．しかし，2次判別関数の理論

界一戸、（を1t7†段階かで変えて，2群の止診率（True Posi−

は精緻であり魅力rlくノなので，あまり批判は行われてこtive）と誤判別率（False Positive）をx−y平、面にプなかった．

ロットしたROC曲線（Receiver Operating Charac−

teristic Curve）を描いて，各種判別結果の優劣の比−一方，内部標本の誤分類数を崩小化する基準で導出

較評イ面を行うことが考えられる［9］．

されるOLDFは，以上の議論とは異なるが，過度に内部標本に適介し外部標本に対しては想くなるのでは

例えば，文献［5］では，胃X線像のデータを各種三11j

ないかという危惧がある．すなわち，特定のデータに別分析（枝分かれ法，数最化ⅠⅠ類，ベイズ診断，多東依存し，結果がイ（安定であったり，普遍的な結果と縁口ジスティツタ，も成分分析，判別分析）で分析した遠いと考えられる．

結果と医師診断の結果をROCll‡I線で比較している．

本講雁では，以上の2点に関して具体的なデー分析結果で常識を醸す結果が得られることをH月らかにタの（3）モテルの評価

IP−OLDFの誤分類数は標本に対してr→意に決まり，変数を増加すると単調に減少するという性質がある．

したい．

本講伴では，IP−OLDFの誤分類数でもって，他の（2）事前確率とリスク（丑 尤度比判別関数の誤分類数を評価することを勧めたい．これ

Fisherグ）線形判別関数では，尤度比（fl／f2）が1す

によって，従来評佃の難しかった判別手法の優劣を定

なわち2群の確率密度が等しい点を判別境界点と呼ん量化できる．

で，判別している．これを，尤度比方式による 判別という．この場合F（x）＝0は，p次元のデータ空間を2分する超、仁面になる．そして，データxを代人して2002年11卜〜j▲© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（41）引る線形式Hi（gi（a）＝Xja′＋1）を考える．すなわち，判2．OLDFのアルゴリズム

別係数の空問において個々のデータは，判別係数の空2，1探索的なOLDFとIP−OLDF

間を2分する超平面になる．データ空聞を判別係数の文献［2〜4］で，1勺部楳本の誤分類数を崩小化する探空瀾＝こ置き検えて考えることが，探索的庖アルゴリズ

索的なOLDFが提案されている．

現実のデ岬タにおムの重要な点である．

いて，多次ノL止三規分布を仮定することには多くの場合

Gl群に械するデータxiで，gi（a）＞0になる半ヤ面

無理があり，特定の分布を仮定しないところに本手法を線形式ⅠIiの＋、㌣ヤ面とし，gi（a）く0になる、「、ド面の意義がある．すでに述べたとおり，l鮎酢標本の誤分を線形式Hiの一半、Iそl血＝二する．線形式Hiグ）＋半、ド類数を最小化するということは，内部標本に過敏にフ面に含まれる任意の係数aでデータxiは1仁しく判別

ィットし，外部標本の誤判別率は逆に悲くなる恐れがされ，一半平面の任意の係数aでデータⅩiは誤分類ある．

されることになる．
一方，OLDFによる内部標本の渋判別率がFisher

G2群のデータxiでは，両辺に｝をかけることにの線形判別関数に比べて少なければ少ないほど，対象より，一gi（a）＞0を十半、l頒とし，−gi（a）＜0を一、仁

データが正規性から乗離していることを分り易くホし平面とすることで，Gl群とい】じ不等号の向きになる．

てくれるのではないかと期待できる．また，OLDF

判別係数の空l言りaは，このようにしてn仰のデーの洪分類数は内部標本に対し−一一意に決まるので，事前タxiで作られるHiで2分割され，その結果としてハ

確率やリスクの導人によって誤分類数が異なり判別丁・体に分割される．このハ体の内部の点で，令ての線形法の比較．沖仰が雉しいというJlくを解l火できる．

式Hiの＋、巨、ド由iに合まれる個数を数え上げる．それ

本講座では，探索的なOLDFに代わって，新しくは，そのハ体の内部のノrl．（を、t勺j別係数とする判別式にお整数計画法を用いて定式化されたIP−OLDFを勧めた

いて，直しぐ判別されたデータの偶数になる．−一方，い．探索法に代わって，数理計画法を捌いることで真−1ト、ド1如こ含まれる個数を数え卜げれば誤分類数になの最適解が求まり，将来的には数理計l哺去のイ川一な情

る．すなわち，ハ休の】与部の∴l言に対して，止しぐ判別

報から確率論とは別の組み合わせ諭による、I利別分析のされた個数（あるいは誤分類数）が一志に決まる．

知見が得られるかもしれない．また，判別分析とl＝1帰このようにして，p次元、Pj別係数の空間は，Hiに分析などを含む線形モデルとして広い枠組みで考察でよって有限偶の凸体に分割され，ハ体の内部の一・1（判きる．

別係数）は，同じ誤分類数（あるいは正しぐ判別され

2．2 探索的なOLDFのアルゴリズムた数）をもつことになる．

（1）p次元データ空間における判別（3）簡単な例

線形判別関数の定数項を1に規準化した線形判別関

例えば，【￥Ilのようにデータが3件ある判別のl！り題を考える．1什卜lのデータがGl群に属し，（−0．14，数（f（x）＝bx′＋1）を考える．

Gl群に揺するデータⅩiが，f（xi）＞0ならば正しく−0．21）という伯を収るとすれば，これを係数とした

判別され，f（xi）く0ならば誤分類されたとする．この、川別関数は−0．14a−0．21b＋1で表される．線形式

場合，G2群に揺するデータxiでは，f（Ⅹi）＜0ならば

一0．14a−（）．21b十1＝0をHlとする．Hlによって，

ll三しぐ判別され，f（Ⅹi）＞0ならば誤分類されることに判別係数の空問は2分割される．−0．14a−0．21b

なる．

しかし，G2群のイ（等式の向辺に−をかけることで，

b
HI

H2

−f（Ⅹi）＞0ならば正しく判別され，−f（xl）＜0ならば娯分類されることになる．こうすることで，不等号の向きをGl群の場合と同じに統一一できる．
このような統一された表．記法において，判別スコアが負になるものを数え卜げれば，それが内部標本の誤分類数になる．
（2）判別係数の空間における判別

次に，仰々のデータⅩiを線形、川別関数の係数とす
42（42）

図1ExampleofOLDF
オペレーションズ・リサーチ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

＋1＞0をHlの＋、ド平面と呼ぶ．この、仁平面の任意

る． この場合も，誤分類数が1の2つの「ll体が選ばれの点（a，b）は，データ空間の判別係数に対応する．

る．次に推標軸を変更する．候補は，（a，H2），（a，−0．14a−0．21b十1＞（）であるから，データ空l問で考Hl），紬，H2），†b，H3），ib，fil）である．これらのえた判別関数ax＋by十1＞（）は，データ（−0．14，

新座標系で，それぞれ探索し，誤分類数凝小のものを−0．21）を正し探索する．座標変換で最小誤分類数を更新できなけれIfliにある点（判別係数）は，Hlに対応したデータをば，寺！圭られたハ休の頂点を頂点とする雌標系で探索す

1上しく判別する．一一ノノ，WO．14a−0．21b＋1＜0をる． 図1の場合，†ⅠIl，H2〉，〈H3，fIl），（H2，H3）

Hlグ）一半平面と呼ぶ．この空削の任意の点（a，b）は，である．この探索で，最小誤分類数が更新されなけれ

一0，14a−0．21b十1く0であるから，データ空間で考は この凸体を一応最適ハ体として終j する．OLDF

えた判別関数はa＊（、0．14）＋b＊（−（）．21）＋1＜0にの判別係数は，最適ハ体の内部のどの点でもよいが，なりデータ（−0．14，−0．21）を，洪判別する．すなわち，

一応全ての頂点の単純平均植を川いることが考えられHlの一半、ド面にある点（判別係数）は，Hlに対応

る．
このノバよは，残念ながらその、1川音のIBM汎川機をしたデータを酢一明りする．

2作トiのデータはG2群に属し（−2，2）としよう．

川いてもi汁算時間がかかり，19変数の今回川いてい

線形式H2は〜2a＋2b十1＝0であるが，G2群に属るl矢・、予データでは6変数までしか分析できなかった

するのでl山j辺に−をかけた2a−2b−1＝0をH2と［4］．また，探索的OLDFのアルゴリズムは行られた

する．2a−2b−1＞（）がf【Ⅰ2の十、ド、ドl巾であり，2a

解カi人城的な最適解か否かの保証がない欠点がある．

本講雌は，20年後に著しく計算速度が改善された−2b−1く0が−1ド、1旬iになる．

すなわち，lズ11は3つのデータで表される線形式

整数i汁画法を川いた新しい最適化手法の紹介である．

†Hl，H2，H3）の場合を考えている．これらの線形式

2．3IP−OLDFのアルゴリズム

で，2次元の一ド面は，7仰の凸体に分割される．央lい（1）数理計画法の回帰分析への応川にある三角形の内部の一・∴tは，3つの線形式で作られた

数札汁1叫法のI叶甘分析への応用として，車回棚分析＋、㌣や面の側にあるので，この内部の一・ご二（で表される判が2次．汁州法（Quadraticl）rogramming，QP）で，別係数をもつ判別関数は，3偶のデータを止しく分類

LAV（Least Absolute Value）回帰分析が線形計画

し，誤分類数はゼロになる．この三角形と辺を共有す

f去（Linear Programming，LP）で定式化できること

る3つのハ体は，その辺すなわち線形式のお／7：い反対はtl−−くから才旨摘されている［8，11］．さらに一般化し側にあるので，三角形側が＋、ド、打面であれば，反対側て，非線形計l哺去でLpノルムのl‖仰分析を扱うことのハ体の猥分類数は1咽える．逆に，もし三角形側がもできる．

−、ド平面の側にあれば，反対側の誤分類数は1少なく

しかし，最小I′1乗法による回帰分析を，わぎわざ2なる．このようにして，辺を共有するハ体は，部分顆

次計輔去で行うことは，操作性や計算時問の．・．−よからも数がおイ7二いに1異なることになる．

H策ではない．これに対して，LPを川いて誤差の絶

ここで重要なことは，崩過凸体は必ず＋半平面で帥まれていることである．もし−、㌣平面のものがあれば，対値の和を最小にするLAV回帰分析は，すでにSASなどの向川統計ソフトにも拉伏されている［6］．

反対側のハ体の誤分類数が1少なくなり，現flミの凸体（2）数理計画法の判別分析への応川が最適でなくなることになる．

すでに述べた通り，線形判別関数は回帰分析の特殊（4）探索的OLDFのアルゴリズム例であった．線形計内法や2次計l坤法による判別関数

三宅と新村［4］は，p次元空【粧ぐ駄分類数を姑小にの定式化は，その延長組上で行える．

するII11休を探累的に探すアルゴリズムを提案している．

簡単に紺介すれば，最初はa軸とb軸を初期推標

Glover［10］は，線形計州法をflい−て定式化された判別関数のそれまでの研究を数人成し，それらを含むとする．a軸とは，H3，H2，Hlの順に交差してい改良モデルを掟案している．

る．交差点に接するハ体の誤分類数を調べ卜げると，

ス変数を個別データ毎に導人し，それらに対して黄み

H2とHlの交差一・∴（に接する凸体（今の場合は「ii＝ニもを導入することで，潰分類されたケースの判別咤界ノ∴（の）の訳分類数が1と−一番小さい．次に，b軸と交差からの抑離の加重利から正しく分頬されたケースの判する∴l．（に接するハ体で崩小誤分類数を持つものを調べ

別蝿軋・1（からの抑離の加1車利を引いたものをl】的関数

2002年1‖1∫© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

スラック変数とサープラ（43）43

としている．そして，それを鼓小化する線形計画法のモデルとして定義している．誤分類されたケースの黄みを1とし，正しく分類されたケースの重みを0とし‖的関数は，e−の和すなわち判別囁界点を緩める制
約式の数（内部標本の誤分類数）を最小化している．

そして，これでもってl勺部標本の萬分類数を最小にたものが，本講煉で取リートげるLP線形ごl明り関数であするハ体の頂点（判別係数a）が最適解として求めらる．

れる．ただし，数理計内法モデルの特徴として，個別
このように重みを過当1にノブ・えることで，LPで定式

データ毎に重みづけすることは容易で，符eiに轟み化できる判別関数のモデルを包括的に記述した点で，を掛ければすむことである．こうすることで，Gloverの研究は．評価できる．

Gloverのように，色々な派生手法を新たに定義でき

しかし，実際のデータへの過川にはいたっておらず，

小さな例題で検証しているのみである．また，せっかく巌過化手法を刷いているのに，悪意的な重みを川いる．しかし，悪意的な重みの利川は，最適化のメリッ
トを相殺すると考える．

実際には，イ（等号を逆にしたものも計算し，誤分類ることで，寺ぎ手られた結果の解釈が難しくなる問題もあ

数の少ないほうを選ぶ必要がある．また，得られた解る．

は最適I†11体の丁貞点である．巌終的には，探索的これに対して，整数計内法を刷いた判別関数の研究は一般的でない．整数計内法のような組み合わせ崩過OLDFで緋介したように全ての頂点を求め単純、lえ均で得られた佃を判別係数とする必要がある．

化は，計算時問がかかり，軟米の大学で広く利11ほれ（4）LP線形判別関数の定式化ているシカゴ人学で開発されたLINDOの普及を行っ一〟，C＝1として，eiを止の実数とすれば，IP−てきた筆者の経験では，て実印問題に適川できるように

OLDFのモデルを，計算時間のかからないLPによるなったのは1990年代の中頃に人ってからである．そ

線形判別関数として定式化できる．LP線形判別関数のため，本来IPで定式化すべき問題もLPで定式化

は，誤分類されるケースの判別境界点からの抑離の和することが，これまでは数理計画法でのモデル作成のを巌小化している．判別境弊点から離れたケースほどひとつの見識であった．

大きなウエイトをrliめる．これに対し，IP−OLDFは，（3）IP−OLDFの定式化

誤分類されるケースの佃1数の和を崩小化している．す整数計画法を用いた最適判別関数は，定式化するとなわち，誤分類されるケースは同じウエイトになる．

Gloverは，次のLPモデルで判別関数を定式化し次のようになる．
MIN el＋e2十…＋em＋e（m＋1）十‥・十e（m＋。）

ている．

ST

MIN h。u。＋∑hlui−k。Vo〜∑kiV．

xllal十・・・＋xplap十1＞−CelST
ao＋xljal＋…＋xpjap＋uo＋uj−Vo−Vj＝b（ただし，j＝1，…，n）

END

Xlmal＋・・・＋xpmap＋1＞−Cem−Xl（m＋1）al−・・・−Xp（m＋1）apLl＞−Ce（m＋ユ）すなわち，ujは誤分類されたデータの判別境界点からの抑離である．u。はデータ全体の平均である．
一ガ，Vjは止しく分類されたデータの判別境界点かーXl（m＋n）al≠・・・LXp（，n＋n）apLl＞LCe（m＋。）

らの距離である．Ⅴ。はデータ全体の・、ト均である．臼

END

的関数は，これらの抑離に重みを掛けて，誤分類され最初のm偶の制約式はGl群のデータに対応したた距離の和からj［しく分類された距離の和を引いて，制約式であり，その後のn個の制約式はG2群のデ崩小化することを提案している．これにより，誤分類ータに対応している．cは大きな二it三の定数であり，ei

された距離の利を栽小化し，止しく分類されたデータ

は各データxlに対応し，各データが誤分類されればの抑離の和を崩大化するという，多排的最適化をLP

1に，正しく分類されれば0になる0／1型の整数変数で定式化したことになる．

とする．こうすることで，正しく分類されるデータの判別境界点は0のまま，誤分類されるデータの判別境
界を0から一Celに緩めることができる．
44（44）

LP線形判別関数は，ho＝hi＝1，k。＝ki＝0にしているので，Gloverグ）モデルの特殊例になる．
このように個別データ毎に東みu．iとvjを雪一え多様
オペレーションズ・リサーチ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

なモデルを定義できるが，悪意的な判断が必要となり，［7］新村秀一，三宅章彦：重回帰分析と判別分析のモデル

その導入は慎重を要する．

また，IP−OLDFとの比較のため，今回の定式化を採用する．別の機会に，Gloverのモデルで再評価し決定（1ト19変数をもつC．P．D．データの多重共線性の解消−，医療情報学，3−3，107†123，1983．

［8］新村秀一：LINDOを用いた線形回帰分析例，円本オてみる必要があるだろう．
以下次号から，

実践，朝倉書店］．

ペレーションズ・リサーチ学会秋季研究アブストラクト

IP−OLDFとLP線形判別関数を，3種類のデータを用いて既存の2つの判別関数と比較評価する．すなわち，新しい手法は既存の手法と複数のデータで評価することが重要である．

集，13−14，1984．
［9］森村英典，牧野都治編：統計・OR活用事典，東京書籍，
1984．

［10］F．Glover，Improve Linear programming models
for discriminant analysis，Decision Sciences，2，771−

本講座の多くは，成踵大学研究肋成金に負っている．

785，1990．

［11］新村秀一，高森寛：実践数理計画法MLINDOを剛−

参考文献て岬，朝倉書店，1992．

［1］A．Miyake＆S．Shinmura，Error rate oflinear［12］新村秀一：垂回帰分析と判別分析のモデル決定（2）−discriminant function，F．T．de Dombal＆F．Gremy，

19変数をもつC．P．D．データのモデル決定−，成践大学

editors435−445，North−Holland PublishingCompany，

経済論集，27−1，180−203，1996．
［13］新村秀一：パソコン楽々統計学，講談社，1997．

1976．

［2］A．Miyake＆S．Shinmura，An Algorithm for the

OptimalLinear Discriminant Function，Proceedingsof the International Conference on Cybernetics andSociety，1447▼1450，1978．

［14］新村秀一：数理計画法を用いた最適線形判別関数，計算機統計学，1ト2，89−101，1998，［15］新村秀一，垂水共之：2変量正規乱数データによる

IP〜OLDFの評価，計算機統計学，12L2，107−124，1999．

［3］S．Shinmura＆A．Miyake，Optimallinear di− ［16］S．Shinmura，A new algorithm of thelinear di−
scriminant functions and their application，Proceed−

scriminantfunctionsusingintegerprogramming，New

ingsoftheCOMPSAC79，167172，1979・

Trendsin Probability and Statistics Volumn5，133−［4］三宅章彦，新村秀一：最適線形判別関数のアルゴリズ

142，2000．

ムとその応札医用電子と生体了Ⅰ二学，18−1，15−20，1980．

［17］S．Shinmura＆T．Tarumi，Evaluationofthe opti−［5］新村秀一，鈴木隆一朗，中西克巳：胃Ⅹ線像の各種判

mallinear discriminant functions uslnginteger pro−

別分析，オペレーションズ・リサーチ，26−1，51−60，1981．

［6］］．P．Sall，SAS RegressionApplications，SASInsti−
tuteInc，1981［新村秀一（1986），SASによる回帰分析の2002年1月号

gramming（IPqOLDF）by the normalrandom data，Proceedingsin ComputationalStatistics2000，95−96，
2000．

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（45）45